Routing (electronic design automation): Difference between revisions

Revision as of 18:28, 13 November 2021

Latest revision as of 08:35, 27 August 2025

(17 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|stageStage of electronic circuit design}}

{{Use American English|date = April 2019}}

{{Short description|stage of electronic circuit design}}

{{About|designing integrated circuits, as part of [[electronic design automation]]|other kinds of routing|routing (disambiguation)}}

{{Use dmy dates|date=January 2022|cs1-dates=y}}

{{Use list-defined references|date=January 2022}}

{{Use American English|date = April 2019}}

In [[electronic design]], '''wire routing''', commonly called simply '''routing''', is a step in the design of [[printed circuit board]]s (PCBs) and [[integrated circuit]]s (ICs). It builds on a preceding step, called [[placement (electronic design automation)|placement]], which determines the ___location of each active element of an IC or component on a PCB. After placement, the routing step adds wires needed to properly connect the placed components while obeying all [[design rules]] for the IC. Together, the placement and routing steps of IC design are known as [[place and route]].

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 31 ⟶ 32:

** [[Switchbox router]]<ref name="Shankar_2014"/>

** River router<ref name="Shankar_2014"/>

** Spine and stitch router<ref>{{Cite web | urlname=https://www.semiwiki.com/forum/content/1208-channel-routing-memories.html |title = Channel Routing Memories}}<"McLellan_2012"/ref>

* Gridless router<ref name="Finch_1985"/><ref name="Minges_1989"/><ref name="Whitaker_2005"/><ref name="Webb_2012"/>

** [[Area router]]

Line 37 ⟶ 38:

*** [[Bloodhound router]]<ref name="CW_1992_Bloodhound"/><ref name="Pfeil_2017_Bloodhound"/><ref name="Redlich_2018_Routers"/> ([[CADSTAR]] by [[Racal-Redac]] / [[Zuken]])

*** [[Specctra]]<ref name="Redlich_2018_Routers"/> (aka [[Allegro PCB Router]]) (gridless since version 10)

** {{anchor|Topological router|AnyAngle}}Topological router

*** [[FreeStyle Router]] (aka ''SpeedWay'', a [[DOS]]-based autorouter for [[P-CAD]])<!-- since 1997 (possibly 1991 or 1996) -->

*** [[TopoR]] (a [[Microsoft Windows|Windows]]-based autorouter, also used in [[Eremex]]'s Delta Design)<!-- since 2003 (possibly 2001 or 2002) -->

Line 68 ⟶ 69:

* [[Integrated circuit design]]

* [[Place and route]]

* [[Auto polarity (differential pairs)]]

* [[Auto crossover (Ethernet)]]

== References ==

Line 74 ⟶ 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={{doi-inline|10.1145/800260.809014|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>

<ref name="Soukup_1979">{{cite conference |author-first=Jirí |author-last=Soukup |title=Global Router |url=http://portal.acm.org/citation.cfm?id=811756 |book-title=Proceedings of the 16th Design Automation Conference |date=1979 |pages=481–489 |___location=San Diego, CA, USA |publisher=[[IEEE Press]]}}</ref>

Line 86 ⟶ 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>

Line 93 ⟶ 96:

|author-first=Bo |author-last=Wu |publisher=[[Western Michigan University]] |type=Thesis |date=April 1992 |s2cid=3357923 |url=https://pdfs.semanticscholar.org/d998/0976dc33c9bfe8b8a049ad8da696526872f7.pdf |access-date=2018-10-22 |url-status=dead |archive-url=https://web.archive.org/web/20181022112048/https://pdfs.semanticscholar.org/d998/0976dc33c9bfe8b8a049ad8da696526872f7.pdf

|archive-date=2018-10-22}}</ref>

<ref name="McLellan_2012">{{cite web |title=Channel Routing Memories |author-first=Paul |author-last=McLellan |date=2012-04-23 |url=https://www.semiwiki.com/forum/content/1208-channel-routing-memories.html |access-date=2022-01-01 |url-status=live |archive-url=https://web.archive.org/web/20210518114742/https://semiwiki.com/uncategorized/1208-channel-routing-memories/ |archive-date=2021-05-18}}</ref>

}}

== Further reading ==

* {{Citecite book |title=Electronic Design Automation For Integrated Circuits Handbook |author-last1=Scheffer |author-first1=Louis K. |author-last2=Lavagno |author-first2=Luciano |author-last3=Martin |author-first3=Grant |date=2006 |chapter=Chapter 8: ''Routing'' |volume=II |publisher=[[CRC Press]] / [[Taylor & Francis]] |___location=Boca Raton, FL, USA |isbn=978-0-8493-3096-4}}

== External links ==

Line 103 ⟶ 107:

{{Digital electronics}}

[[Category:Autorouters|*]]