692 CHAPTER 12 Global and detailed routing wire pitch via spacing wire width wire spacing via width FIGURE 12.5 An example of design rules. Typical rules define wire width, wire spacing, wire pitch, via width, and via spacing on each layer. often related with the manufacturing details during fabrication. To improve the manufacturing yield, connections of nets have to follow the rules provided by foundries. For example, in the 65-nm technology, the physical limitations of an optical lithography system would impose a constraint on a wire such that its width cannot be smaller than 65 nm. Figure 12.5 illustrates a typical set of design rules. It defines the minimum widths of wires and vias, the minimum wire-to-wire spacing, and the minimum via-to-via spacing of a layer. The distance between two wires or routing tracks of the grid-based model is often called wire pitch. Other design rules of the manufacturing process, such as resistance and capacitance of each layer, are also included. The objective of the performance constraint is to make the connections meet the performance specifications provided by chip designers. For example, the timing constraint is often the most important performance constraint for high-speed designs. The speed of a chip is limited by its critical nets, which have smaller timing budgets (or timing slacks) than others. To meet the perfor- mance constraint, it is desirable to carefully route these critical nets by proper routing topologies. 12.3 GENERAL-PURPOSE ROUTING In Section 12.2.1, we modeled the routing resources by the global- and detailed- routing graphs. For global and detailed routing, we can perform a graph-search technique on these routing models. In the following, we introduce three popu- lar graph-searching techniques, the maze, line-search, and A*-search routing