Area‐time complexity on a vlsi model with boundary layout assumption

<jats:title>Abstract</jats:title><jats:p>In the VLSI circuit, the area occupied by the circuit and the time required for computation are important measures of evaluation. Thompson, Brent and Kung have proposed a VLSI model to evaluate the VLSI circuit by the area <jats:italic>A</jats:italic> and the computation time <jats:italic>T.</jats:italic> It is an important problem to examine the change of the area and the computation time when a certain practical assumption is imposed on the VLSI model. This paper shows that when an assumption that the input and the output are connected at the boundary of the circuit (called boundary‐layout assumption) is imposed on the VLSI model, relations <jats:italic>AT</jats:italic> = ω(max(<jats:italic>n, m</jats:italic>)) and <jats:italic>AT</jats:italic><jats:sup>a</jats:sup> = ω(max(<jats:italic>n, m</jats:italic>)[max(log <jats:italic>N</jats:italic>, log <jats:italic>M</jats:italic>)]<jats:italic>a</jats:italic>) (α > 1) are produced for the nontrivial class of <jats:italic>n</jats:italic>‐input, <jats:italic>m</jats:italic>‐output logic functions. Above, <jats:italic>N</jats:italic> is the maximum of <jats:italic>N</jats:italic><jats:sub>1</jats:sub>, …, <jats:italic>N</jats:italic><jats:sub>m</jats:sub>, where <jats:italic>Ni</jats:italic> is the number of inputs on which the <jats:italic>i</jats:italic>th output depends, and <jats:italic>Mj</jats:italic> is the maximum of <jats:italic>M</jats:italic>1, …, <jats:italic>Mn</jats:italic>, where <jats:italic>Mj</jats:italic> is the number of outputs which depends on the <jats:italic>j</jats:italic>th input. When the boundary‐layout assumption is not imposed, <jats:italic>AT</jats:italic>α = ω(max(<jats:italic>n, m</jats:italic>){max(log <jats:italic>N</jats:italic>, log <jats:italic>M</jats:italic>)}α‐1) (α ≥ 1) holds. Consequently, for this class of functions, the boundary‐layout assumption properly affects <jats:italic>AT</jats:italic>α (α ≥ 1). It is shown also by an actual example that there exist functions which achieve the lower bounds.</jats:p>