Routing (electronic design automation): Difference between revisions

Revision as of 23:26, 3 August 2023

Latest revision as of 08:35, 27 August 2025

(11 intermediate revisions by 8 users not shown)

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-hardcomplete]], ifboth in the case where all angles are allowed and [[NP-complete]]or if routing is restricted to only horizontal and vertical wires.<ref>{{Cite arejournal allowed|last1=Garey |first1=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|url-access=subscription }}</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 |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|s2cid=17511882 }}</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.

Line 77:

<ref name="Byers_1991">{{cite book |title=Printed Circuit Board Design with Microcomputers |author-first=T. J. |author-last=Byers |edition=1 |publisher=[[Intertext Publications/Multiscience Press, Inc.]], [[McGraw-Hill Book Company]] |___location=New York, USA |date=1991-08-01 |isbn=978-0-07-009558-8 |lccn=91-72187 |pages=99–101 |url=https://dl.acm.org/citation.cfm?id=114661}}</ref>

<ref name="Whitaker_2005">{{cite book |title=The Electronics Handbook |editor-first1=Jerry C. |editor-last1=Whitaker |editor-first2=Richard C. |editor-last2=Dorf |author-first1=Ravindranath |author-last1=Kollipara |author-first2=Vijai K. |author-last2=Tripathi |author-first3=Jerry E. |author-last3=Sergent |author-first4=Glenn R. |author-last4=Blackwell |author-first5=Donald |author-last5=White |author-first6=Zbigniew J. |author-last6=Staszak |chapter=11.1.3 Packaging Electronic Systems - Design of Printed Wiring Boards |publisher=[[CRC Press]], [[Taylor & Francis Group, LLC]] |date=2005 |edition=2 |isbn=978-0-8493-1889-4 |lccn=2004057106 |page=1266 |chapter-url=http://s1.downloadmienphi.net/file/downloadfile6/192/1385077.pdf |access-date=2017-09-25 |url-status=live |archive-url=https://web.archive.org/web/20170925235855/http://s1.downloadmienphi.net/file/downloadfile6/192/1385077.pdf |archive-date=2017-09-25}}</ref>

<ref name="Lee_1961">{{cite journal |doi=10.1109/TEC.1961.5219222 |author-first=Chester Y. |author-last=Lee |title=An algorithm for path connections and its applications |journal=[[IRE Transactions on Electronic Computers]] |volume=EC-10 |issue=3 |date=September 1961 |pages=346–365|s2cid=40700386 |url=https://semanticscholar.org/paper/6b9cbd70349aac279cb69ffb6017ee6504a729b9 }}</ref>

<ref name="Hightower_1969">{{cite conference |author-first=David W. |author-last=Hightower |title=A solution to line-routing problems on the continuous plane |book-title=DAC'69: Proceedings of the 6th Annual Conference on Design Automation |publisher=[[ACM Press]] |date=1969 |pages=1–24 |doi=10.1145/800260.809014}} (NB. This contains one of the first descriptions of a "line probe router".)</ref>

<ref name="Reed_1985">{{cite journal |author-first1=James B. |author-last1=Reed |author-first2=Alberto |author-last2=Sangiovanni-Vincentelli |author-first3=Mauro |author-last3=Santamauro |title=A new symbolic channel router: YACR2 |journal=[[IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems]] |volume=4 |issue=3 |pages=203–219 |date=1985 |doi=10.1109/TCAD.1985.1270117 |s2cid=17065773 }} [https://www.researchgate.net/publication/3225251_A_New_Symbolic_Channel_Router_YACR2]</ref>

Line 89:

<ref name="CW_1992_Bloodhound">{{cite journal |title=Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen |language=de |journal=[[Computerwoche]] |date=1992-03-13 |url=https://www.computerwoche.de/a/bloodhound-entflechtet-leiterplatten-auf-16-lagen,1133225 |access-date=2018-10-20 |url-status=live |archive-url=https://archive.today/20181021231138/https://www.computerwoche.de/a/bloodhound-entflechtet-leiterplatten-auf-16-lagen,1133225 |archive-date=2018-10-21}}</ref>

<ref name="Redlich_2018_Routers">{{cite book |title=Schaltungsdesign |author-first=Detlef |author-last=Redlich |chapter=1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung |language=de |publisher=[[Ernst-Abbe-Hochschule Jena]] (EAH) |chapter-url=http://web.eah-jena.de/fhj/etit/fb/homepage/home-redlich/lehre/design/Documents/Rechnergest_LP_Entwurf_Einf%C3%BChrung.pdf |access-date=2018-10-20 |archive-url=https://archive.today/20181021231530/http://web.eah-jena.de/fhj/etit/fb/homepage/home-redlich/lehre/design/Documents/Rechnergest_LP_Entwurf_Einf%C3%BChrung.pdf |archive-date=2018-10-21}}</ref>

<ref name="Webb_2012">{{cite web |title=A Tribute to Alan Finch, the Father of Gridless Autorouting |author-first=Darrell |author-last=Webb |work=Zuken Blog |date=2012-12-20 |url=https://blog.zuken.com/a-tribute-to-alan-finch-the-father-of-gridless-autorouting/ |access-date=2018-10-22 |url-status=live |archive-url=https://archive.today/20181022034218/https://blog.zuken.com/a-tribute-to-alan-finch-the-father-of-gridless-autorouting/ |archive-date=2018-10-22}}</ref>

<ref name="Finch_1985">{{cite conferencebook |author-first1=Alan C. |author-last1=Finch |author-first2=Ken J. |author-last2=Mackenzie |author-first3=G. J. |author-last3=Balsdon |author-first4=G. |author-last4=Symonds |title=A22nd MethodACM/IEEE for Gridless Routing of Printed Circuit Boards |journal=Design Automation Conference, 2009. Dac '09. 46th ACM/IEEE |conferencechapter=22ndA ACM/IEEEMethod Designfor AutomationGridless Conference,Routing Lasof Vegas,Printed Nevada,Circuit USABoards |date=1985-06-23<!-- /26 --> |publisher=[[Racal-Redac Ltd.]] |___location=Newtown, Tewkesbury, Gloucestershire, UK |issn=0738-100X |isbn=0-8186-0635-5 |pages=509–515 |doi=10.1109/DAC.1985.1585990 |url=https://www.cs.york.ac.uk/rts/docs/DAC-1964-2006/PAPERS/1985/DAC85_509.PDF |access-date=2018-10-22 |url-status=live |archive-url=https://web.archive.org/web/20181022030533/https://www.cs.york.ac.uk/rts/docs/DAC-1964-2006/PAPERS/1985/DAC85_509.PDF |archive-date=2018-10-22}}</ref>

<ref name="Ritchey_1999">{{cite journal |title=PCB routers and routing methods |author-first=Lee W. |author-last=Ritchey |publisher=Speeding Edge |date=December 1999 |issue=February 1999 |journal=PC Design Magazine |url=http://www.speedingedge.com/PDF-Files/pcbrouters.pdf |access-date=2018-10-22 |url-status=live |archive-url=https://web.archive.org/web/20181022033826/http://www.speedingedge.com/PDF-Files/pcbrouters.pdf |archive-date=2018-10-22}}</ref>

<ref name="Shankar_2014">{{cite book |title=VLSI and Computer Architecture |author-first1=Ravi |author-last1=Shankar |author-first2=Eduardo B. |author-last2=Fernandez |publisher=[[Academic Press]] |date=2014-01-12 |volume=20 |series=VLSI Electronics Microstructure Science |editor-first=Norman G. |editor-last=Einspruch |isbn=978-1-48321784-0 |url=https://books.google.com/books?id=jDGoBQAAQBAJ&pg=PA232 |access-date=2018-10-22 }}</ref>