Routing (electronic design automation): Difference between revisions

Revision as of 22:16, 27 October 2017

Latest revision as of 08:35, 27 August 2025

(46 intermediate revisions by 21 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 [[Placementplacement (EDAelectronic 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 [[Pinpin (electronics)|pinspin]]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.

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 (EDA)|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.

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.

The task of all routers is the same. They are given some pre-existing polygons consisting of [[Pin (electronics)|pins]] (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 [[NP-hard]] if all angles are allowed and [[NP-complete]] if only horizontal and vertical wires are allowed. Variants of [[Channel router|channel routing]] have also been shown to be NP-complete, 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 11 ⟶ 14:

== {{anchor|Manual router|Interactive router|Autorouter|Push-and-shove router}}Types of routers ==

[[File:PCB design and realisation smt and through hole.png|thumb|A PCB as a design on a computer (left) and realized as a board assembly populated with components (right). The board is double sided, with through-hole plating, green solder resist and a white legend. Both surface mount and through-hole components have been used.]]

The earliest types of EDA routers were "manual routers"—the drafter clicked a mouse on the endpoint of each line segment of each net.

Modern PCB design software typically provides "interactive routers"—the drafter selects a pad and clicks a few places to give the EDA tool an idea of where to go, and the EDA tool tries to place wires as close to that path as possible without violating [[design rule checking]] (DRC). Some more advanced interactive routers have "push and shove" (aka "shove-aside" or "automoving") features in an interactive router; the EDA tool pushes other nets out of the way, if possible, in order to place a new wire where the drafter wants it and still avoid violating DRC.

Line 17 ⟶ 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-TahuchiMikami–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-based router<ref name="Wu_1992_Graph"/>

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

*** [[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) -->

*** [[Toporouter]] (Anthony Blake's open-source router in [[PCB (software)|PCB]] of the [[gEDA suite]])<!-- since 2008 -->

*** [[TopRouter]] (the topological pre-router in [[CadSoft Computer|CadSoft]]/[[Autodesk]]'s [[EAGLE 7.0]] and higher)<!-- since 2014 -->

*** SimplifyPCB (a topological router with a focus on bundle routing with hand-routing results)<ref name="SimplifyPCB"/>

== {{anchor|Ripup-router}}How routers work ==

Line 39 ⟶ 49:

* First, determine an approximate course for each net, often by routing on a coarse grid. This step is called ''global routing'',<ref name="Soukup_1979"/> 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''' aka '''rip-up and retry''':<ref name="Byers_1991"/>

*Select a sequence in which the nets are to be routed.

*Route each net in sequence

Line 58 ⟶ 68:

* [[Design flow (EDA)]]

* [[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-10099–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 |url-status=live |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-21}}</ref>

<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 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|*]]