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

other models is the elapsed time in seconds, which is approximated by the number of steps
multiplied by the length of the longest step. This time is generally a function of the area of the
chip and the problem for which the chip is designed.
Another measure of time, but one that is given only a cursory examination, is the period
P of a VLSI chip. This is the time between successive inputs to a pipelined chip, one designed
to receive a new set of inputs while the previous inputs are propagating through it. Pipelining
is illustrated in Section 12.5.1 on H-trees and Section 11.6 on block I/O.
In this chapter we assume that VLSI chips compute a single function f : X n

X m ,
a perfectly general assumption that allows any FSM computation to be performed. While
this allows the VLSI chip to be a CPU or a RAM, to convey ideas we limit our attention
to functions that are simply defined, such as matrix multiplication and the discrete Fourier
transform.
The variables of the function computed by a VLSI chip are supplied via its I/O ports. A
single port can receive the values of multiple variables but at different time instances. Also,
the value of a variable can be supplied at multiple ports, either in the same time step or in
multiple time steps. However, the outputs of a function computed by a chip are supplied once
to an output port. As noted above, a port can be either an input or output port or serve both
purposes, but not in the same time step.
As with the FSM, we cannot allow either the time or the I/O port at which data is received
as input or is supplied as output to be data-dependent. To do otherwise is to assume that an
external agent not included in the model is performing computations on behalf of the user.
We can expect misleading results if this is allowed. Thus, we assume that each I/O operation
is where- and when-oblivious ; that is, where an input or output occurs is data-independent,
as are the times at which the I/O operations occur.
For many VLSI computations it is important that the input data be read once by the
chip even if it may be convenient to read it multiple times. (These are called semellective or
read-once computations.) For example, if a chip is connected to a common bus it may be
desirable to supply the data on which the chip operates once rather than add hardware to the
chip to allow it to request external data. However, in other situations it may be desirable to
provide data to a chip multiple times. Such computations are called multilective . Multilective
computations must be where- and when-oblivious.
If a multilective VLSI algorithm reads its n input variables βμn times but only μn times
when multiple inputs of a variable (at multiple time steps) at one I/O port are treated as a
single input, then the algorithm is

→

( β , μ )

-multilective .

12.4 VLSI Performance Criteria
As stated in Theorem 7.4.1 ,theproduct pT p of the time, T p , and the number of processors, p ,
in a parallel network of RAM processors to solve a problem cannot be less than the serial time,
T s , on a serial RAM with the same total storage capacity for that problem. Applying this result
to the VLSI model, since the number of processors of any given size that can be placed on a
chip of area A is proportional to A , it follows that the product AT of area with the time T
for a chip to complete a task cannot be less than the serial time to compute the same function
using a single processor; that is, AT =Ω( T s ) .
In the next section we show that the matrix-vector multiplication and prefix functions can
be realized optimally with respect to the AT measure. This holds because these problems have