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

(a) (b) (c)
Figure 12.6 (a) The result of shrinking a physical gate to a point. (b) A crossing of two wires,
and (c) four types of connection between two wires.

n g satisfy the following bounds.

A/λ 2 n w ≤

A/λ 2 n g ≤

Because each point of crossing or touching of wires occupies area at least λ 2 ,thenumber
of points at which wires cross and touch on each of the ν layers of a chip that has area A is
at most A/λ 2 .AsshowninFig. 12.6 (a), when gates are made infinitesimal two additional
bends are created at the point at which the output wire touches the gate. This can be viewed
as adding four wire bends per gate. Since the number of gates is at most A/λ 2 ,wehavethe
following bound on n cr , the number of wire crossings and touchings.
n cr ≤

( ν + 4 ) A/λ 2

Consider the first of the two simulations. T layers of one chip are placed one above the
other. To expose overlapping wires, displace all layers to the northeast by an infinitesimal
amount. Every pair of wires that cross or meet has the potential to introduce crossings, as
suggested in Fig. 12.7 (a) and (b). The maximum number of crossings that can be introduced
pertouchingorcrossingofwiresis T 2 . Since the number of input vertices is O ( AT ) ,this
provides an upper bound of O ( AT 2 ) on the number of inputs, gates, and crossings of the
resultant planar circuit.
Now consider the second simulation. T copies of one chip are laid side-by-side and the
layout of each chip opened and at most n w parallel wires inserted to make connections to
adjacent chips. Since there are n w wire segments on a single chip, at most n 2 w new wire
crossings are introduced on one chip. Thus, the number of inputs, gates, and crossings in this
layout is O ( AT + n 2 w T )= O ( A 2 T ) .
The following theorem, which is an application of Theorem 3.1.1 to the VLSI model,
summarizes the above results. It makes use of the fact the planar circuit size of a function
f computed by a VLSI chip of the kind described above is no larger than that of the planar
circuits just constructed. This theorem demonstrates the importance of the measures AT 2 and
A 2 T as characterizations of the complexity of VLSI computations. It also shows that lower
bounds on the performance of VLSI chips can be obtained in terms of the planar circuit size
of the functions computed by them.