Routing (electronic design automation): Difference between revisions

Revision as of 03:02, 18 January 2024

Revision as of 09:45, 19 January 2024

Line 8:

The task of all routers is the same. They are given some pre-existing polygons consisting of [[pin (electronics)|pin]]s (also called terminals) on cells, and optionally some pre-existing wiring called preroutes. Each of these polygons are associated with a [[net (electronics)|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 connect the nets, routers may also be expected to make sure the design meets timing, has no [[crosstalk]] problems, meets any metal density requirements, does not suffer from [[antenna effect]]s, 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 [[Computational complexity theory|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 known to be [[NP-complete]], both in the case where all angles are allowed or if routing is restricted to only horizontal and vertical wires.<ref>{{Cite journal |last=Garey |first=M. R. |last2=Johnson |first2=D. S. |year=1977 |title=The Rectilinear Steiner Tree Problem is NP-Complete |url=http://epubs.siam.org/doi/10.1137/0132071 |journal=SIAM Journal on Applied Mathematics |language=en |volume=32 |issue=4 |pages=826–834 |doi=10.1137/0132071 |issn=0036-1399}}</ref>. Variants of [[Channel router|channel routing]] have also been shown to be NP-complete,<ref>{{Cite journal |first=Thomas G. |last=Szymanski |year=1985 |title=Dogleg Channel Routing is NP-Complete |url=https://ieeexplore.ieee.org/document/1270096/ |journal=IEEE transactions on computer-aided design of integrated circuits and systems |volume=4 |issue=1 |pages=31-41 |doi=10.1109/tcad.1985.1270096}}</ref> as well as routing which reduces [[crosstalk]], number of [[via (electronics)|via]]s, and so on.

Routers therefore seldom attempt to find an optimum result. Instead, almost all routing is based on [[heuristic (computer science)|heuristic]]s which try to find a solution that is good enough.