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

To complete the physical modeling of chips we recognize three types of transmission
model , the synchronous, transmission-line, and diffusion models. The synchronous model
assumes that one unit of time is needed to transmit a bit across a wire, independent of its
length. This is a good model when the switching time of gates is large by comparison with
the time to transmit data through a wire or when wires are short, a situation that prevails for
most designs. When it does not prevail, the unit of transmission time can be increased so that
it does apply. The transmission-line model assumes that the time to transmit a bit across a
wire is proportional to its length (see Problems 12.1 and 12.2 ), whereas the diffusion model
assumes it is quadratic in its length. The models apply to VLSI chip technologies at different
wire lengths. The synchronous, transmission-line, and diffusion models apply to wires that are
short, medium-length, and long, respectively.
Although we do not examine energy consumption in this chapter, the type of gate used
can have a large impact on the amount of energy consumed during a computation. NMOS
transistors consume energy all the time, whereas CMOS transistors consume energy only when
they change their state.
When the area of I/O pads and gates are comparable, the placement of the pads on a VLSI
chip can have a big impact on the area occupied by a chip. For example, if the chip realizes a
tree and its n leaves (and their pads) are placed on the boundary of a convex region, as noted
in Problem 12.3 , the chip must have area proportional to n log n . However, as shown in
Section 12.5.1 , when its leaves can be placed anywhere, there is a layout for a tree (known as
the H-tree) that has area proportional to n . If the I/O pads are much larger than the gates, the
impact of their placement is diminished.

12.3 VLSI Computational Models
We assume that a VLSI chip implements a finite-state machine instantiated as a clocked se-
quential machine. (A chip could also model an analog computer rather than a digital one, a
topic not discussed in this topic.) Although every FSM is eventually realized from two-input
gates, binary memory cells, and wires carrying binary values (see Section 3.1 ), chips are gener-
ally designed around an aggregate model for data. That is, if operations are done on integers,
the wires associated with an integer travel together on the chip surface. Although the time re-
quired for an operation on data depends on the size of alphabet from which the data is drawn
and on the complexity of the operation itself, we simplify the analysis by assuming that one
unit of time is taken. A more sophisticated analysis takes these factors into account.
To be concrete we let the states of an FSM be represented as tuples over a set X of binary
b -tuples. We also assume that gates realize functions

h : X 2

{ → X }

and that memory cells
hold one value of X .Werecognizea logic circuit over the set X as the graph of a straight-line
in which the operations are drawn from a basis

h : X 2 . This model is used to study

problems defined over non-binary alphabets, such as matrix multiplication and the discrete
Fourier transform over rings.
We continue to use the notation λ for the minimum feature size of a VLSI chip even
though we now allow data to be treated as values in the set X . When the set X is big, it will
be important to make use of its size in accounting for the area occupied by wires and gates, an
issue that we ignore in this chapter.
Computation time in the synchronous model is the number of steps executed by a chip.
This is the same measure of time used for finite-state machines. Computation time in the

{ → X }