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.
Also read:
