Routing (electronic design automation)

Routing is a crucial step in the design of ICs. The placement step determines the location of each active element of an IC. Routing is then the process of creating all the wires needed to properly connect all the placed components, while obeying the design rules of the process.

Routing is the blue-collar work of IC design. There are no conceptual difficulties and very little use of higher mathematics. Almost everything is based on a few basic techniques which have been known for a long time — the papers describing these were published before most readers of this work were born. The success of a router is determined by hard work, heuristics, and implementation — reducing memory usage, increasing speed, and dealing with a multitude of obscure but necessary design rules. Perhaps as a result, almost all state-of-the-art routers are built in industry, and relatively little is published about them. In contrast, the placement problem can be attacked using a wide variety of techniques, some quite sophisticated, and many academic groups develop their own placers. A placement contest at ISPD in 2005, using state-of-the-art examples, drew nine contestants from academia. A similar contest for routing would probably not find even one academic router that can solve a state-of-the-art routing problem.

Almost every problem associated with routing is known to be intractable. The simplest routing problem, finding the shortest route for one net in one layer with no obstacles and no design rules, is called the Steiner tree problem. It is NP-hard if all angles are allowed and NP-complete using horizontal and vertical wires. Variants of channel routing are shown to be NP-complete, as is Routing considering crosstalk, via minimization, and so on. Routers therefore, seldom attempt to find an optimum result. Instead, almost all routing is based on heuristics trying to find a solution that is good enough.

A specific concern for IC routers is that the design rules vary considerably from layer to layer. The allowed width and spacing on the lower layers may be four or more times smaller than the legal widths and spacings on the upper layers. This introduces many additional complications not faced by routers for other applications such as PC boards or MCMs. Particular difficulties ensue if the rules are not simple multiples of each other, and when vias must traverse between layers with different rules.

Types of Routers

The task of all routers is the same. They are given some pre-existing polygons consisting of pins (also called terminals) on cells, and (optionally) some pre-existing wiring called preroutes. Each of these polygons is associated with a net, usually by name or number. The primary task of the router is to create geometries such that all terminals assigned to the same net are connected, no terminals assigned to different nets are connected, and all design rules are obeyed. A router can fail by not connecting terminals that should be connected (an open), by mistakenly connecting two terminals that should not be connected (a short), or by creating a design rule violation. In addition to correctly connecting the nets, routers may also be expected to make sure the design meets timing, has no crosstalk problems, meets any metal density requirements, and so on. This long list of often conflicting objectives is what makes routing difficult.

References

Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0849330963 Old fashioned (paper) survey of the field.