← Back to results

to content Main menu Main menu move to sidebar hide Navigation Main page Contents Current events Random article About Wikipedia Contact us Contribute Help Learn to edit Community portal Recent changes Upload file Special pages Search Search Appearance Donate Create account Log in Personal tools Donate Create account Log in Contents move to sidebar hide (Top) 1 Complexity of routing 2 Overall routing strategy 3 Main types of autorouters 4 How routers work 5 See also 6 References 7 Further reading 8 External links Toggle the table of contents Routing (electronic design automation) 6 languages Deutsch Italiano Русский Українська 吴语 中文 Edit links Article Talk English Read Edit View history Tools Tools move to sidebar hide Actions Read Edit View history General What links here Related changes Upload file Permanent link Page information Cite this page Get shortened URL Print/export Download as PDF Printable version In other projects Wikidata item Appearance move to sidebar hide From Wikipedia, the free encyclopedia Stage of electronic circuit design This article is about designing integrated circuits, as part of electronic design automation . For other kinds of routing, see routing (disambiguation) . In electronic design , wire routing , commonly called simply routing , is a step in the design of printed circuit boards (PCBs) and integrated circuits (ICs). It builds on a preceding step, called 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 pins (also called terminals) on cells, some obstacles where wires cannot be routed, and optionally some pre-existing wiring called preroutes. Each of the pins is associated with a 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 connecting 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 effects , and so on. This long list of often conflicting objectives is what makes routing extremely difficult. Complexity of routing [ edit ] Almost every problem associated with routing is known to be 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. [ 1 ] Variants of channel routing have also been shown to be NP-complete, [ 2 ] as well as routing which reduces crosstalk , number of vias , and so on. Even before routing problems were proved NP-complete, the difficulty of finding optimal solutions was apparent. Therefore almost all algorithms are based on heuristics , which do not try for an optimum, but instead a solution that is "good enough". [ 3 ] Design rules sometimes vary considerably from layer to layer. On integrated circuits with multiple metal layers, for example, the allowed width and spacing on the lower layers may be four or more times smaller than the allowed widths and spacings on the upper layers. This introduces many additional complications not faced by routers for other applications such as printed circuit board or multi-chip module design. Particular difficulties ensue if the rules are not simple multiples of each other, and when vias must traverse between layers with different rules. 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. Overall routing strategy [ edit ] 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. Modern PCB design software also typically provides "autorouters" that route all remaining unrouted connections without human intervention. Modern integrated circuits typically use fully automatic routing, as there can be far too many nets to route by hand. If the automatic routing does not yield a fully routed solution, a typical fix is to change the placement to allow more room for the routes, rather than try to complete the missing routes manually. Main types of autorouters [ edit ] Maze router [ 4 ] [ 5 ] Lee router [ 6 ] [ 4 ] [ 7 ] The A* search algorithm is commonly used in maze and Lee routers. Hadlock router [ 8 ] Flood router [ 4 ] Line-probe router Mikami–Tahuchi router [ 9 ] Hightower router [ 10 ] [ 7 ] [ 11 ] [ 4 ] Pattern router [ 7 ] [ 11 ] Channel router [ 12 ] [ 11 ] [ 7 ] [ 13 ] Switchbox router [ 13 ] River router [ 13 ] Spine and stitch router [ 14 ] Gridless router [ 15 ] [ 11 ] [ 7 ] [ 16 ] Area router Graph theory-based router [ 17 ] Bloodhound router [ 18 ] [ 19 ] [ 20 ] ( CADSTAR by Racal-Redac / Zuken ) Specctra [ 20 ] (aka Allegro PCB Router ) (gridless since version 10) Topological router FreeStyle Router (aka SpeedWay , an MS-DOS -based autorouter for P-CAD ) TopoR (a Windows -based autorouter, also used in Eremex 's Delta Design) Toporouter (Anthony Blake's open-source router in PCB of the gEDA suite ) TopRouter (the topological pre-router in CadSoft / Autodesk 's EAGLE 7.0 and higher) SimplifyPCB (a topological router with a focus on bundle routing with hand-routing results) [ 21 ] How routers work [ edit ] Many routers execute the following overall algorithm: First, determine an approximate course for each net, often by routing on a coarse grid. This step is called global routing , [ 22 ] 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 : [ 4 ] Select a sequence in which the nets are to be routed. Route each net in sequence If not all nets can be successfully routed, apply any of a variety of "cleanup" methods, in which selected routings are removed, the order of the remaining nets to be routed is changed, and the remaining routings are attempted again. This process repeats until all nets are routed or the program (or user) gives up. An alternative approach is to treat shorts, design rule violations, obstructions, etc. on a similar footing as excess wire length—that is, as finite costs to be reduced (at first) rather than as absolutes to be avoided. This multi-pass "iterative-improvement" routing method [ 23 ] is described by the following algorithm: For each of several iterative passes: Prescribe or adjust the weight parameters of an "objective function" (having a weight parameter value for each unit of excess wire length, and for each type of violation). E.g., for the first pass, excess wire length may typically be given a high cost, while design violations such as shorts, adjacency, etc. are given a low cost. In later passes, the relative ordering of costs is changed so that violations are high-cost, or may be prohibited absolutely. Select (or randomly choose) a sequence in which nets are to be routed during this pass. "Rip up" (if previously routed) and reroute each net in turn, so as to minimize the value of the objective function for that net. (Some of the routings will in general have shorts or other design violations.) Proceed to the next iterative pass until routing is complete and correct, is not further improved, or some other termination criterion is satisfied. Most routers assign wiring layers to carry predominantly "x" or "y" directional wiring, though there have been routers which avoid or reduce the need for such assignment. [ 24 ] There are advantages and disadvantages to each approach. Restricted directions make power supply design and the control of inter-layer crosstalk easier, but allowing arbitrary routes can reduce the need for vias and decrease the number of required wiring layers. See also [ edit ] Electronic design automation Design flow (EDA) Integrated circuit design Place and route Auto polarity (differential pairs) Auto crossover (Ethernet) References [ edit ] ^ Garey, M. R.; Johnson, D. S. (1977). "The Rectilinear Steiner Tree Problem is NP-Complete" . SIAM Journal on Applied Mathematics . 32 (4): 826– 834. doi : 10.1137/0132071 . ISSN   0036-1399 . ^ Szymanski, Thomas G. (1985). "Dogleg Channel Routing is NP-Complete". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (1): 31– 41. Bibcode : 1985ITCAD...4...31S . doi : 10.1109/tcad.1985.1270096 . S2CID   17511882 . ^ Stevens, James Edward, Jr. (1972). Fast heuristic techniques for placing and wiring printed circuit boards (Ph.D. thesis). Urbana : University of Illinois at Urbana-Champaign . {{ cite thesis }} : CS1 maint: multiple names: authors list ( link ) ^ a b c d e Byers, T. J. (1991-08-01). Printed Circuit Board Design with Microcomputers (1 ed.). New York, USA: Intertext Publications/Multiscience Press, Inc. , McGraw-Hill Book Company . pp.  99– 101. ISBN   978-0-07-009558-8 . LCCN   91-72187 . ^ Ritchey, Lee W. (December 1999). "PCB routers and routing methods" (PDF) . PC Design Magazine (February 1999). Speeding Edge. Archived (PDF) from the original on 2018-10-22 . Retrieved 2018-10-22 . ^ Lee, Chester Y. (September 1961). "An algorithm for path connections and its applications". IRE Transactions on Electronic Computers . EC-10 (3): 346– 365. Bibcode : 1961IRTEC..10..346L . doi : 10.1109/TEC.1961.5219222 . S2CID   40700386 . ^ a b c d e Kollipara, Ravindranath; Tripathi, Vijai K.; Sergent, Jerry E.; Blackwell, Glenn R.; White, Donald; Staszak, Zbigniew J. (2005). "11.1.3 Packaging Electronic Systems - Design of Printed Wiring Boards" (PDF) . In Whitaker, Jerry C.; Dorf, Richard C. (eds.). The Electronics Handbook (2 ed.). CRC Press , Taylor & Francis Group, LLC . p. 1266. ISBN   978-0-8493-1889-4 . LCCN   2004057106 . Archived (PDF) from the original on 2017-09-25 . Retrieved 2017-09-25 . ^ Hadlock, Frank O. (1977-12-01). "A shortest path algorithm for grid graphs" . Networks . 7 (4): 323– 334. doi : 10.1002/net.3230070404 . ^ Mikami, Koichi; Tabuchi, Kinya (1968). A computer program for optimal routing of printed circuit connectors . IFIPS Proceedings. Vol. H47. pp.  1745– 1478. ^ Hightower, David W. (1969). "A solution to line-routing problems on the continuous plane". DAC'69: Proceedings of the 6th Annual Conference on Design Automation . ACM Press . pp.  1– 24. doi : 10.1145/800260.809014 . (NB. This contains one of the first descriptions of a "line probe router".) ^ a b c d Minges, Merrill L. (1989). Electronic Materials Handbook: Packaging . Vol. 1. ASM International . ISBN   978-0-87170-285-2 . Retrieved 2017-09-27 . ^ Reed, James B.; Sangiovanni-Vincentelli, Alberto; Santamauro, Mauro (1985). "A new symbolic channel router: YACR2". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 (3): 203– 219. Bibcode : 1985ITCAD...4..208R . doi : 10.1109/TCAD.1985.1270117 . S2CID   17065773 . [1] ^ a b c Shankar, Ravi; Fernandez, Eduardo B. (2014-01-12). Einspruch, Norman G. (ed.). VLSI and Computer Architecture . VLSI Electronics Microstructure Science. Vol. 20. Academic Press . ISBN   978-1-48321784-0 . Retrieved 2018-10-22 . ^ McLellan, Paul (2012-04-23). "Channel Routing Memories" . Archived from the original on 2021-05-18 . Retrieved 2022-01-01 . ^ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, G. J.; Symonds, G. (1985-06-23). "A Method for Gridless Routing of Printed Circuit Boards". 22nd ACM/IEEE Design Automation Conference (PDF) . Newtown, Tewkesbury, Gloucestershire, UK: Racal-Redac Ltd. pp.  509– 515. doi : 10.1109/DAC.1985.1585990 . ISBN   0-8186-0635-5 . ISSN   0738-100X . Archived (PDF) from the original on 2018-10-22 . Retrieved 2018-10-22 . ^ Webb, Darrell (2012-12-20). "A Tribute to Alan Finch, the Father of Gridless Autorouting" . Zuken Blog . Retrieved 2018-10-22 . {{ cite web }} : CS1 maint: deprecated archival service ( link ) ^ Wu, Bo (April 1992). Graph Theory Based Routing Algorithms (PDF) (Thesis). Western Michigan University . S2CID   3357923 . Archived from the original (PDF) on 2018-10-22 . Retrieved 2018-10-22 . ^ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen" . Computerwoche (in German). 1992-03-13 . Retrieved 2018-10-20 . {{ cite journal }} : CS1 maint: deprecated archival service ( link ) ^ Pfeil, Charles (2017-11-02). "A lifetime designing PCBs: From design to software" . EDN Network . Archived from the original on 2018-10-21 . Retrieved 2018-10-20 . ^ a b Redlich, Detlef. "1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung" (PDF) . Schaltungsdesign (in German). Ernst-Abbe-Hochschule Jena (EAH) . Retrieved 2018-10-20 . {{ cite book }} : CS1 maint: deprecated archival service ( link ) ^ "Simplify Design Automation – the next generation in design methodology" . ^ Soukup, Jirí (1979). "Global Router" . Proceedings of the 16th Design Automation Conference . San Diego, CA, USA: IEEE Press . pp.  481– 489. ^ Rubin, Frank (1974). "An iterative technique for printed wire routing" . Proceedings 11th Design Automation Workshop . pp.  308– 13. ^ Linsker, Ralph (1984). "An iterative-improvement penalty-function-driven wire routing system" (PDF) . IBM Journal of Research and Development . 28 (5): 613– 624. doi : 10.1147/rd.285.0613 . Further reading [ edit ] Scheffer, Louis K.; Lavagno, Luciano; Martin, Grant (2006). "Chapter 8: Routing ". Electronic Design Automation For Integrated Circuits Handbook . Vol. II. Boca Raton, FL, USA: CRC Press / Taylor & Francis . ISBN   978-0-8493-3096-4 . External links [ edit ] http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf v t e Digital electronics Components Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU) Theory Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent Design Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine Applications Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature Design issues Metastability Runt pulse Retrieved from " https://en.wikipedia.org/w/index.php?title=Routing_(electronic_design_automation)&oldid=1348006605 " Category : Autorouters Hidden categories: CS1 maint: multiple names: authors list CS1: long volume value CS1 maint: deprecated archival service CS1 German-language sources (de) Articles with short description Short description matches Wikidata Use dmy dates from January 2022 Use list-defined references from January 2022 Use American English from April 2019 All Wikipedia articles written in American English This page was last edited on 10 April 2026, at 03:19  (UTC) . Text is available under the Creative Commons Attribution-ShareAlike 4.0 License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy . Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. , a non-profit organization. Privacy policy About Wikipedia Disclaimers Contact Wikipedia Legal & safety contacts Code of Conduct Developers Statistics Cookie statement Mobile view Search Search Toggle the table of contents Routing (electronic design automation) 6 languages Add topic