VLSI Models of Computation - Models of Computation: Exploring the Power of Computing - page 602

realization of normal algorithms are due to Preparata and Vuillemin [ 262 ], as explained in
Chapter 7 .Lengauer[ 193 ] provides an in-depth treatment of algorithms for VLSI chip lay-
out.
Most authors prefer to derive lower bounds on AT 2 by partitioning the planar region oc-
cupied by chips [ 59 , 195 ,326]. In effect, they employ a physical version of the planar separator
theorem. The characterization of VLSI lower bounds in terms of planar circuit complexity in-
troduced by Savage [ 288 ] reinforces the connection between memoryless and memory-based
computation explored in Chapter 3 but for planar computations by VLSI chips. It also pro-
vides an opportunity to introduce the elegant planar separator theorem of Lipton and Tarjan
[ 203 ]. Lipton and Tarjan [ 204 ] developed quadratic lower bounds on the planar circuit size of
shifting and matrix multiplication before the connection was established between VLSI com-
plexity and planar circuit size. Improving upon results of [ 288 ], McColl [ 209 ]andMcColland
Paterson [ 210 ] show that almost all Boolean functions on n variables require a planar circuit
size of Ω( 2 n ) and that this lower bound can be achieved for all functions to within a constant
multiplicative factor close to 1. Turan [ 336 ] has shown that the upper bound of Lemma 12.6.1
is tight by exhibiting a family of functions of linear standard circuit size whose planar circuit
size is quadratic.
Abelson [ 1 ]andYao[ 366 ] studied communication complexity with fixed partitions. Yao
[ 367 ]andLiptonandSedgewick[ 202 ] made explicit the implicit connection between VLSI
communication complexity and the derivation of the AT 2 lower bounds. (See also [ 236 ],
[12], and [194] for a discussion of the conditions under which lower bounds can be derived
on the VLSI communication complexity measure.)
Many authors have contributed to the derivation of semellective lower bounds for partic-
ular functions. Among these are Thompson [ 326 , 327 ,328, 329 ], who obtained bounds of the
form AT 2 =Ω( n 2 ) for the DFT and sorting, as did Abelson and Andreae [ 3 ]andBrent
and Kung [59] for integer multiplication, JaJ´aandKumar[ 149 ] for a variety of problems, Bi-
lardi and Preparata [ 41 ] for sorting, Savage for matrix multiplication, inversion, and transitive
closure [ 289 ] and binary integer powers and reciprocals [ 288 ], and Vuillemin for transitive
functions [ 355 ] (see Problem 10.22 ). These authors generally show that the lower bounds for
functions can be met either to within a small multiplicative constant factor.
Good VLSI designs have been given by Baudet, Preparata, and Vuillemin [ 31 ]forcon-
volution, Guibas and Liang [ 123 ] for systolic stacks, queues, and counters, and Kung and
Song [ 183 ] and Kung, Ruane, and Yen [ 182 ] on 2D convolution. Also, Luk and Vuillemin
[ 207 ] give an optimal VLSI integer multiplier and Mehlhorn has provided optimal algorithms
for integer division and square rooting [ 217 ] whose range of optimality has been extended
by Mehlhorn and Preparata [ 219 ]. Preparata [ 258 ] has given a mesh-based optimal VLSI
multiplier for large integers and Preparata and Vuillemin have given optimal algorithms for
multiplying square [ 260 ] and triangular matrices [261]. C. Savage [ 284 ] has given a systolic
algorithm for graph connectivity.
Lower bounds for the semellective computation of predicates by VLSI algorithms have
been derived by Yao [ 367 ] for graph isomorphism, by Lipton and Sedgewick [ 202 ]forthe
recognition of context-free languages, pattern matching, and binary integer factorization test-
ing, and by Savage [ 288 ] for the characteristic predicates of multi-output functions.
Hochschild [ 134 ], Kedem and Zorat [ 163 , 164 ], Savage [ 290 , 291 ], and Turan [337] have
developed lower bounds on performance of multilective VLSI algorithms. Savage has explored
multilective planar circuit size [ 291 ], giving a multi-output function with a Ω( n 4 / 3 ) lower