Compaction

Except for the gridless routing models, detailed routing still occurs in a discrete graph setting. Its output is an embedding of a graph representing the circuit into a mostly very regular routing graph. This representation of a layout is also called symbolic, because transistors and wires are represented by symbols, such as vertices and edges labeled in appropriate ways. Labels can, for instance, determine the type and strength of a transistor, or the width of a wire. These labels can be attached to the circuit description in a variety of stages of the circuit or layout design process. One possibility is to attach the labels to the netlist before the layout design is started. In this case, the appropriate labels are derived from a simulation or timing analysis of the netlist. Another possibility is to run a performance-optimization program after the detailedrouting phase. Such optimizers are described in [179, 310]. Attaching labels after the detailed-routing phase allows for incorporating layout aspects into the performance optimization of the circuit. For instance, the delay of propagating a wire depends on the length of the wire. If the layout is not known at the time that the labels are computed, some nominal value has to be used here. This approach is viable only if the dependence of the delay on the wire length is a second-order phenomenon. As the complexity of chips increases, this is no longer the case, and performance optimizers that make use of layout data become increasingly important. We do not discuss this issue further here, but refer the reader to the literature [179, 310, 385].