C H A P T E RVLSI Models of ComputationThe 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 1959by Jack Kilby and Robert Noyce. An integrated circuit contains wi res, transistors, resistors,and other components all integrated on the surface of a chip, a piece of semiconductor mate rialabout the size of a th umbnail. And the revolution continues. The number of components thatcan be placed on a semiconductor chip has doubled almost every 18 month s for about 40 years.Today more than 10 m illion of them can fit on a single chip. Integrated circuits w ith very largenumbers of components exhibit what i s known as ver y large-scale integration (VLSI). Thischapter explores the new models that arise as a result of VLSI.As the size of the electronic components d e creased in size, the area occupied by wiresconsumed an i ncreasing fraction of chip area. In fact, today some applications devote morethan half of their area to wires. In this ch apte r we examine VLSI models of computationthat take this fact into account. Using simulation techniques analogous to those employed inChapter3, we show th at the performance of algorithms on VLSI chips can be characterizedby the product AT2, where A is the chip area and T is the number of steps used by a chipto compute a function. We relate AT2to the planar circuit size Cp,Ω(f) of a function f ,ameasure that plays the role for VLSI chi ps that circuit size plays for FSMs. The AT2measureis the direct analog of the measure CΩ(δ, λ)T for the finite-state machine that was introducedin Chapter 3, where CΩ(δ, λ) is the size of a circuit to simulate the next-state and outputfunctions of the FSM. We also relate the measure A2T to Cp,Ω(f).575576 Chapter 12 VLSI Models of Computation Models of Computation12.1 The VSLI ChallengeThe desi gn of VLSI chips represents an enormous inte lle ctual challenge akin to that of con-structing very large programs. They each involve the assembly of m illions of eleme nts, instruc-tions i n the case of software, and electronic components in the case of ch ips. The design andimplementation of VLSI chips i s also challenging because it i nvolves many steps and manytechnologies. In this section we provide a brief i ntroduction to this process as preparationfor the introduction of the VLSI models and algori thms that are the principal topics of thischapter.12.1.1 Chip FabricationA VLSI chip consists of a number of conducting, insulating, and doped layers that are placedon a semiconductor substrate. (A doped layer is created on the surface of the substrate byinfusing small concentrations of impurities into the semiconductor. This is called doping.)The layers are created using ma sks, templates with open regions through which ionizing radi-ation is projected onto the surface of th e semiconductor. The radiation changes the chemicalproperties of a previously deposited photose nsitive material so that the ex posed regions canbe washed away with a solvent. The mate rial that is now exposed can be doped or removed.Doping is used to create transistors and wires. A removal step is used when a metallic layer hasbeen previously deposited from which sections are to be removed, leaving wires. A chip mayhave several layers of wires separated by layers of insulating material in addition to the dopedlayers that form transistors and wi res. The layout of a NAND gate is shown schematically inFig.12.1, in w hich the shadings of rectangles and annotations i dentify to a chip de signer thetypes of materi als used to realize the gate.cVssp-plusp-wellVddbacab(a) (b)Figure 12.1 The schematic layout of a NAND gate and its logical symbol.c!John E Savage 12.1 The VSLI Challenge 577Geometric design rules specify the amounts of overlap of and separation between metal anddopant rectangles that are needed to guarantee the desired electrical and electronic properties ofa VLSI circuit. If wires are to o thin, electrons, which move through them at very high speeds,can cause excess heating as well as dislodge atoms and create an open circuit (this is calledmetal m ig ration), espe cially at points at which a wi re bends to descend into a well createdduring chi p fabrication. Similarly, if wires are too close, an error in registration of masks maycause short circuits between wires. Also, since transistors are constructed through the dopingand overlaying of insulating and conducting materials, if the regions defining a transistor aretoo small, it will not behave as expected.The geometric design rules for a particular chip technology can be quite complex. For thepurpose of analy sis they are simplified into a few rules concerning the width and se parationof rectangles, the amount of area required for contacts be tween wires on layers separated byinsulation, and the size of the various rectangular regions that form gates and transistors. Assuggested by this discussion, a VLSI chip is quasiplanar; that is, its components lie on a fewlayers, which are separated by ins ulation except where contacts are mad e between layers.12.1.2 Design and LayoutMany tools and te ch niques have been developed to address the complexity of chip layout.Typically these tools and techniques use abstraction; that is, they decompose a problem intosuccessively lower level units of increasing complexity. At each level th e number of units in-volved in a design is kept s mall so that the design is comprehensible.The design of a VLSI chip begins with the specifi cation of its functionality at the func-tional or algorithmic le vel. Either a function or an algorithm is given as the starting point.An algorithm is then produced and translated into a specification at the a rchitectural level.At this level a chip is specified in terms of large units such as a CPU, random-access memory,bus, floating-point uni t, and I/O devi ces . (The material of Chapters3 and 4 is relevant at thislevel.) After an architectural specification is produced, design commences at the logical level.Here particular methods for realizing architectural units are chosen. For example, an ad dercould be realized eithe r as a ripple or a carry-lookahead adder depending on the stated speedand cos t objectives. (The material of Chapter2 applies at this level.)At the gate level, the next level in the design process, a technology, such as NMOS andCMOS, is chosen i n which to realize the