Routing (electronic design automation): Difference between revisions

Revision as of 23:20, 21 October 2018

Latest revision as of 08:35, 27 August 2025

(34 intermediate revisions by 17 users not shown)

Line 1:

{{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 18 ⟶ 21:

The main types of autorouters are:

* [[Maze router]]<ref name="Byers_1991"/><ref name="Ritchey_1999"/>

** {{anchor|Lee}}[[Lee router]]<ref name="Lee_1961"/><ref name="Byers_1991"/><ref name="Whitaker_2005"/>

** {{anchor|Hadlock}}[[Hadlock router]]<ref name="Hadlock_1977"/>

** [[Flood router]]<ref name="Byers_1991"/>

* [[Line-probe router]]

** {{anchor|Mikami-Tahuchi}}[[Mikami–Tahuchi router]]<ref name="Mikami_1968"/>

** {{anchor|Hightower}}[[Hightower router]]<ref name="Hightower_1969"/><ref name="Whitaker_2005"/><ref name="Minges_1989"/><ref name="Byers_1991"/>

* [[Pattern router]]<ref name="Whitaker_2005"/><ref name="Minges_1989"/>

* [[Channel router]]<ref name="Reed_1985"/><ref name="Minges_1989"/><ref name="Whitaker_2005"/><ref name="Minges_1989Shankar_2014"/>

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

** GridlessRiver router<ref name="Whitaker_2005"/><ref name="Minges_1989Shankar_2014"/>

** Spine and stitch router<ref name="McLellan_2012"/>

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

** [[Area router]]

** Graph theory-theoreticalbased router<ref name="Wu_1992_Graph"/>

*** [[Bloodhound router]]<ref name="CW_1992_Bloodhound"/><ref name="Pfeil_2017_Bloodhound"/><ref name="Redlich_2018_Routers"/> (CADStar[[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 64 ⟶ 69:

* [[Integrated circuit design]]

* [[Place and route]]

* [[Auto polarity (differential pairs)]]

* [[Auto crossover (Ethernet)]]

== References ==

{{reflist|refs=

<ref name="Minges_1989">{{cite book |title=Electronic Materials Handbook: Packaging |author-first=Merrill L. |author-last=Minges |publisher=[[ASM International]] |date=1989 |volume=1 |isbn=978-0-87170-285-12 |url=https://books.google.com/books?id=c2YxCCaM9RIC&pg=PA758 |access-date=2017-09-27 |dead-url=no}}</ref>

<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-28 |lccn=91-72187 |pages=99-10199–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 |id={{ISBN|0-8493-1889-0}} |lccn=2004057106 |page=1266 |chapter-url=http://s1.downloadmienphi.net/file/downloadfile6/192/1385077.pdf |access-date=2017-09-25 |dead-url-status=nolive |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 }}</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 |urldoi=http://ieeexplore10.ieee.org1109/xpls/abs_allTCAD.1985.jsp?arnumber=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>

<ref name="Rubin_1974">{{cite conference |author-first=Frank |author-last=Rubin |url=http://portal.acm.org/citation.cfm?id=811407 |title=An iterative technique for printed wire routing |book-title=Proceedings 11th Design Automation Workshop |date=1974 |pages=308–13}}</ref>

<ref name="Linsker_1984">{{cite journal |author-first=Ralph |author-last=Linsker |title=An iterative-improvement penalty-function-driven wire routing system |journal=[[IBM Journal of Research and Development]] |volume=28 |issue=5 |pages=613–624 |date=1984 |url=http://www.research.ibm.com/journal/rd/285/ibmrd2805N.pdf |doi=10.1147/rd.285.0613}}</ref>

<ref name="Mikami_1968">{{cite conference |author-first1=Koichi |author-last1=Mikami |author-first2=Kinya |author-last2=Tabuchi |title=A computer program for optimal routing of printed circuit connectors |conference=[[IFIPS]] Proceedings |volume=H47 |date=1968 |pages=1745–1478}}</ref>

<ref name="Hadlock_1977">{{cite journal |author-first=Frank O. |author-last=Hadlock |title=A shortest path algorithm for grid graphs |journal=Networks |date=1977-12-01 |volume=7 |number=4 |pages=323-334323–334 |doi=10.1002/net.3230070404 |url=https://www.researchgate.net/publication/227815552_A_Shortest_Path_Algorithm_for_Grid_Graphs227815552}}</ref>

<ref name="SimplifyPCB">{{Cite web | url=http://www.simplifyda.com |title = Simplify Design Automation – the next generation in design methodology}}</ref>

<ref name="Pfeil_2017_Bloodhound">{{cite journal |title=A lifetime designing PCBs: From design to software |author-first=Charles |author-last=Pfeil |date=2017-11-02 |journal=[[EDN Network]] |url=https://www.edn.com/electronics-blogs/all-aboard-/4459033/A-lifetime-designing-PCBs--From-design-to-software |access-date=2018-10-20 |dead-url-status=nolive |archive-url=https://web.archive.org/web/20181021225546/https://www.edn.com/electronics-blogs/all-aboard-/4459033/A-lifetime-designing-PCBs--From-design-to-software |archive-date=2018-10-20<!-- -->21}}</ref>

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

<ref name="Redlich_2018_Routers">{{cite book |title=Schaltungsdesign |author-first=Detlef |author-last=Redlich |chapter=1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung |language=Germande |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 |dead-url= |archive-url=httphttps://archive.istoday/NeYMu20181021231530/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-2021}}</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 book |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=22nd ACM/IEEE Design Automation Conference |chapter=A Method for Gridless Routing of Printed Circuit Boards |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>

<ref name="Wu_1992_Graph">{{cite book |title=Graph Theory Based Routing Algorithms

|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-34}}

== External links ==

* http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf<!-- https://web.archive.org/web/20171001184326/http://users.eecs.northwestern.edu/~haizhou/357/lec6.pdf -->

* http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf<!-- https://web.archive.org/web/20171001185742/http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf -->

{{Digital electronics}}

[[Category:Autorouters|*]]