Routing (EDA)
From Wikipedia, the free encyclopedia
Routing is a crucial step in the design of integrated circuits. The preceding 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. From the user point of view, place and route are often lumped together as necessary physical operations. From an algorithm point of view, placement and routing are very different.
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.
[edit] 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.
The four main types of routers are:
- Maze routers.
- Line probe routers
- Channel routers
- Area routers
[edit] See also
In addition, there are hundreds of articles on various technical details of this subject (Routing (EDA)). These are normally presented at conferences such as the Design Automation Conference (DAC) and the International Conference on Computer-Aided Design (ICCAD), along with many smaller conferences. The main journal in the field is IEEE Transactions on Computer-Aided Design. Most of these journals and conference proceedings are published by the IEEE or the ACM. You can search the IEEE on-line library and the ACM digital library and view the abstracts for free. Downloading full text requires purchase, society membership, or a site license; many schools and companies have such licenses already.
[edit] References
- Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0-8493-3096-3 A survey of the field of electronic design automation. This summary was derived (with permission) from Chapter 8, volume II, Routing, by Lou Scheffer.
- C.Y. Lee, An algorithm for path connections and its applications, IRE Trans. Electronic Comput., EC-10, 346–365, 1961. One of the first descriptions of a maze router.
- D.W. Hightower, A solution to line-routing problems on the continuous plane, DAC’69: Proceedings of the 6th Annual Conference on Design Automation, ACM Press, 1969, pp. 1-24. One of the first descriptions of a line probe router.
- J. Reed, A. Sangiovanni-Vincentelli, and M. Santamauro, A new symbolic channel router: YACR2, IEEE Trans. CAD, pp. 203–219, 1985. Probably the most widely known channel router.
