688 CHAPTER 12 Global and detailed routing 12.1 INTRODUCTION Routing is an important step in the design of integrated circuits (ICs). It generates wiring to interconnect pins of the same signal, while obeying the manufacturing design rules. As IC process advances to nanometer technology, foundries may fab- ricate billions of transistors in a single chip, and the number of transistors per die will still grow drastically in the near future. This increasing complexity imposes sub- stantial challenges for physical design, especially for routing. Research in VLSI routing has received much attention in the literature. Rout- ing is typically a very complex combinatorial problem. To make it manageable, the routing problem is usually solved by use of a two-stage approach of global routing followed by detailed routing. Global routing first partitions the rout- ing region into tiles and decides tile-to-tile paths for all nets while attempting to optimize some given objective function (e.g., total wirelength and circuit timing). Then, guided by the paths obtained in global routing, detailed routing assigns actual tracks and vias for nets. Figure 12.1 illustrates the process of global routing and detailed routing. After placement, we have a placed layout shown in Figure 12.1a, which contains the information about the exact locations of blocks, pins of blocks, and I/O pads at chip boundaries. We are also provided with a netlist that describes a list of con- nections by indicating which pins or pads should be electrically connected to form a set of nets. Figure 12.1b illustrates some global-routing paths. It first divides the routing region into tiles and then generates a "loose" route for each connection by finding the tile-to-tile paths to connect pins and/or pads. Figure 12.1c shows a result of detailed routing, which determines the exact route for each net by searching within the tile-to-tile path. Here, the exact route means a path specified by the actual geometric layout such as metal wires and vias. In the following we formally give the problem definition of the routing problem and describe the routing model and constraints. (a) (b) (c) FIGURE 12.1 Routing problem: (a) A given placement result with fixed locations of blocks and pins. (b) Global routing. (c) Detailed routing.