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

This result can be applied to any of the fully normal algorithms described in Section 7.6
and the Benes permutation network discussed in Section 7.8.2 .

12.6 Area-Time Tradeoffs
The AT 2 measure encountered in the last section is fundamental to VLSI computation. This
is established by deriving a lower bound on AT 2 in terms of the planar circuit complexity,
C p , Ω ( f ) ,ofthefunction f computed by a VLSI chip of area A in T steps. A similar result is
derived for the product A 2 T . The planar circuit size of f is the size of the smallest memoryless
planar circuit for f .Themeasures AT 2 and A 2 T are the sizes of two different memoryless
planar circuits that compute the same mapping from inputs to outputs as a VLSI chip of area
A that executes T steps.

12.6.1 Planar Circuit Size
We now formally define planar circuit size and show how it relates to the standard circuit size
measure.

DEFINITION 12.6.1 A planar circuit over the set X is a logic circuit over the set X that has been
embedded in the plane in such a way that gates do not overlap but edges may cross. A planar circuit
is semellective if there is a unique vertex at which each input variable is supplied. Otherwise, the
planar circuit is multilective .
The size of a planar circuit is the number of inputs, edge crossings, and gates drawn from
abasis Ω=

h : X 2

{ → X } that the circuit contains. The planar circuit size of a function

f : X n X m over Ω , C p , Ω ( f ) ,isthesizeofthesmallestplanarcircuitfor f over the basis Ω .

A multilective circuit of order μ , μ

→

m has μn input vertices.
The size of the smallest multilective planar circuit of order μ for f is denoted C ( μ )

≥

1 ,forafunction f :

B

n

→B

p , Ω ( f ) . If the planar

circuit is semellective, the planar circuit size of f is denoted C ( 1 )

p , Ω ( f ) or C p , Ω ( f ) when confusion

is not likely.

Every binary function has a planar circuit. To see this, observe that every function has a
circuit, which is a graph, and that every graph has a planar embedding with edge crossings.
The planar circuit size of a function is at worst quadratic in its standard circuit size, as we now
show.

LEMMA 12.6.1 The (multilective) planar circuit and standard size of f : B

n m relative to

→B

the basis Ω are in the following relationship where r is the fan-in of Ω .

r 2 C Ω ( f ) / 2 + C Ω ( f )+ n
Proof The first inequality follows because the planar circuit size measure includes inputs,
crossings, and gates, whereas the circuit size measure includes only gates.
Consider an embedding of a standard circuit for f containing C Ω ( f ) gates. In such
an embedding it is not necessary for any two edges to intersect more than once because if
they violate this condition the edge segments between any two successive crossings can be
swapped so that these two crossings can be eliminated. Since every gate has at most r inputs,
a minimal standard circuit for f has at most rC Ω ( f ) edges connecting gates. It follows that

C Ω ( f )+ n ≤ C p , Ω ( f ) ≤