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

CHAPTER
VLSI Models of Computation
The electronics revolution initiated by the invention of the transistor by Schockley, Brattain,
and Bardeen in 1947 accelerated with the invention of the integrated circuit in 1958 and 1959
by Jack Kilby and Robert Noyce. An integrated circuit contains wires, transistors, resistors,
and other components all integrated on the surface of a chip , a piece of semiconductor material
about the size of a thumbnail. And the revolution continues. The number of components that
can be placed on a semiconductor chip has doubled almost every 18 months for about 40 years.
Today more than 10 million of them can fit on a single chip. Integrated circuits with very large
numbers of components exhibit what is known as very large-scale integration (VLSI). This
chapter explores the new models that arise as a result of VLSI.
As the size of the electronic components decreased in size, the area occupied by wires
consumed an increasing fraction of chip area. In fact, today some applications devote more
than half of their area to wires. In this chapter we examine VLSI models of computation
that take this fact into account. Using simulation techniques analogous to those employed in
Chapter 3 , we show that the performance of algorithms on VLSI chips can be characterized
by the product AT 2 ,where A is the chip area and T is the number of steps used by a chip
to compute a function. We relate AT 2 to the planar circuit size C p , Ω ( f ) of a function f ,a
measure that plays the role for VLSI chips that circuit size plays for FSMs. The AT 2 measure
is the direct analog of the measure C Ω ( δ , λ ) T for the finite-state machine that was introduced
in Chapter 3 ,where C Ω ( δ , λ ) is the size of a circuit to simulate the next-state and output
functions of the FSM. We also relate the measure A 2 T to C p , Ω ( f ) .
575