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², where A is the chip area and T is the number of steps used by a chip to compute a function. We relate AT² to the planar circuit size $C_{{\rm p},\Omega}(f)$of a function f, a measure that plays the role for VLSI chips that circuit size plays for FSMs. The AT² measure is the direct analog of the measure $C_{\Omega} (\delta, \lambda) T$ for the finite-state machine that was introduced in Chapter 3, where $C_{\Omega} (\delta, \lambda)$ is the size of a circuit to simulate the next-state and output functions of the FSM. We also relate the measure A²T to $C_{{\rm p},\Omega}(f)$.