Routing (electronic design automation)

Routing (electronic design automation)

Routing is a crucial step in the design of integrated circuits. It builds on a preceding step, called placement, which determines the location of each active element of an IC. Routing is then the process of addingall wires needed to properly connect all of the placed components while obeying all design rules.

The task of all routers is the same. They are given some pre-existing polygons consisting of pins (alsocalled terminals) on cells, and optionally some pre-existing wiring called preroutes. Each of these polygonsare associated with a net, usually by name or number. The primary task of the router is to creategeometries such that all terminals assigned to the same net are connected, no terminals assigned to differentnets are connected, and all design rules are obeyed. A router can fail by not connecting terminalsthat 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 connect the nets, routersmay also be expected to make sure the design meets timing, has no crosstalk problems, meets any metaldensity requirements, does not suffer from antenna effects, and so on. This long list of often conflicting objectives is what makes routing extremely difficult.

Almost every problem associated with routing is known to be intractable. The simplest routing problem, called the Steiner tree problem, of finding the shortest route for one net in one layer with no obstacles and no design rules is NP-hard if all angles are allowed and NP-complete if only horizontal and verticalwires are allowed. Variants of channel routing have also been shown to be NP-complete, as well as routing which reduces crosstalk, number of vias, and so on.Routers therefore seldom attempt to find an optimum result. Instead, almost all routing is based on heuristics which try to find a solution that is good enough.

Design rules sometimes vary considerably from layer to layer. For example, the allowed width and spacing on the lower layers may be four or more times smaller than the allowed widthsand spacings on the upper layers. This introduces many additional complications not faced by routers forother applications such as printed circuit board or Multi-Chip Module design. 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 four main types of routers are:
*Maze router [cite journal | author=C.Y. Lee|title=An algorithm for path connections and its applications| journal=IRE Trans. Electronic Comput.|volume=EC-10| pages-346–365 | year=1961 ]
*Line probe router [cite conference | author=D.W. Hightower | title=doi-inline|10.1145/800260.809014|A solution to line-routing problems on the continuous plane | booktitle=DAC’69: Proceedings of the 6th Annual Conference on Design Automation
publisher=ACM Press| year=1969|pages= 1-24| note=One of the first descriptions of a line probe router
]
*Channel router [cite journal|author=J. Reed, A. Sangiovanni-Vincentelli, and M. Santamauro|title= [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1270117 A new symbolic channel router: YACR2] | journal=IEEE Trans. CAD| pages= 203–219, |year=1985]
*Area routers

How routers work

Many routers execute the following overall algorithm:
* First, determine an approximate course for each net, often by routing on a coarse grid. This step is called "global routing" [cite conference|author=J. Soukop|title= [http://portal.acm.org/citation.cfm?id=811756 Global Router] |booktitle=Proceedings of the 16th Design Automation Conference|year=1979|pages=481-489|location=San Diego, CA|publisher=IEEE Press] , and may optionally include layer assignment. Global routing limits the size and complexity of the following detailed routing steps, which can be done grid square by grid square.

For detailed routing, the most common technique is rip-up and reroute:
*Select a sequence in which the nets are to be routed.
*Route each net in sequence
*If not all nets can be successfully routed, apply any of a variety of "cleanup" methods, in which selected routings are removed, the order of the remaining nets to be routed is changed, and the remaining routings are attempted again.This process repeats until all nets are routed or the program (or user) gives up.

An alternative approach is to treat shorts, design rule violations, obstructions, etc. on a similar footing as excess wire length -- that is, as finite costs to be reduced (at first) rather than as absolutes to be avoided. This multi-pass "iterative-improvement" routing method [cite conference | author=F. Rubin| title= [http://portal.acm.org/citation.cfm?id=811407 An iterative technique for printed wire routing] |booktitle= Proc. 11th Design Automation Workshop|year=1974|pages=308-13] is described by the following algorithm:
*For each of several iterative passes:
*Prescribe or adjust the weight parameters of an "objective function" (having a weight parameter value for each unit of excess wire length, and for each type of violation). E.g., for the first pass, excess wire length may typically be given a high cost, while design violations such as shorts, adjacency, etc. are given a low cost. In later passes, the relative ordering of costs is changed so that violations are high-cost, or may be prohibited absolutely.
*Select (or randomly choose) a sequence in which nets are to be routed during this pass.
*"Rip up" (if previously routed) and reroute each net in turn, so as to minimize the value of the objective function for that net. (Some of the routings will in general have shorts or other design violations.)
*Proceed to the next iterative pass until routing is complete and correct, is not further improved, or some other termination criterion is satisfied.

Most routers assign wiring layers to carry predominantly "x" or "y" directional wiring, though there have been routers which avoid or reduce the need for such assignment [cite journal|author=R. Linsker| title= [http://www.research.ibm.com/journal/rd/285/ibmrd2805N.pdf An iterative-improvement penalty-function-driven wire routing system] |journal=IBM J. Res. Develop|volume=28|issue=5|pages=613–24 |year=1984] . There are advantages and disadvantages to each approach. Restricted directions make power supply design and the control of inter-layer crosstalk easier, but allowing arbitrary routes can reduce the need for vias and decrease the number of required wiring layers.

See also

*Electronic design automation
*Design flow (EDA)
*Integrated circuit design

Further reading

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. A portion of this summary was derived (with permission) from Chapter 8, volume II, "Routing", by Lou Scheffer.

*


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Electronic design automation — (EDA) is the category of tools for designing and producing electronic systems ranging from printed circuit boards (PCBs) to integrated circuits. This is sometimes referred to as ECAD (electronic computer aided design) or just CAD. (Printed… …   Wikipedia

  • Magma Design Automation — Type Public NASDAQ: LAVA Industry Software Programming Founded 199 …   Wikipedia

  • Design flow (EDA) — Design flows are the explicit combination of electronic design automation tools to accomplish the design of an integrated circuit. Moore s law has driven the entire IC implementation RTL to GDSII design flows from one which uses primarily… …   Wikipedia

  • Design closure — is the process by which a VLSI design is modified from its initial description to meet a growing list of design constraints and objectives. Every step in the IC design (such as static timing analysis, placement, routing, and so on) is already… …   Wikipedia

  • Routing (disambiguation) — Routing may refer to:*Route (GIS), in geographic information system *Routing, in computer networking **iproute2, the Linux routing tool *Routing (EDA), an integrated circuit design stage in electronic design automation *Route of administration,… …   Wikipedia

  • Integrated circuit design — Layout view of a simple CMOS Operational Amplifier ( inputs are to the left and the compensation capacitor is to the right ). The metal layers are colored blue and green, the polysilicon is red and vias are crosses. Integrated circuit design, or… …   Wikipedia

  • PCB-Design — Benutzeroberfläche einer Layout Software Platine mit platzierten Bauelementen, sog. „Rattennest“. Die grünen „Gummibänder“ müssen als Leiterzüge verlegt werden …   Deutsch Wikipedia

  • automation — /aw teuh may sheuhn/, n. 1. the technique, method, or system of operating or controlling a process by highly automatic means, as by electronic devices, reducing human intervention to a minimum. 2. a mechanical device, operated electronically,… …   Universalium

  • Corrugated box design — High graphics overlap box: die cut for plastic handle and locking tabs Corrugated box design is the process of matching design factors for corrugated fiberboard boxes with the functional physical, processing and end use requirements. Packaging… …   Wikipedia

  • Placement (EDA) — Placement is an essential step in electronic design automation the portion of the physical design flow that assigns exact locations for various circuitcomponents within the chip’s core area. An inferior placement assignment will not only affect… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”