By now every part of the chip has its spot, and the clock wiring is in. But the millions of tiny parts still aren’t connected to each other. Routing draws every wire between them, exactly as the parts list says.
Those levels are real: ten or more thin layers of copper wiring, stacked on top of the chip’s tiny switches. A small upright plug called a joins a wire on one layer to a wire on the next, like an elevator. Wires on the same layer must never touch, or their signals would mix.
By this stage the chip exists as a : a list of its building blocks, called cells (small ready-made circuits such as logic gates, and flip-flops, which each store one bit), together with which of their connection points, or pins, must be joined. Each group of pins that must be wired together is a . Earlier stages have fixed where every cell sits on the silicon and have built the wiring that delivers the clock, the steady beat that keeps all the flip-flops in step.
Routing turns every remaining net into metal. It draws wire segments on the , the layers of wiring above the transistors, and places , the vertical plugs that join one layer to the next. The result has to meet four conditions at once: every pin of every net is connected; no two nets touch; every shape obeys the factory’s design rules about how thin, how close and how small metal may be; and the chip is still fast enough once the real wire lengths are known.1
That is too big a problem to solve in one step, so it is split in two. plans a rough path for every net across a coarse grid of tiles. then draws the exact wires, following that plan.12 Every chip design flow has both engines, whether it uses commercial tools such as Cadence Innovus or Synopsys Fusion Compiler, or the open-source OpenROAD, whose global router (grt) is based on a program called FastRoute and whose detailed router (drt) is based on TritonRoute.46
Routing is where estimates become measurements. Until now, timing tools have guessed each wire’s resistance and capacitance (its parasitics) from where the cells sit. After routing, those values come from real shapes. It is also where the foundry’s full set of geometric rules is enforced on every piece of metal.
Routing inherits its difficulty from placement. How crowded the wiring is (congestion), how many pins are packed into a small area, and how narrow the channels between large blocks are decide whether the router can finish cleanly. The textbook reading of a global-routing failure is simple: many violations mean the netlist must be restructured or placement redone; a few may still be fixed by detailed routing.1
The core search algorithms (Lee’s maze routing, A* search, rip-up and reroute, channel routing) have stayed largely unchanged in commercial tools for decades. The work goes into making them meet real-world requirements: every design rule honored, good results, scale to large designs, and acceptable runtime.9 OpenROAD shows the whole pipeline in the open. A FastRoute-based global router produces route guides; then TritonRoute runs pin access analysis, track assignment, initial routing, repeated search and repair, and its own rule checker.46 Each step is explained below.
- Default GCell size, OpenROAD global_route
- 15 M3 pitches
- Default congestion iterations, FastRoute in OpenROAD
- 50
- Max detailed-routing iterations, OpenROAD detailed_route
- 64
- TritonRoute DRC reduction vs. best published academic routers (ISPD-2018, avg.)
- 92%
The first three come from the OpenROAD documentation, the last from the TritonRoute paper.469 A GCell is one tile of the global router’s grid; 15 M3 pitches means 15 track spacings of the third metal layer. DRC counts are design-rule violations left after routing.
On a single layer, nets A and B can’t cross without touching: a short circuit between two signals.
Routing starts with the placed chip, with the clock wiring and power wiring already built. It also gets the parts list of which pins must connect, and the factory’s rule book for wires.
It ends with a drawing of every wire and via. Then another tool checks that signals can still cross the chip in time.
| Direction | What | Format |
|---|---|---|
| In | The placed design: where every cell, large block (macro) and chip-edge pin sits, plus the finished clock wiring, the power grid and areas wires must avoid | DEF, or the tool’s own database (OpenROAD: .odb) |
| In | The netlist: every cell and which pins each net joins, including buffers added by earlier stages | Verilog |
| In | The rulebook for wires: layers, directions, track spacing, widths, spacing rules, via shapes, antenna limits and special wide-wire rules; plus each cell’s pin shapes and no-go areas | Tech LEF and cell LEF |
| In | Timing targets and each cell’s timing data, so the router can favor urgent nets | SDC, Liberty (.lib) |
| Out | The routed design: every wire segment and via, net by net | DEF (NETS with ROUTED wiring) or .odb |
| Out | Measured resistance and capacitance of every net, including coupling between neighbors | SPEF |
| Out | Reports: congestion, rule violations, antenna, wire length, via counts, timing | Text logs, violation marker files, views in the tool’s viewer |
All of these are text files with fixed formats that every tool reads. (Library Exchange Format) is the router’s rulebook. For each routing layer it gives the preferred direction (horizontal or vertical) and the pitch, the spacing between neighboring wire positions, from which the routing grid is built. It also gives the minimum wire width and spacing, the smallest allowed piece of metal, the via shapes and the antenna limits explained later.3
(Design Exchange Format) describes the design itself. After routing it lists every net’s wiring as straight segments on named layers, with vias placed by name where the route changes layer.3 A separate step called extraction then measures each net’s resistance and capacitance from those shapes and writes them to a file, which the timing check reads.8 SDC and Liberty are the timing files from earlier stages: what speed the chip must reach, and how fast each cell is.
Three inputs are easy to miss. First, non-default rules (LEF NONDEFAULTRULE): per-layer wider widths, extra spacing, special vias and minimum cut counts that selected nets, such as clocks, may use. They must exist before routing starts.3 Second, antenna data: the per-layer ratio limits, each cell pin’s gate and diffusion area, and a cell marked ANTENNACELL that the router can insert as a protective diode. If any of it is missing, the antenna checker’s results mean nothing.37
Third, the file passed between the two routers: the , one set of rectangles per net saying which GCells and layers its wires should stay in. TritonRoute reads them in the format of the ISPD-2018/2019 routing contests.6 On the output side, OpenRCX, OpenROAD’s extractor, computes wire resistance, coupling capacitance to neighbors and capacitance to ground from a rules file calibrated once per process and corner (a set of manufacturing and temperature conditions), and writes SPEF.8 Signoff teams usually re-extract with the extractor the foundry has qualified before the final timing check.
Tap or hover any box: four inputs on the left, two routing passes in the middle, three outputs on the right.
Lanes and levels
Each layer is split into evenly spaced lanes, like the lanes on a running track. On one layer, all the lanes run left to right. On the next layer up, they run top to bottom. So a wire that needs to turn a corner hops up or down a level through a via.
Plan first, then draw
- Plan. The software lays a grid of big squares over the chip, like a map split into neighborhoods. It picks a rough path for every connection, square by square. Where more wires want to pass than there is room for, there is : a traffic jam. The planner sends some wires around it.
- Draw. Then it draws every wire exactly, in its own lane, and checks every rule. If something breaks a rule, it pulls out the nearby wires and tries again, pass after pass, until nothing is wrong.
Short connections use the thin lower layers. Long ones climb to the thick upper layers, where signals travel faster.
Metal stack, tracks and vias
The runs from M1, the lowest layer, which sits just above the transistors and is partly used inside the cells themselves, up to the top layers used for power and long routes. Each layer has a ; a typical stack runs M1 and M3 horizontally and M2 vertically.3 Wires sit on , evenly spaced lines one pitch apart, and the tracks of all layers together form the grid the router works on.3 A joins two neighboring layers.
Lower layers are thin and closely packed. Upper layers are wider and thicker, so they resist current less. A signal is a voltage change that has to charge up the wire, and a wire with more resistance charges more slowly, so timing-critical nets get pushed up to the upper layers.19
Global routing: the plan
The global router lays a coarse grid of tiles called over the chip. It ignores exactly where inside a tile a wire runs. It only counts, for each border between two neighboring tiles on each layer, how many tracks cross that border (its capacity) and how many nets want to cross it (its demand). It then gives every net a path through the tiles without exceeding any border’s capacity.1 In OpenROAD a GCell is 15 M3 track spacings on a side by default.4
A worked example: on M3, a border between two tiles is crossed by 15 tracks, but a power wire blocks 3 of them, so its capacity is 12. If 14 nets want to cross, the border has an of 2. The router tries to send two of those nets around, through neighboring tiles or on other layers. Overflow added up over every border is the headline number of a congestion report, and a picture of it tile by tile is the congestion map.
Nets with more than two pins are first broken into two-pin pieces. The router finds a short branching shape that reaches all the pins, a , and routes each branch separately. About half of all nets have only two pins anyway.1 Each piece is first tried as a simple L- or Z-shaped path, which is fast. Where those shapes would overflow, the router searches the grid properly with . Nets that still collide are then ripped up and routed again, with crowded borders made more expensive each round so nets learn to avoid them.15 The result is a set of for every net, plus a congestion report.4
Track assignment and detailed routing: the drawing
puts the long straight stretches of each route onto specific tracks. then connects everything for real. It first works out a legal way to reach each cell’s pins without blocking its neighbors’. It then draws wires on the track grid, inside each net’s guides. Finally it runs repeated search-and-repair passes: find every broken rule, pull up the wires near it, route them again, until the count of violations reaches zero.26 A last clean-up pass can replace single vias with , so a connection survives if one plug is badly made.2
Finishing: extraction and late fixes
Once the layout is clean, an extraction tool computes each net’s resistance and capacitance, including the coupling to the wires beside it, and writes for the timing check.8 Any remaining timing problems are fixed with small (engineering change orders): make one gate stronger, insert a buffer (a small amplifier cell), and reroute only the nets touched. OpenROAD’s global router has an incremental mode for this.4 Very late in a project, a “metal-only” ECO rewires spare cells scattered across the chip during placement, so that only the masks for metal and vias have to change, not the costly ones for the transistors.25
Global routing in practice
The global router models the chip as a coarse 3D grid graph: one node per GCell per layer, with a capacity on every edge. On it, it chooses each net’s topology and layers while weighing routability, timing, crosstalk and power.9 FastRoute, the core of OpenROAD’s grt, works in stages. It builds Steiner trees with the FLUTE lookup-table method and reshapes them away from congestion. It then tries pattern routes (L- and Z-shapes), monotonic routes (paths that never double back) and multi-source multi-sink maze routing (search that can start from and end at any point already on the net’s tree), all inside a rip-up-and-reroute loop. It uses “virtual capacity”, adjusting each edge’s capacity as it goes to divert wires away from the most congested regions, and finishes with a layer assignment that keeps via counts low.5 Three settings matter most in practice:
- Capacity adjustment. set_global_routing_layer_adjustment hides a fraction of each layer’s tracks from the global router. That spreads routing out and lowers peak congestion, leaving slack for what the coarse model can’t see: pin access, vias and rule overhead in detailed routing.4 Lower layers usually need larger adjustments, because pins, local vias and power rails use up their tracks.
- Macro extension. set_macro_extension blocks extra GCells around macros (large pre-designed blocks such as memories). This stops the global router from promising tracks at macro edges that will be needed to reach the macro’s own pins.4
- Timing priority. -critical_nets_percentage marks that share of nets with the worst slack (the least time to spare) as critical, and gives them preference during congestion iterations, so detours land on nets that can afford them. OpenROAD also has a resistance-aware layer assignment mode, still marked as not ready for production.4
Read overflow per layer as well as in total. Thousands of overflowed edges spread across a block point to a problem of overall density or floorplan. A tight cluster next to a macro corner points to a local placement fix. Routers can be told to continue despite leftover congestion (in OpenROAD, -allow_congestion), but residual overflow can turn into detours or rule violations later.41
The detailed-routing pipeline
TritonRoute is a good open model of an industrial detailed router. It runs in four stages.
- Pin access analysis finds legal points and via choices for reaching every pin, once for each distinct combination of cell type, orientation and alignment to the track grid.11
- Track assignment is a simplified greedy method, run on panels 50 GCells across, horizontal layers first and then vertical, followed by one pass of reassignment.9
- Initial detailed routing connects every net once.6
- Search and repair repeats. Each iteration cuts the die into clips of 7×7 GCells and hands each clip to a worker thread. The worker routes with A* search on a grid graph, runs its own rule check, rips up and reroutes the nets near each violation, and commits its result. Alternate iterations shift the clip grid, so violations that sat on a clip boundary land inside a clip next time.9
OpenROAD exposes the iteration count (-droute_end_iter, 1 to 64) and writes the violations still left as a marker file (-output_drc) that you can load in its viewer.6 The textbook summary of the same stages: assign tracks, route every connection so none is left open, search and repair until every design rule is met, then optimize, for example by adding redundant vias.2
ECO routing and extraction
Optimization after routing, and functional ECOs that change the logic, reroute only the nets that changed. The risk is local. A buffer dropped into a full area may find no legal way to connect. A metal-only patch that has to use distant spare cells adds long wires, timing violations and congestion.25 Every ECO needs fresh extraction. OpenRCX models coupling from the distance to the nearest neighbor and from how densely the layers above and below are filled, so a reroute changes the coupling of the nets around it as well as its own.8
Placed pins: Three two-pin nets, A, B and C, with their cells already placed.
Capacity 15 − 3 = 12; demand 14; overflow 2. The router must send 2 nets through neighboring tiles or onto other layers.
The factory can only build wires that follow its rules. Wires can’t be too thin or too close together. The router checks millions of shapes against rules like these, and keeps fixing until none are broken.
One rule protects the chip while it is being made. Building each layer leaves a little static charge on the wires, like the shock you get from a doorknob. A long wire can collect enough to zap the tiny switch it leads to. This is called the . The router fixes it by hopping the wire up to a higher layer near the switch, or by adding a tiny part that drains the charge away.
The factory that builds the chip, the foundry, publishes design rules: the limits of what its process can print reliably. Checking a layout against them is called , and each broken rule is a violation. The router carries a simplified version of these rules, from LEF, and must satisfy them as it draws.
Rules that shape routing
- Width and spacing. Each layer has a minimum wire width and a minimum gap between wires. The gap must be larger next to wide wires and where two wires run side by side for a long distance.3
- Line-end spacing. The end of a wire needs more clearance than its side, so a wire end that faces a neighbor too closely is a violation. LEF calls these end-of-line (EOL) rules.3
- Minimum area. Every separate piece of metal must have at least a set area, so a tiny landing pad between two vias may need a patch of extra metal.3
- Via rules. Via plugs need a minimum gap from each other, enough metal around them on the layers above and below (enclosure), and on wide wires sometimes a minimum number of plugs.3
These rules interact. A legal via can push a neighbor’s wire end into violation, and a minimum-area patch can create a spacing error. That is why detailed routers check rules as they go and repeat their passes.9 In a healthy run the number of violations drops fast in the first passes, then slowly through a tail of hard cases near crowded pins and the edges of large blocks.
Antennas
Each metal layer is shaped by plasma etching, which leaves electric charge on the metal. A transistor’s gate, its control input, sits on an extremely thin insulating film. Once the chip is finished, every net also touches the output of the cell that drives it, which gives that charge a harmless way out. But while the lower layers are being made, a stretch of metal may be connected only to gates, and if it collects enough charge it can break through the film and damage them. This is the .320
The foundry limits the antenna ratio: the area of metal connected to a node on a layer divided by the area of the gates connected to it, with a limit for each layer.3 A made-up example: if a layer’s limit is 400 and the gate connected to a wire has an area of 0.1 µm², that wire may have at most 40 µm² of metal on that layer before it reaches a higher layer. Routers fix violations in two ways. They can break the wire and finish the connection on a higher layer close to the gate, so only a short stub stays on the risky layer. Or they can add a small diode, a one-way electrical part that gives the charge a safe path into the silicon.320 In OpenROAD, check_antennas reports violations and repair_antennas inserts diode cells near the affected gates after global routing.74
Redundant vias
A via with a single plug that fails to form in manufacturing leaves its net broken. Detailed routers therefore finish with a pass that replaces single vias with wherever there is room. That lowers resistance and raises the share of chips that work.2
What the router actually checks
The rules a router sees come from tech LEF.3 In plain terms:
- spacing tables, where the required gap depends on both wires’ widths and on how long they run side by side (the parallel run length);
- end-of-line spacing, often with extra conditions about other wires running alongside the end;
- minimum area, and minimum step (no tiny notches or jogs in a wire’s outline);
- cut spacing between via plugs, and enclosure, which can differ by direction;
- minimum cuts for vias on wide wires.
TritonRoute builds spacing tables, end-of-line spacing and cut spacing into the costs of its path search, so the search avoids likely violations in the first place. It handles minimum area separately: as it writes each finished path, it adds patch metal along the preferred direction wherever a piece is too small.9 The foundry’s full signoff rule deck is larger and more context-dependent than what LEF can express, so a router-clean layout still goes through full DRC. Expect a small, recurring set of violations that only the signoff check finds and that need manual or scripted fixes.
Getting the count to zero
Search and repair works only if its costs learn. TritonRoute keeps two kinds of cost on its grid graph. Object costs are added around each shape when it is drawn and removed when it is ripped up, steering new wires away from likely violations. Marker costs are added around each violation the checker reports; they fade over a worker’s rip-up rounds but are never removed, which gives the worker a memory of recent trouble spots. That memory stays inside the worker; nothing carries over from one detailed-routing iteration to the next.9
If the count stops falling, the cause is usually structural: a pin with no legal way in, a clash between two cells’ edges that placement created, or a GCell that global routing overfilled. More iterations rarely fix those. Load the marker file in the viewer, group the violations by type and by location, and fix the placement or the capacity adjustments.
Antennas in detail
The checker walks each net layer by layer from its gates upward. For each piece of wire it computes a partial area ratio (PAR): that piece’s metal area over the gate area connected below it. Then, for each gate and each wire above it, it adds up the PARs along the path between them to get a cumulative area ratio (CAR). Both are compared with the rules.7 Limits can be piecewise-linear (PWL) in the connected diffusion area, meaning a diode raises the allowed ratio. If the PDK instead gives a constant diffusion ratio, a diode can’t help, and OpenROAD’s repair_antennas declines to insert one.4 Filler cells (the blank cells that fill gaps in the rows) must come out before diodes go in and be put back after.4 Fix antennas on the global route, then check again after detailed routing, because the final wiring can differ from the guides.
Spacing: The gap is smaller than the layer’s minimum spacing (the dashed outline): a spacing violation.
Transistors first: the driver’s output (left) and the gate it will drive (right). Nothing connects them yet.
Long, thin wires slow signals down. So the router gives the most urgent connections the shortest paths and the thick upper layers.
Two wires that run side by side for a long way can also disturb each other. When one switches, it gives its neighbor a nudge. This is called . The router fixes it by spacing the wires apart, or by running a quiet shield wire between them.
Timing-driven routing
Every signal has to get from one flip-flop to the next within one tick of the clock. The time left over on a path is its ; negative slack means the signal arrives too late. A wire slows a signal in two ways: its resistance limits how fast current can flow, and its capacitance is the charge that has to be filled before the voltage changes. Longer and thinner wires are worse on both counts. Timing-driven routing ranks nets by slack and gives the ones with the least to spare first claim on short paths and on the upper layers, whose wider wires resist current less.194
Crosstalk
Two wires running side by side, separated by insulator, form a small capacitor: . It grows with the length they run together and shrinks as the gap between them grows.15 When the signal on one wire, the aggressor, switches, it pushes on its neighbor, the victim. If the victim is holding steady, the push can make a brief glitch, which is a real error if a flip-flop happens to store it. If the victim is switching at the same moment, the push can slow it down or speed it up, which changes its timing.17 Routers reduce by leaving extra space,15 by running a shield wire tied to ground or power beside the victim, and by choosing which nets become neighbors when tracks are assigned.18
Special wiring rules
A (NDR) lets chosen nets use wider wires, extra spacing or vias with several plugs.3 Wider wires lower resistance and delay; extra spacing lowers coupling.1915 Clock nets commonly get one. NDR wires use up more tracks, so they go only on the nets that need them.19
Layers and resistance
Upper layers have wider wires and wider spacing, so their resistance is lower, which makes layer assignment a timing tool. Timing-aware layer assignment moves critical segments up while watching congestion, via count and coupling.19 There are limits. Manufacturing allows wire widths only from a set of predefined values, and on the lowest layers of advanced nodes an NDR can only be built as several parallel minimum-width wires, not one wide one.19 Promotion also costs vias: every segment moved up needs a via stack at each end, and vias add delay of their own.19
Signal integrity
At tight pitches, a wire’s coupling to the wires beside it on the same layer can exceed its capacitance to ground, while coupling to wires further away is negligible.18 That makes the choice of neighbor the main lever.
Static timing tools can’t simulate every combination of switching neighbors, so they use a shortcut. Each coupling capacitance is replaced by a capacitance to ground of , where , the switch factor, reflects what the neighbor is doing: 0 if it switches the same way at the same time, 1 if it holds still, 2 if it switches the opposite way. The tool starts from the worst case, then narrows each using the time windows in which each net can actually switch, and repeats until the numbers settle. Kahng, Muddu and Sarto showed that 2 is not a safe upper bound: for signals modeled as ramps with different slopes, the worst case is , so a assumption can underestimate delay.17 Coupling grows with the length two wires run in parallel.15 So when one path shows a large crosstalk-induced delay change (delta delay), look first for a few long runs beside switching neighbors.
Router-side fixes, roughly from cheapest to most expensive: reassign tracks so sensitive nets aren’t neighbors; add spacing, through an NDR or by spreading wires; shield with power or ground wires; move one net to another layer; and finally make the victim’s driver stronger or add a buffer. In He and Lepak’s experiments, solving net ordering and shield insertion together used 15% to 57% fewer shield wires than doing them one after the other.18 In DEF, a shielded net names its shield net with SHIELDNET, and the shield wiring itself is listed under SPECIALNETS.3
M6 is fastest at this length: its low resistance per length outweighs the extra vias.
The victim glitches to 38% of the supply, above the 30% limit used here. If a flip-flop captures it, that is a real error.
On the newest chips, the lowest wires are so fine and so close together that the factory can’t print them in one go. It prints them in two or more steps instead, like painting every other stripe first. That adds rules about which wires may sit side by side.
Some new chips also move the power wiring underneath the switches, to the back of the chip. That frees up room on top for signal wires.
Chips are printed by shining light through a mask, a stencil of the layer’s shapes. On the newest manufacturing processes (“advanced nodes”) the lowest metal layers are too dense to print in one exposure, so they use . One method, litho-etch-litho-etch (LELE), splits a layer’s shapes across two masks printed one after the other. Others use thin spacer films grown on the sides of printed lines to halve the spacing once (SADP) or twice (SAQP).21 For the router, this means each shape gets a “color” for its mask, and shapes too close to share a mask must get different colors.22
Cells have also become so small that reaching each pin legally without blocking a neighbor’s pin, called , is one of the most serious problems of advanced processes.11 Power wiring is a big consumer of routing space too, and new processes move it below the transistors or to the , out of the signal layers.23
- Coloring. In LELE, any two shapes closer than the coloring spacing need different masks. Draw each shape as a node and each too-close pair as an edge: this conflict graph must be two-colorable, and a cycle with an odd number of shapes is not. Decomposition can remove such a cycle only by splitting one shape into two parts printed on different masks (a stitch). If no split resolves the cycle, the layout itself must change.22 SADP and SAQP make regular rows of lines from spacers; SAQP was printing a 36 nm minimum metal pitch by 2017.21 Routers enforce the preferred direction more strictly on these layers.2
- Pin access. TritonRoute’s pin access oracle computes access points for each unique instance, meaning a combination of cell type, orientation and offset to the track grid. Access points can be on or off a track, reached on the same layer (planar) or by a via from above. Dynamic programming then picks a combination of access points that do not conflict inside the cell, and then across neighboring cells.11
- Resistance and via pillars. Lower-layer wires and vias near the transistors get narrower, and so more resistive, with each generation.23 A via pillar places several vias in parallel in a regular pattern to cut via resistance; one patented method puts them at a driver’s output on a path with negative slack. Pillars take extra space, use routing resources and complicate routing.24
- Power rails and track supply. Power wiring takes at least 20% of routing resources. Buried power rails move each cell’s power and ground rails below the transistors, which reduces the number of tracks a cell needs on its lowest wiring layer. Backside power delivery moves the whole power network off the signal stack.23 Both shrink cell height or hand tracks back to signals, and both change the router’s pin access and capacity models.
3 same-mask conflicts (red). Tap a shape to move it to the other mask.
Below is a tiny chip with two wiring layers. One runs left to right, the other up and down. Eight connections, A to H, each need a wire between two pins. A big block and a power wire are in the way.
Press Route next. Watch a connection spread out from one pin like ripples in a pond until it reaches the other. Then press Route all. In the starting order, one connection gets stuck, because earlier wires took its space.
Press Rip up & reroute to move the wire in its way. Try Shuffle order too: some orders work on the first try.
The grid is 20 × 14 tracks with two layers: M1 runs horizontally and M2 vertically. Eight two-pin nets, A to H, are routed one at a time. Each search spreads out from one pin, step by step, keeping the cheapest way to reach every grid point: a step along a layer’s direction costs 1, and a change of layer through a via costs whatever the via-cost slider says (3 by default). Routed nets block their tracks for everyone after them. In the default order exactly one net fails.
Rip up & reroute removes the routed net that blocks it most, routes the failed net first, then reroutes the one it removed. Then experiment. Raising the via cost alone changes little, because on this grid every turn needs a via. Tick “Allow wrong-way steps” (cost 4) first, then raise the via cost: nets start jogging sideways on one layer instead of hopping layers, so the via count falls while the total wire length grows. Use Shuffle order to see how much the order of routing matters.
This is sequential maze routing on a 20 × 14, two-layer track grid, with a large blocked area and a pre-routed M2 power strap. Each net is a Lee wave expansion generalized to weighted costs (Dijkstra’s algorithm): preferred-direction steps cost 1, wrong-way steps cost 4 when enabled, and a via costs whatever the slider says.121 Each net’s readout shows its path cost and how many grid points the search visited. Compare the visited count with the path length: that gap is what Hadlock’s detour numbers and A* search exist to shrink.131 In the default order one net fails. That is the order dependence of sequential routing, which is why sequential routers combine a heuristic net order with rip-up and reroute.13 The rip-up button is a single round of rip-up and reroute with no memory. Compare it with negotiated congestion, which keeps raising the price of fought-over resources across iterations.14 Then, with wrong-way steps allowed, sweep the via cost and watch the trade between wire length and via count that real routers make on every net.
An engineer watching a routing run checks three things.
- Did the plan fit? After planning, a map colors the chip like a weather radar. A big red blob means the wires there won’t fit. The fix usually means going back and spreading the parts out.
- Are the mistakes going away? The drawing pass repeats many times. The count of broken rules should drop fast, then trickle to zero. If it gets stuck at a few hundred, something bigger is wrong.
- Is it still fast enough? Real wires are a bit slower than the earlier guesses. Small fixes follow.
Routing tools are driven by scripts: lists of commands, here in a language called Tcl, that the tool runs in order. The script below is an illustrative routing step in the style of the open-source OpenROAD tools. Step by step, it says which layers each kind of net may use, tells the global router to assume fewer tracks than really exist (to leave headroom), runs global routing, fixes antenna problems, fills empty gaps in the cell rows with filler cells, runs detailed routing, and finally measures every wire’s resistance and capacitance. Lines starting with # are comments. Real flows split this across several scripts with settings tuned for each design.
Below are an illustrative OpenROAD-style script, a global-routing congestion report, a detailed-routing log and an excerpt of the routed DEF. The logs are modeled on OpenROAD output but are not verbatim, and the numbers are illustrative. Read them for three things: the overflow on each layer, how fast the violation count falls from one iteration to the next, and which kinds of violation survive the longest. The notes beside each file walk through what to look for.
# route.tcl: illustrative OpenROAD-style routing step, not a complete flow
read_db results/4_cts.odb ;# placed, with clock tree and power grid built
read_sdc constraints/top.sdc
# Which layers each class of net may use
set_routing_layers -signal M2-M8 -clock M4-M8
# Tell the global router it has fewer tracks than LEF says
set_global_routing_layer_adjustment M2 0.50
set_global_routing_layer_adjustment M3-M8 0.25
set_macro_extension 2
# 1. Global routing: guides + congestion report (to diagnose overflow, add -allow_congestion)
global_route -congestion_iterations 50 \
-critical_nets_percentage 10 \
-congestion_report_file reports/congestion.rpt \
-verbose
# 2. Timing on global-route parasitics
estimate_parasitics -global_routing
report_worst_slack -max
# 3. Antennas on the global route, then fillers
repair_antennas -iterations 3 -ratio_margin 10
check_antennas
filler_placement FILL*
# 4. Detailed routing: pin access, track assignment, search and repair
detailed_route -output_drc reports/route_drc.rpt \
-droute_end_iter 64 -verbose 1
check_antennas
# 5. Extract and save
set_extraction_rules_file rules/rcx_typ.rules
extract_parasitics
write_spef results/top.spef
write_def results/5_route.def
write_db results/5_route.odb- 1L6Signals avoid M1, which is mostly cell-internal and pins. Clocks stay on the thicker, less resistive upper layers.
- 2L9Hide 50% of M2 from the global router. Pins, local vias and rails eat lower-layer tracks the coarse model can’t see.
- 3L11Block 2 GCells around each macro so the global router doesn’t promise tracks at macro edges that pin access will need.
- 4L14Up to 50 rip-up-and-reroute rounds on the GCell grid to drive overflow to zero.
- 5L15The worst 10% of nets by slack get first claim on short paths during congestion iterations.
- 6L20First timing look with routed-length wires and layer assignment, before committing to detailed routing.
- 7L24Insert diodes near gates of violating nets. The 10% margin leaves room for the final wiring to differ from the guides.
- 8L26Fillers go in after diode insertion, which needs the empty space.
- 9L29Remaining violations go to a marker file you can load in the GUI.
- 10L31Recheck antennas on the final wiring. The guides were only an approximation of it.
- 11L35Extraction uses the rules file set above, calibrated for this process and corner. write_spef then saves the result for signoff timing.
The global router’s report compares tracks available with tracks wanted, layer by layer. Resource is the capacity left after the adjustments and blockages; Demand is how much of it the nets use; Usage is the ratio of the two. The last column gives the worst overflow on any single horizontal border, the worst on any vertical border, and the total over all borders. Any nonzero overflow is a warning.
[INFO GRT-0020] Min routing layer: M2
[INFO GRT-0021] Max routing layer: M8
[INFO GRT-0088] Layer M2 Track-Pitch = 0.2000 line-2-Via Pitch: 0.1900
[INFO GRT-0019] Found 412 clock nets.
[INFO GRT-0001] Minimum degree: 2 Maximum degree: 38
[INFO GRT-0003] Macros: 4
[INFO GRT-0004] Blockages: 18,224
[INFO GRT-0101] Running extra iterations to remove overflow.
[INFO GRT-0103] Extra Run for hard benchmark.
[INFO GRT-0197] Via related to pin nodes: 152,880
[INFO GRT-0198] Via related Steiner nodes: 6,214
[INFO GRT-0111] Final number of vias: 401,377
[INFO GRT-0112] Final usage 3D: 2,112,906
[INFO GRT-0096] Final congestion report:
Layer Resource Demand Usage (%) Max H / Max V / Total Overflow
---------------------------------------------------------------------
M2 318,402 201,377 63.25% 0 / 2 / 9
M3 486,110 359,872 74.03% 3 / 0 / 21
M4 461,920 315,505 68.30% 0 / 1 / 4
M5 402,355 211,041 52.45% 0 / 0 / 0
M6 240,118 98,250 40.92% 0 / 0 / 0
M7 118,900 31,770 26.72% 0 / 0 / 0
M8 58,220 10,460 17.97% 0 / 0 / 0
---------------------------------------------------------------------
Total 2,086,025 1,228,275 58.88% 3 / 2 / 34
[INFO GRT-0018] Total wirelength: 812,904 um
[WARNING GRT-0115] Global routing finished with overflow.- 1L8The first pass left overflow, so FastRoute ran its congestion-removal iterations.
- 2L12Via count matters: each via adds resistance and blocks tracks. Compare it run over run.
- 3L18All the overflow sits on M2–M4, which is typical: pins and local connections crowd the lower layers.
- 4L19Max overflow 3 on one M3 edge. A handful of overflowed edges may clear in detailed routing; a cluster will not.
- 5L21Upper layers are lightly used. Pushing a few long nets up (layer promotion) could relieve M3.
- 6L26Total overflow 34 against about 2 million units of capacity. Load the congestion report in the GUI to see whether these edges cluster.
- 7L29This warning appears when the run is allowed to continue with congestion (-allow_congestion, for diagnosis); without that flag, global_route stops with an error here. Fix it before detailed routing with capacity adjustments, keep-out margins around macros, or placement changes.
Detailed routing reports its violations after every iteration. The total should fall steeply and then crawl. The table breaks them down by layer and by rule: Short means two different nets touch; Metal Spacing means two wires are too close; EOL means a wire end is too close to something; Cut Spacing means two via plugs are too close; Min Area means a piece of metal is too small. The lower layers dominate because that is where the pins are.
[INFO DRT-0165] Start pin access.
[INFO DRT-0078] Complete 2,941 unique inst patterns.
[INFO DRT-0081] Complete 1,388 unique instances with 0 pins lacking access points.
[INFO DRT-0181] Start track assignment.
[INFO DRT-0184] Done with 228,516 vertical wires in 4 frboxes and 241,077 horizontal wires in 4 frboxes.
[INFO DRT-0194] Start detail routing.
[INFO DRT-0195] Start 0th optimization iteration.
[INFO DRT-0199] Number of violations = 18,412.
Viol/Layer M1 M2 M3 M4 M5
Cut Spacing 0 211 38 4 0
EOL 0 1,906 522 61 3
Metal Spacing 12 3,118 1,047 170 12
Min Area 0 388 41 2 0
Short 27 7,402 2,839 501 108
[INFO DRT-0195] Start 1st optimization iteration.
[INFO DRT-0199] Number of violations = 4,906.
[INFO DRT-0195] Start 2nd optimization iteration.
[INFO DRT-0199] Number of violations = 3,877.
[INFO DRT-0195] Start 3rd optimization iteration.
[INFO DRT-0199] Number of violations = 412.
[INFO DRT-0195] Start 8th optimization iteration.
[INFO DRT-0199] Number of violations = 31.
Viol/Layer M1 M2 M3
EOL 0 9 2
Metal Spacing 0 11 3
Short 2 4 0
[INFO DRT-0195] Start 17th optimization iteration.
[INFO DRT-0199] Number of violations = 0.
[INFO DRT-0198] Complete detail routing.
Total wire length = 848,331 um.
Total number of vias = 389,215.
[INFO DRT-0267] cpu time = 05:12:40, elapsed time = 00:21:03, memory = 9,842 MB.- 1L3Pin access first. Zero pins lacking access points is a precondition for convergence; any nonzero count needs a placement fix.
- 2L8Iteration 0 is the first complete route. Thousands of violations here are normal.
- 3L14Shorts dominate early: nets routed independently overlap, then repair separates them.
- 4L16A big drop after one search-and-repair pass. Inside each clip, workers rip up nets near markers and reroute them with marker costs added.
- 5L22The long tail: 31 violations left after eight iterations.
- 6L24Line ends, spacing and shorts on M2 and M3, at pins. If they cluster on one cell type or one macro edge, more iterations won’t help.
- 7L30Converged. Routed wirelength is about 4% above the global estimate.
- 8L31Fewer vias than the global router’s count, after real layer choices. Next comes redundant-via insertion.
Finally, part of the routed DEF. Each net lists its pins, then its wiring: a layer, a series of points (an asterisk repeats the previous x or y), and via names at points where the route changes layer. NEW starts a separate segment on the same net.3
VERSION 5.8 ;
DESIGN top ;
UNITS DISTANCE MICRONS 1000 ;
DIEAREA ( 0 0 ) ( 200000 200000 ) ;
TRACKS Y 100 DO 1000 STEP 200 LAYER M1 ;
TRACKS X 100 DO 1000 STEP 200 LAYER M2 ;
TRACKS Y 100 DO 1000 STEP 200 LAYER M3 ;
TRACKS X 200 DO 500 STEP 400 LAYER M4 ;
NONDEFAULTRULES 1 ;
- CLK_2S
+ LAYER M4 WIDTH 200 SPACING 400
+ LAYER M5 WIDTH 200 SPACING 400 ;
END NONDEFAULTRULES
NETS 3 ;
- n1043 ( U1023 ZN ) ( U1188 A1 ) ( u_alu/U88 D ) + USE SIGNAL
+ ROUTED M1 ( 48300 10500 ) VIA12_1C
NEW M2 ( 48300 10500 ) ( * 15300 ) VIA23_2C
NEW M3 ( 48300 15300 ) ( 61700 * ) VIA23_2C
NEW M2 ( 61700 15300 ) ( * 12100 ) VIA12_1C
NEW M3 ( 52200 15300 ) VIA34_1C
NEW M4 ( 52200 15300 ) ( * 60500 ) VIA34_1C
NEW M3 ( 52200 60500 ) ( 130100 * ) ;
- clk_leaf_7 ( CTS_BUF_12 Z ) ( u_alu/U88 CK ) ( u_alu/U90 CK )
+ USE CLOCK + NONDEFAULTRULE CLK_2S + SHIELDNET VSS
+ ROUTED M4 ( 96200 58100 ) ( * 61900 ) VIA45_2C
NEW M5 ( 96200 61900 ) ( 130100 * ) ;
- n2210 ( U2210 ZN ) ( ANT_DIODE_3 A ) ( U2290 B ) + USE SIGNAL
+ ROUTED M2 ( 70300 34100 ) ( * 36500 ) VIA23_1C
NEW M3 ( 70300 36500 ) ( 72200 * ) VIA34_1C
NEW M4 ( 72200 36500 ) ( * 88100 ) ;
END NETS- 1L5M1 tracks: horizontal (Y positions), 0.2 µm pitch, offset 0.1 µm. The router’s grid comes from LEF PITCH and OFFSET.
- 2L6M2 runs vertically, so its tracks are X positions. Directions alternate up the stack.
- 3L8M4 has twice the pitch: upper layers are wider and less resistive.
- 4L10A non-default rule: double spacing on M4 and M5 for clock nets to cut coupling.
- 5L16Wiring starts on M1 at the driver pin and immediately climbs through a via to M2.
- 6L17A vertical M2 segment; the asterisk keeps x = 48300. VIA23_2C is a double-cut via, inserted for yield.
- 7L20NEW starts a separate branch of the same net, here a Steiner branch point at x = 52200.
- 8L21An M4 vertical carries the branch north; upper layers have wider pitch and lower resistance.
- 9L24This clock net uses the NDR and is shielded by VSS wiring defined in SPECIALNETS.
- 10L27An antenna diode cell was added to this net by repair_antennas, close to the gate it protects.
- 11L28The route leaves M2 after a short stub and finishes on M4, which keeps the M2 antenna ratio low.
Lower layers: 4 GCells overflow, clustered at the macro corner and over a dense group of cells. A cluster like this rarely clears in detailed routing.
Iteration 0, the first complete route: 18,412 violations, mostly shorts where nets overlap. Normal at this point.
- Wire traffic jams. Too many wires need to pass through one area, and they won’t all fit. The real fix is usually to spread the parts out.
- Mistakes that won’t go away. A few broken rules can refuse to clear, often in crowded corners. Running the router longer rarely helps.
- Slower than expected. Real wires are longer than the guesses. A signal that was just on time before routing can arrive late after.
- Noisy neighbors. Long side-by-side wires can nudge each other and cause wrong values.
- Ignoring leftover overflow. Overflow left after global routing can turn into detours or rule violations in detailed routing. Fix it earlier: tell the global router to assume fewer tracks, keep a margin clear around large blocks, block off crowded areas partly, or spread the cells out.41
- Crowded lower layers. Pins, short local vias and power rails all compete for the lowest layers. Without reducing the capacity the global router assumes there, its plan looks fine and the detailed router then chokes.4
- Unreachable pins. Cells with many pins packed tightly together can leave some pins with no legal way in. Each pin’s access has to work both inside its own cell and alongside the neighboring cells.11 The detailed router reports pins without access early; the usual fix is to leave a little space around those cells or move them.
- Timing gets worse after routing. Detours, vias and coupling add delay that the estimates made during placement missed. Check timing on the global route first. Then extract the routed layout to SPEF and check timing again with that.8
- Antenna fixes undone. Filler cells must be removed before protective diodes can be inserted, and put back after.4 Diodes inserted on the global route also need a recheck after detailed routing, because the final wires may differ.
- Special rules everywhere. Wide or extra-spaced wiring on too many nets uses up the tracks other nets need.19
- Violation counts that stop falling. A residue of violations that survives iteration after iteration is usually structural: pins with no legal access, a clash between neighboring cells’ edges, a pinch point at a macro edge, or an overfilled GCell. Group the markers by cell type and location before spending more iterations on them.
- Global and detailed disagree. The coarse model ignores pin access, via overhead and how rules interact, so zero overflow doesn’t guarantee a clean detailed route. Per-layer capacity adjustments cut the tracks the global router assumes, which spreads routing and lowers peak congestion to ease detailed routing.4 Use them together with macro extension, and compare how well the final wiring stayed inside the guides.
- Crosstalk surprises at signoff. Timing that looked clean before routing can lose slack to crosstalk-induced delay on a few long parallel runs. Switch factors that understate the worst case make it worse.17 Run crosstalk-aware timing from the first complete route onward.
- Extractors that disagree. The router’s internal estimates, OpenRCX or another fast extractor, and the foundry’s signoff extractor all give different numbers. Calibrate the rules files for each corner and compare the extractors early.8
- Coloring conflicts. On double-patterned layers a route can form an odd-length conflict cycle with its neighbors. Decomposition can fix it only by splitting a shape; if no split works, the layout must change.22
- Hidden resistance. Moving a net up the stack helps only if the via stack it needs is cheap, since every via adds delay.19 Via pillars cut that resistance on critical paths but use routing resources.24
- ECO damage. Late ECOs that rely on distant spare cells add long wires, timing violations and congestion.25 A reroute also changes the coupling of the untouched nets around it.8 Re-extract and rerun crosstalk-aware timing after every ECO.
Abutted cells: the edge pins can only be reached from neighboring tracks, and their vias would clash. Cell B’s pin 1 has no legal access. Tap a pin.
This part goes deeper, into the math, models and algorithms behind the chapter. It’s written for the Expert level.
Maze routing: Lee and its descendants
C. Y. Lee’s 1961 paper posed wiring as a path-connection problem on a grid and solved it by wave expansion.12 Step by step:
- Label the source cell 0.
- Label every free neighbor of a cell labeled with , so a “wave” of labels spreads out.
- Stop when the wave reaches the target.
- Trace back from the target, always stepping to a neighbor with a label one lower.
This is breadth-first search, so it is guaranteed to find a minimum-cost path whenever one exists.9 The price is time and memory proportional to the area of grid searched. Early improvements cut both. Akers observed that a repeating 2-bit code is enough to store the labels. Waves can be grown from source and target at once. And the search can be confined to a box 10–20% larger than the one around the two pins, enlarged only if it fails.13
Hadlock (1977) labels cells by detour number : the number of steps on the path that point away from the target. Path length is then the Manhattan distance plus , so minimizing detours still finds a shortest path while searching far fewer cells. Soukup (1978) runs a straight line toward the target and falls back to Lee-style expansion only to get around obstacles. It is 10–50× faster than Lee but may miss the shortest path.13 A* adds to each node’s cost an estimate of the distance still to go, and always expands the most promising node first; bidirectional A* searches from both ends.1 Once steps have different costs (vias, wrong-way steps, congestion), plain breadth-first expansion no longer finds the cheapest path, and routers use Dijkstra’s algorithm or A* instead.1
Line-probe routers
Line-probe routers search with line segments instead of grid cells. Mikami and Tabuchi (1968) extend lines from the source and the target and treat every grid point on a line as an escape point from which a new perpendicular line can start. Hightower (1969) keeps a single escape point per line segment; when a line runs alongside blocked cells, the escape point goes just past the end of the segment.13 Line search uses less time and memory than Lee’s algorithm and A*.9
Steiner trees
Nets with more than two pins need trees. Constructing a rectilinear Steiner minimum tree is NP-hard: no known method finds the optimum quickly for every case. Some structure helps. An RSMT for pins has at most Steiner points, each joining 3 or 4 branches, and lies inside the pins’ bounding box.1 Hanan’s theorem says candidate Steiner points can be limited to the crossings of horizontal and vertical lines drawn through the pins.131 In practice, FLUTE uses precomputed lookup tables to find RSMTs for nets with fewer than 10 pins very quickly. FastRoute uses FLUTE to build its initial trees, then reshapes them around congestion.15
Spanning tree over the pins only: length 19. Wires may join only at pins. Switch to the Steiner tree.
Global routing as an optimization problem
Formally, global routing packs one Steiner tree per net into a graph whose edges have capacities, and even simple special cases are NP-hard.15 The textbook integer linear program (ILP) gives each net a small set of candidate routes, with a 0-or-1 variable for each, requires exactly one route per net, and caps the number of routes using any edge at its capacity. It is convenient but slow, and may not scale to the largest netlists without dividing the chip into regions.1
Letting the variables take fractional values turns this into a multicommodity flow problem, one “commodity” per net sharing the edge capacities. That problem has fully polynomial approximation schemes: algorithms that get within any chosen margin of the optimum in reasonable time. Randomized rounding then turns the fractional answer back into one route per net, overshooting capacities only slightly when edges have enough capacity.15 Carden, Li and Cheng applied this in 1996, minimizing edge congestion rather than wire length, and showed that under certain conditions the result comes within a computable bound of the optimum.16 Vygen describes a generalization, min-max resource sharing, in which timing, power and yield loss join edge capacity as resources to share.15
Negotiated congestion
Routing nets one at a time makes the result depend on their order: early nets grab resources that later nets need. Rip-up and reroute lets nets overlap for a while and then reroutes the ones in conflict.1 McMurchie and Ebeling’s FPGA router (1995), known as PathFinder, added the piece that makes it settle. The cost of using node is :
- is a base cost, such as the node’s own delay;
- grows with the number of other nets using right now;
- , the history term, grows a little in every iteration in which is overused, and never shrinks.
Every net is ripped up and rerouted in every iteration. Over time the history term makes chronically contested resources permanently expensive, so nets with alternatives leave and the net that needs the resource most keeps it. Timing-critical nets weight delay more heavily than congestion.14 Modern ASIC global routers use the same idea on edges: the cost of an edge rises with its congestion, the number of nets crossing it divided by its capacity.1 FastRoute adds virtual capacity, pattern and monotonic routing, and multi-source multi-sink maze routing on top.5
Three nets, three nodes, each node holds one net. B is cheap (b = 1) and every net can use it; A and C cost 3. Net 2 has no other option. Press Next for iteration 1.
TritonRoute’s detailed routing
The 2018 TritonRoute targeted the ISPD-2018 routing contest with a mixed integer linear program (MILP). It routed each layer as a set of parallel panels, first the even-numbered panels and then the odd-numbered ones, working up from the bottom layer, and beat the contest’s first-place results by 50% on average on the contest’s scoring metric.10 The open-source router in OpenROAD was rebuilt from scratch for an industrial-style flow.6 Its stages:
- Pin access analysis. For each unique instance, generate access points and directions that obey the design rules, then use dynamic programming to pick combinations that are compatible within the cell and with its neighbors.11
- Track assignment. A simplified greedy assignment on panels 50 GCells across, horizontal layers first and then vertical, followed by one reassignment pass.9
- Clip-based search and repair. Each iteration splits the die into 7×7-GCell clips. A worker per clip copies in its region, routes with A* on a 3D grid graph, runs a rule check, and rips up and reroutes until the clip is clean or its own iteration budget runs out. Then it commits its result. Alternate iterations offset the clips by 0 and −4 GCells.9
- Costs that encode rules. Object costs are added to the graph edges near each shape, covering spacing that depends on parallel run length, end-of-line spacing and cut spacing, and are removed with the shape. Marker costs are added around each reported violation and fade over the worker’s rip-up rounds without being removed. That history lives only inside the worker and steers its rerouted nets away from trouble spots.9
On the ISPD-2018 benchmarks it improved on the best published academic results by 0.4% in wire length, 9.3% in via count and 92.0% in rule violations, on average.9 Path search itself is old and well understood. The engineering problems are the rule model, pin access, splitting the work for parallel workers, and cost schedules that turn rip-up and reroute into convergence.
Q1On one wiring layer, 15 tracks cross the border between two tiles of the global router’s grid. A power wire blocks 3 of them, and 14 nets want to cross. What is the overflow on that border?
Q2Why do neighboring metal layers run in alternating directions (one horizontal, the next vertical, and so on)?
Q3While the M2 layer is being etched, a long M2 wire connected only to a transistor’s gate collects enough electric charge to damage it. This is an antenna violation. Which fix works?
Q4What does a SPEF file hold, and where does it come from?
Sources
Show Hide 25 sources
- VLSI Physical Design: From Graph Partitioning to Timing Closure, Chapter 5 slides (Global Routing)GCell grid graph with edge capacities; ILP and rip-up-and-reroute; pattern routing; negotiated congestion; RSMT properties, Hanan grid, FLUTE; net pin-count statistics.
- VLSI Physical Design: From Graph Partitioning to Timing Closure, Chapter 6 slides (Detailed Routing)Detailed routing stages (track assignment, routing, search and repair, redundant vias); preferred-direction enforcement; via doubling and antenna limits.
- LEF/DEF Language Reference, Product Version 5.7LAYER DIRECTION and PITCH (generates DEF TRACKS), AREA, ENDOFLINE spacing, cut ENCLOSURE, NONDEFAULTRULE, MINCUTS, ANTENNACELL, antenna ratios and fixes, DEF ROUTED/NEW wiring.
- Global Routing (grt)FastRoute-based global_route; default GCell 15 M3 pitches; 50 congestion iterations; layer adjustment; critical-net priority; repair_antennas diode insertion.
- FastRouteRip-up and reroute; FLUTE-based congestion-driven Steiner trees; pattern, monotonic and maze routing; virtual capacity; via-aware Steiner trees and layer assignment.
- Detailed Routing (drt)TritonRoute-based: pin access analysis, track assignment, initial detailed routing, search and repair, DRC engine; -droute_end_iter up to 64; -output_drc.
- Antenna Rule Checker (ant)check_antennas; partial (PAR) and cumulative (CAR) area ratios computed by walking the wire graph from each gate.
- Parasitics Extraction (rcx)OpenRCX extracts wire R, coupling C and ground C using a per-node, per-corner rules file and writes SPEF.
- TritonRoute: The Open Source Detailed RouterTrack assignment, 7×7 GCell clips with shifted offsets, A*-based worker routing, object and marker (history) costs; vs. best academic results: vias −9.3% and DRCs −92.0% on average.
- TritonRoute: An Initial Detailed Router for Advanced VLSI TechnologiesFirst TritonRoute: MILP-based routing of parallel panels, layer by layer; contest metric 50% better on average than the ISPD-2018 first-place results.
- The Tao of PAO: Anatomy of a Pin Access Oracle for Detailed RoutingPin access as a crucial advanced-node issue; access points and patterns; dynamic-programming-based, design-rule-aware pin access analysis per unique instance.
- Routing lecture slides (lec06-2), including the Lee maze-routing algorithmLee’s 1961 maze router (IRE Trans. Electronic Computers): finds a path from S to T by wave propagation, guaranteed to find a connection and a minimum path, at O(MN) time and space.
- Routing lecture slides (lec06-3)Lee memory and runtime reductions; Hadlock detour number; Soukup; Mikami–Tabuchi and Hightower line-probe routers; global routing formulation; Hanan’s theorem.
- Placement and Routing Tools for the Triptych FPGAMcMurchie and Ebeling’s negotiated-congestion router: node cost (b + h)·p with a history term that permanently raises congested nodes’ cost; sharing penalty raised gradually; every net rerouted every iteration; critical connections get more weight.
- Global Routing (lecture slides)Global routing as Steiner tree packing; NP-hard even in simple cases; multicommodity-flow relaxation and randomized rounding; coupling capacitance vs. spacing; spreading for yield.
- A Global Router with a Theoretical Bound on the Optimal SolutionGlobal routing as multiterminal multicommodity flow, minimizing congestion, with randomized rounding to integer routes.
- On Switch Factor Based Analysis of Coupled RC InterconnectsCrosstalk causes functional noise and delay change; switch factors of 0–2 in standard flows, worst case 3 for ramp inputs; coupling can equal area plus fringe capacitance.
- Simultaneous Shield Insertion and Net Ordering for Capacitive and Inductive Coupling MinimizationSame-layer coupling exceeds ground capacitance; net ordering (track assignment) and shield insertion reduce noise.
- MiniDelay: Multi-Strategy Timing-Aware Layer Assignment for Advanced Technology NodesUpper layers are wider and less resistive, so critical nets go up; NDR wires as wide or parallel wires; lower layers allow only parallel-wire NDRs.
- Antenna effectPlasma etching charge on gate-connected metal; per-layer and cumulative metal-to-gate area ratios; fixes by jumping to a higher layer or adding diodes.
- Multiple patterningLELE pitch splitting, spacer-based SADP and SAQP; 36 nm metal pitch by SAQP as of 2017.
- Layout Decomposition for Double Patterning LithographyFeatures closer than the coloring spacing need opposite masks; odd conflict cycles are not 2-colorable and force splits.
- Backside power deliveryPower interconnect takes at least 20% of routing resources; buried power rails cut Mint tracks; 15–20 BEOL layers with narrow, resistive lower wires.
- Method and circuit for via pillar optimization (US 9,977,857 B1)A via pillar is multiple vias arranged in parallel and symmetrically; used to cut via resistance at a driver output and so wire delay; costs space and routing resources and complicates routing.
- Resource-Aware Functional ECO Patch GenerationMetal-only ECOs rewire spare cells after placement is frozen; distant spares mean long wires, timing violations and congestion.