Routing – connecting the dots within chip
Routing is an important step in the design of integrated circuits. It involves generating metal wires to connect the pins of same signal while obeying manufacturing design rules. Before routing is performed on the design, cell placement has to be carried out wherein the cells used in the design are placed. But the connections between the pins of the cells pertaining to same signal need to be made. At the time of placement, there are only logical connections between these pins. The physical connections are made by routing. More generally speaking, routing is to locate a set of wires in routing space so as to connect all the nets in the netlist taking into consideration routing channels’ capacities, wire widths and crossings etc. The objective of routing is to minimize total wire length and number of vias and that each net meets its timing budget. The tools that perform routing are termed as routers. You typically provide them with a placed netlist along with list of timing critical nets. These tools, in turn, provide you with the geometry of all the nets in the design.
VLSI routing is generally considered to be a complex combinatorial problem. Several algorithms have been developed for routing, each having its own pros and cons. The complexity of the routing problem is very high. To make it manageable, most routers usually take a two-step approach of global routing (approximation of routing wires) followed by detailed routing (actual routing of wires).
Global routing: Using a global routing algorithm, the router divides the design into tiles, each tile having a limited number of tracks and generates “loose” route for each connection by finding tile-to-tile paths (As shown in figure (ii)). The routes are not finalized, but the approximate length is known by the distance among the tiles. For example, a tile may have 12 tracks. So, global router will assign 12 tracks to each tile. But, the final assignment of the track is not done during global routing.
Detailed routing: Using detailed routing, the router determines the exact route for each net by searching within tile-to-tile path. It involves providing actual physical path to a net from one connected pin to another (as shown in figure (iii)). Hence, detailed routed wire represents actual resistance, capacitance and length of the net.
What router has to take care: While routing, a router has to pertain to specific constraints like timing budget for each critical net, also called performance constraints. There are other performance constraints too – like the router has to route in such a way as not to cause any crosstalk issues. There should not be any antenna issues. Also, there are a set of design rules like resistance, capacitance, wire/via width/spacing that need to be followed. For instance, technology may be limited by the minimum feature size it can have. Like, in 65 nm technology, the foundry cannot have wire widths less than 65 nm. So, the wires in the design have to be constrained to have wire length greater than 65 nm. Similarly, there are foundry specific constraints for other parameters. Each of these is termed as a Design Rule. Any violation pertaining to these in the design is termed as DRC (Design Rule Check) violation.
Grid based and gridless routing: In grid based routing, a routing grid is superimposed on routing region. Routing takes place along the grid lines. The space between adjacent grid lines is called wire pitch and is equal to sum of minimum width of wires and spacing of wires. On the other hand, any model that does not follow grid based routing is termed as gridless routing model. This model is suitable for wire sizing and perturbation and is more complex and slower than grid based routing. In other words, grid based routing is much easier and simpler in implementation.
We have discussed here routing in VLSI designs. Although many advanced tools are available for achieving the purpose, most of these compromise with the quality of results to save run-time. Almost all tools have the option of routing with more emphasis on meeting timing or congestion. With most of the tools, in present day multi-million gate designs, perfect DRC-free routing (without opens and shorts) is generally not obtained in first pass. You have to route incrementally a few times to achieve the same.
