Combinatorial Algorithms for Integrated 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.

In this chapter, we will lay the formal framework for discussing the algorithmic problems arising in circuit layout. We will be rather formal right from the beginning, so as to be able to describe clearly the algorithmic structures with which we will be working. The first definition we will give is that of an algorithmic problem.

This chapter summarizes the results from graph theory that will be used in this book. Graphs are one of the fundamental structures treated in discrete mathematics. We begin with an extensive set of classical definitions from graph theory (Section 3.1). Then we review general algorithmic techniques for exploring graphs so as to impose structures on them (Sections 3.2 to 3.7). Subsequently, we discuss important graph problems that are used in many areas of circuit layout. In Sections 3.8 to 3.10, we consider problems of finding paths and more general connection subnetworks in graphs. Such problems occur naturally in wire routing. Path problems are also the basis of many optimization procedures, such as compaction and area minimization in floorplanning. In Sections 3.11 and 3.12, we discuss network flow and matching problems that are of special importance in circuit partitioning and detailed routing, but that also find applications in other aspects of circuit layout. In Section 3.13, we include newer material on processing hierarchically defined graphs. This material gains its significance through being the formal reflection of hierarchical circuit design (see Section 1.2.2.1). Finally, we summarize results on planar graphs (Section 3.14).

In this chapter, we will look at optimization problems from a different point of view—from one that is, in some sense, more fundamental. We will interpret finding the optimum solution of an optimization problem as a search process on the space of legal configurations. (From now on, we will mostly be concerned with legal configurations. Thus, we will omit the word legal unless it is not clear from the context what kind of a configuration we mean.) The configuration space can be represented as a set of geometric points or, alternatively, as a directed graph, and we will choose whatever representation is better suited to our purpose. There exists a large number of search heuristics and strategies for optimization problems; we will survey the ones that are most important for layout design.

As we already mentioned in Chapter 1, the layout problem is a constrained optimization problem. There is a multitude of cost functions that is of interest in layout. The most important ones are the following.

In real-life applications, the provably good layout algorithm presented in Chapter 5 does not perform well enough to be of service. Thus, in practice, the layout problem is solved in a sequence of phases that attack subproblems with exact algorithms or heuristically. These phases are combined with a suitable usage of the circuit hierarchy. The first layout phase usually solves some variant of the placement problem.

The routing phase follows the placement phase. It determines the course of the wires that connect the cells laid out during the placement. The structure of the routing phase depends greatly on the design and fabrication technology. There are two approaches to routing—two-phase and area routing. In area routing, the routing process is carried out in one phase that determines the exact course of the wires. In two-phase routing the routing phase is subdivided into the global (or loose) routing phase—which determines how wires maneuver around and through cells—and the detailed (or local or homotopic) routing phase—which determines the exact course of the wires. We now describe both approaches to routing intuitively.

The detailed-routing phase follows the global-routing phase in the two-phase approach to routing. Recall that the global-routing phase constructs routes that are paths in a routing graph whose edges represent routing regions. For the purpose of detailed routing, these edges have to be expanded to give an accurate graph representation of the respective routing region. The resulting detailedrouting graph looks very much like the routing grids used in area routing with the exception that it is (almost) always planar. However, in contrast to the area-routing problem, the input now contains not only a set of nets, but also a global route for each net. This route specifies how the net maneuvers around the obstacles in the routing region that are defined by the cells of the circuit. The detailed-routing problem is to find detailed routes through the routing graph that comply with the global routes and that obey a certain set of constraints. The constraint set is the detailed-routing model.