Routing (electronic design automation)

Last updated

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.

Contents

The task of all routers is the same. They are given some pre-existing polygons consisting of pins (also called terminals) on cells, and optionally some pre-existing wiring called preroutes. Each of these polygons are 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 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 effects, 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 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. Routers therefore seldom attempt to find an optimum result. Instead, almost all routing is based on heuristics which try to find a solution that is good enough.

Design rules sometimes vary considerably from layer to layer. 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.

Types of routers

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. PCB design and realisation smt and through hole.png
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. Modern PCB design software also typically provides "autorouters" that route all remaining unrouted connections without human intervention.

The main types of autorouters are:

How routers work

Many routers execute the following overall algorithm:

For detailed routing, the most common technique is rip-up and reroute aka rip-up and retry: [3]

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 [22] is described by the following algorithm:

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. [23] 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

Related Research Articles

<span class="mw-page-title-main">Printed circuit board</span> Board to support and connect electronic components

A printed circuit board (PCB), also called printed wiring board (PWB), is a medium used to connect or "wire" components to one another in a circuit. It takes the form of a laminated sandwich structure of conductive and insulating layers: each of the conductive layers is designed with a pattern of traces, planes and other features etched from one or more sheet layers of copper laminated onto and/or between sheet layers of a non-conductive substrate. Electrical components may be fixed to conductive pads on the outer layers in the shape designed to accept the component's terminals, generally by means of soldering, to both electrically connect and mechanically fasten them to it. Another manufacturing process adds vias, plated-through holes that allow interconnections between layers.

Electronic design automation (EDA), also referred to as electronic computer-aided design (ECAD), is a category of software tools for designing electronic systems such as integrated circuits and printed circuit boards. The tools work together in a design flow that chip designers use to design and analyze entire semiconductor chips. Since a modern semiconductor chip can have billions of components, EDA tools are essential for their design; this article in particular describes EDA specifically with respect to integrated circuits (ICs).

<span class="mw-page-title-main">Circuit diagram</span> Graphical representation of an electrical circuit

A circuit diagram is a graphical representation of an electrical circuit. A pictorial circuit diagram uses simple images of components, while a schematic diagram shows the components and interconnections of the circuit using standardized symbolic representations. The presentation of the interconnections between circuit components in the schematic diagram does not necessarily correspond to the physical arrangements in the finished device.

<span class="mw-page-title-main">Gerber format</span> Standard file format used for designing printed circuit boards

The Gerber format is an open, ASCII, vector format for printed circuit board (PCB) designs. It is the de facto standard used by PCB industry software to describe the printed circuit board images: copper layers, solder mask, legend, drill data, etc. The standard file extension is .GBR or .gbr though other extensions like .GB, .geb or .gerber are also used.

Place and route is a stage in the design of printed circuit boards, integrated circuits, and field-programmable gate arrays. As implied by the name, it is composed of two steps, placement and routing. The first step, placement, involves deciding where to place all electronic components, circuitry, and logic elements in a generally limited amount of space. This is followed by routing, which decides the exact design of all the wires needed to connect the placed components. This step must implement all the desired connections while following the rules and limitations of the manufacturing process.

Placement is an essential step in electronic design automation — the portion of the physical design flow that assigns exact locations for various circuit components within the chip's core area. An inferior placement assignment will not only affect the chip's performance but might also make it non-manufacturable by producing excessive wire-length, which is beyond available routing resources. Consequently, a placer must perform the assignment while optimizing a number of objectives to ensure that a circuit meets its performance demands. Together, the placement and routing steps of IC design are known as place and route.

<span class="mw-page-title-main">Signal integrity</span>

Signal integrity or SI is a set of measures of the quality of an electrical signal. In digital electronics, a stream of binary values is represented by a voltage waveform. However, digital signals are fundamentally analog in nature, and all signals are subject to effects such as noise, distortion, and loss. Over short distances and at low bit rates, a simple conductor can transmit this with sufficient fidelity. At high bit rates and over longer distances or through various mediums, various effects can degrade the electrical signal to the point where errors occur and the system or device fails. Signal integrity engineering is the task of analyzing and mitigating these effects. It is an important activity at all levels of electronics packaging and assembly, from internal connections of an integrated circuit (IC), through the package, the printed circuit board (PCB), the backplane, and inter-system connections. While there are some common themes at these various levels, there are also practical considerations, in particular the interconnect flight time versus the bit period, that cause substantial differences in the approach to signal integrity for on-chip connections versus chip-to-chip connections.

Zuken Inc. is a Japanese multinational corporation, specializing in software and consulting services for end-to-end electrical and electronic engineering. Zuken came into existence as a pioneer in the development of CAD systems in Japan to contribute to electronics manufacturing. The literal translation of Zuken is "graphics laboratory." Established in 1976 in Yokohama, Japan, it is listed on the Tokyo Stock Exchange; net sales amounted to US$216 million for the year 2011.

<span class="mw-page-title-main">FreePCB</span> Printed circuit board design program for Microsoft Windows

FreePCB is a printed circuit board design program for Microsoft Windows, written by Allan Wright.

<span class="mw-page-title-main">Layout Versus Schematic</span> Type of electronic circuit design software

The Layout Versus Schematic (LVS) is the class of electronic design automation (EDA) verification software that determines whether a particular integrated circuit layout corresponds to the original schematic or circuit diagram of the design.

In electronic design automation, maze runner is a connection routing method that represents the entire routing space as a grid. Parts of this grid are blocked by components, specialised areas, or already present wiring. The grid size corresponds to the wiring pitch of the area. The goal is to find a chain of grid cells that go from point A to point B.

<span class="mw-page-title-main">KiCad</span> Free software suite for electronic design automation

KiCad is a free software suite for electronic design automation (EDA). It facilitates the design and simulation of electronic hardware for PCB manufacturing. It features an integrated environment for schematic capture, PCB layout, manufacturing file viewing, ngspice-provided SPICE simulation, and engineering calculation. Tools exist within the package to create bill of materials, artwork, Gerber files, and 3D models of the PCB and its components.

TopoR is an EDA program developed and maintained by the Russian company Eremex. It is dedicated to laying out a printed circuit board (PCB). The current version is 6.3.17875 as of 2017-09-20.

This page is a comparison of electronic design automation (EDA) software which is used today to design the near totality of electronic devices. Modern electronic devices are too complex to be designed without the help of a computer. Electronic devices may consist of integrated circuits (ICs), printed circuit boards (PCBs), field-programmable gate arrays (FPGAs) or a combination of them. Integrated circuits may consist of a combination of digital and analog circuits. These circuits can contain a combination of transistors, resistors, capacitors or specialized components such as analog neural networks, antennas or fuses.

<span class="mw-page-title-main">PCB (software)</span>

PCB is a free and open-source software suite for electronic design automation (EDA) - for printed circuit boards (PCB) layout. It uses GTK+ for its GUI widgets.

<span class="mw-page-title-main">DesignSpark PCB</span>

DesignSpark PCB is a free electronic design automation software package for printed circuit boards. Although there is no charge for the software, the user must register with DesignSpark.com to unlock the program and it displays advertisements which must be acknowledged before the user can begin working.

<span class="mw-page-title-main">DipTrace</span>

DipTrace is a proprietary software suite for electronic design automation (EDA) used for electronic schematic capture and printed circuit board layouts. DipTrace has four applications: schematic capture editor, PCB layout editor with built-in shape-based autorouter and 3D preview, component editor, and pattern editor.

<span class="mw-page-title-main">Pulsonix</span>

Pulsonix is an electronic design automation (EDA) software suite for schematic capture and PCB design. It is produced by WestDev, which is headquartered in Gloucestershire, England, with additional sales and distribution offices overseas. It was first released in 2001, and runs on Windows.

<span class="mw-page-title-main">Proteus Design Suite</span> Electronic design automation software

The Proteus Design Suite is a proprietary software tool suite used primarily for electronic design automation. The software is used mainly by electronic design engineers and technicians to create schematics and electronic prints for manufacturing printed circuit boards.

Specctra is a commercial PCB auto-router originally developed by John F. Cooper and David Chyan of Cooper & Chyan Technology, Inc. (CCT) in 1989. The company and product were taken over by Cadence Design Systems in May 1997. Since its integration into Cadence's Allegro PCB Editor, the name of the router is Allegro PCB Router. The latest version is 17.4 – 22.1.

References

  1. ↑ 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.
  2. ↑ 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. doi:10.1109/tcad.1985.1270096. S2CID   17511882.
  3. 1 2 3 4 5 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.
  4. ↑ Ritchey, Lee W. (December 1999). "PCB routers and routing methods" (PDF). PC Design Magazine. Speeding Edge (February 1999). Archived (PDF) from the original on 2018-10-22. Retrieved 2018-10-22.
  5. ↑ Lee, Chester Y. (September 1961). "An algorithm for path connections and its applications". IRE Transactions on Electronic Computers . EC-10 (3): 346–365. doi:10.1109/TEC.1961.5219222. S2CID   40700386.
  6. 1 2 3 4 5 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.
  7. ↑ Hadlock, Frank O. (1977-12-01). "A shortest path algorithm for grid graphs". Networks. 7 (4): 323–334. doi:10.1002/net.3230070404.
  8. ↑ Mikami, Koichi; Tabuchi, Kinya (1968). A computer program for optimal routing of printed circuit connectors. IFIPS Proceedings. Vol. H47. pp. 1745–1478.
  9. ↑ 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".)
  10. 1 2 3 4 Minges, Merrill L. (1989). Electronic Materials Handbook: Packaging. Vol. 1. ASM International. ISBN   978-0-87170-285-2 . Retrieved 2017-09-27.
  11. ↑ 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. doi:10.1109/TCAD.1985.1270117. S2CID   17065773.
  12. 1 2 3 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.
  13. ↑ McLellan, Paul (2012-04-23). "Channel Routing Memories". Archived from the original on 2021-05-18. Retrieved 2022-01-01.
  14. ↑ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, G. J.; Symonds, G. (1985-06-23). A Method for Gridless Routing of Printed Circuit Boards (PDF). 22nd ACM/IEEE Design Automation Conference, Las Vegas, Nevada, USA. Design Automation Conference, 2009. Dac '09. 46th ACM/IEEE. 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.
  15. ↑ Webb, Darrell (2012-12-20). "A Tribute to Alan Finch, the Father of Gridless Autorouting". Archived from the original on 2018-10-22. Retrieved 2018-10-22.
  16. ↑ 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.
  17. ↑ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen". Computerwoche (in German). 1992-03-13. Archived from the original on 2018-10-21. Retrieved 2018-10-20.
  18. ↑ 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.
  19. 1 2 Redlich, Detlef. "1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung" (PDF). Schaltungsdesign (in German). Ernst-Abbe-Hochschule Jena (EAH). Archived from the original (PDF) on 2018-10-21. Retrieved 2018-10-20.
  20. ↑ "Simplify Design Automation – the next generation in design methodology".
  21. ↑ Soukup, Jirí (1979). "Global Router". Proceedings of the 16th Design Automation Conference. San Diego, CA, USA: IEEE Press. pp. 481–489.
  22. ↑ Rubin, Frank (1974). "An iterative technique for printed wire routing". Proceedings 11th Design Automation Workshop. pp. 308–13.
  23. ↑ 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.