Introduction to Circuit Layout

In the combinatorial sense, the layout problem is a constrained optimization problem. We are given a description of a circuit—most often as a netlist, which is a description of switching elements and their connecting wires. We are looking for an assignment of geometric coordinates of the circuit components— in the plane or in one of a few planar layers—that satisfies the requirements of the fabrication technology (sufficient spacing between wires, restricted number of wiring layers, and so on) and that minimizes certain cost criteria (the area of the smallest circumscribing rectangle, the length of the longest wire, and so on). Practically all versions of the layout problem as a whole are intractable; that is, they are NP-hard. Thus, we have to resort to heuristic methods. One of these methods is to break up the problem into subproblems, which are then solved one after the other. Almost always, these subproblems are NP-hard as well, but they are more amenable to heuristic solution than is the layout problem itself. Each one of the layout subproblems is decomposed in an analogous fashion. In this way, we proceed to break up the optimization problems until we reach primitive subproblems. These subproblems are not decomposed further, but rather are solved directly, either optimally—if an efficient optimization algorithm exists—or approximately. The most common way of breaking up the layout problem into subproblems is first to do component placement, and then to determine the approximate course of the wires in a global-routing phase. This phase may be followed by a topological compaction that reduces the area requirement of the layout, after which a detailed-routing phase determines the exact course of the wires without changing the layout area. After detailed routing, a geometric-compaction phase may further reduce the area requirement of the layout. This whole procedure may be done hierarchically, starting with large blocks as circuit components, which are themselves laid out recursively in the same manner. This recursive process may be controlled by algorithms and heuristics that allow for choosing among layout alternatives for the blocks such that the layout area of the circuit is minimized. If cells are variable in this sense, the placement phase is called floorplanning. Exactly how a given version of the layout problem is broken up into subproblems depends on both the design and the fabrication technology. For instance, in standard-cell design the detailed-routing phase essentially reduces to channel routing. In gate-array layout, the placement phase incorporates an assignment of functional circuit components to cells on the master.