ABSTRACT
One of the many application areas that has made effective use of algorithm design and analysis is computer-aideddesign (CAD)ofdigital circuits.Manyaspectsof circuitdesignyield tocombinatorial models and the algorithmic techniques discussed in other chapters. In this chapter we focus on one area within the field of CAD: layout of very large scale integrated (VLSI) circuits, which is a particularly good example of the effective use of algorithm design and analysis. We will discuss specific problems in VLSI layout and how algorithmic techniques have been successfully applied. This chapter will not provide a broad survey of CAD techniques for layout, but will highlight a few problems that are important and have particularly nice algorithmic solutions. The reader may find more complete discussions of the field in the references discussed in Section 8.9 at the end of this chapter. Integrated circuits aremadeby arranging active elements (usually transistors) on aplanar substrate
and interconnecting these elements with conducting wires that are also patterned on the planar substrate [41]. There may be several layers that can be used for wires, but there are restrictions on how wires in different layers can connect, as well as requirements of separations between wires and elements. Therefore, the layout of integrated circuits is usually modeled as a planar-embedding problem with several layers in the plane. VLSI circuits containmillions of transistors. Therefore, it is not feasible to consider the positioning
of each transistor separately. Transistors are organized into subcircuits called components; this may be done hierarchically, resulting in several levels of component definition between the individual
8-1
transistors and the complete VLSI circuit. The layout problem for VLSI circuits becomes one of positioning components and their interconnecting wires on a plane, following the design rules, and optimizing some measure such as area or wire length. Within this basic problem structure are a multitude of variations rising from changes in design rules and flexibilities within components as to size, shape, and regions where wires may connect to components. Graph models are used heavily, both to model the components and interconnections themselves and to capture constraint between objects. Geometric aspects of the layout problem must also be modeled. Most layout problems are optimization problems and most are NP-complete. Therefore, heuristics are also employed heavily. In the following text, we present several of the best known and best understood problems in VLSI layout.
