Routing (EDA)
Encyclopedia
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
, 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.
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 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 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 routing
have also been shown to be NP-complete, as well as routing which reduces crosstalk, number of via
s, 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.
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 DRC. Some more advanced interactive routers have "push and shove" 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 four main types of autorouters are:
For detailed routing, the most common technique is rip-up and reroute:
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 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. 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.
Printed circuit board
A printed circuit board, or PCB, is used to mechanically support and electrically connect electronic components using conductive pathways, tracks or signal traces etched from copper sheets laminated onto a non-conductive substrate. It is also referred to as printed wiring board or etched wiring...
s (PCBs) and integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
s (ICs). It builds on a preceding step, called placement
Placement (EDA)
Placement is an essential step in electronic design automation - the portion of the physical design flow that assigns exact locations for various circuitcomponents within the chip’s core area...
, 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.
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 effect
Antenna effect
The antenna effect, more formally plasma induced gate oxide damage, is an effect that can potentially cause yield and reliability problems during the manufacture of MOS integrated circuits. Fabs normally supply antenna rules, which are rules that must be obeyed to avoid this problem. A violation...
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 intractable
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. The simplest routing problem, called the Steiner tree
Steiner tree
The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
problem, of finding the shortest route for one net in one layer with no obstacles and no design rules is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
if all angles are allowed and NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
if only horizontal and vertical
wires are allowed. Variants of channel routing
Channel router
A channel router is a specific variety of router for integrated circuits. Normally using two layers of interconnect, it must connect the specified pins on the top and bottom of the channel. Specified nets must also be brought out to the left and right of the channel, but may be brought out in any...
have also been shown to be NP-complete, as well as routing which reduces crosstalk, number of via
Via (electronics)
A via is a vertical electrical connection between different layers of conductors in a physical electronic circuit.- In IC :In integrated circuit design, a via is a small opening in an insulating oxide layer that allows a conductive connection between different layers. A via on an integrated circuit...
s, 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
Printed circuit board
A printed circuit board, or PCB, is used to mechanically support and electrically connect electronic components using conductive pathways, tracks or signal traces etched from copper sheets laminated onto a non-conductive substrate. It is also referred to as printed wiring board or etched wiring...
or Multi-Chip Module
Multi-Chip Module
A multi-chip module is a specialized electronic package where multiple integrated circuits , semiconductor dies or other discrete components are packaged onto a unifying substrate, facilitating their use as a single component...
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
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 DRC. Some more advanced interactive routers have "push and shove" 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 four main types of autorouters are:
- Maze routerMaze routerMaze 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....
- Line probe router
- Channel routerChannel routerA channel router is a specific variety of router for integrated circuits. Normally using two layers of interconnect, it must connect the specified pins on the top and bottom of the channel. Specified nets must also be brought out to the left and right of the channel, but may be brought out in any...
- Area routers
- Switchbox routing
How routers work
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, 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:
- 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 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. 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
- Electronic design automationElectronic design automationElectronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
- Design flow (EDA)Design flow (EDA)Design flows are the explicit combination of electronic design automation tools to accomplish the design of an integrated circuit. Moore's law has driven the entire IC implementation RTL to GDSII design flows from one which uses primarily...
- Integrated circuit designIntegrated circuit designIntegrated circuit design, or IC design, is a subset of electrical engineering and computer engineering, encompassing the particular logic and circuit design techniques required to design integrated circuits, or ICs...