Non-Default Rules and Multi-Patterning-Aware Routing

The idea

Default routing assumes every wire is minimum width at minimum spacing. Two departures from that assumption are routine at advanced nodes, and both change what the router must model.

A non-default rule (NDR (Non-Default Rule)) is a named rule set (width, spacing, via choice) attached to chosen nets. Wider wire has lower resistance; wider spacing has lower coupling. The router must honour the rule in its search: an NDR (Non-Default Rule) net blocks the neighbouring tracks its spacing requires and consumes several nets' worth of capacity.

Multi-patterning arises when the wire pitch is below what one lithography exposure can print. With LELE (Litho-Etch-Litho-Etch) double patterning, one layer is printed as two masks, and any two shapes closer than the single-mask pitch must be on different masks:

• coloring distance the spacing below which two shapes cannot share a mask; above it, mask choice is free
• the layout's shapes and these adjacencies form a conflict graph; the layer is manufacturable only if that graph is 2-colorable (bipartite)

An odd cycle in the conflict graph cannot be colored no matter how the masks are assigned. The smallest is a triangle: three shapes each within the coloring distance of the other two, for instance two wires on adjacent tracks plus a third shape that runs beside one of them on a neighbouring track and ends too close to the other on its own track. Every spacing rule can be satisfied while the coloring is impossible; the router must avoid closing such cycles. SADP (Self-Aligned Double Patterning) removes the coloring problem by defining the pitch with a deposited spacer, at the price of confining wires to a fixed one-dimensional grid with heavy restrictions on jogs and wrong-way segments. The figure below walks through both processes and what each looks like from the router's side:

The recipe

Step 1 (assign rules). Attach NDRs (Non-Default Rules) to the nets that need them: clocks, timing-critical or noise-sensitive signals. Ration them; each costs the capacity of several default nets.

Step 2 (route with widened footprints). In the search, an NDR (Non-Default Rule) net occupies its width plus its spacing halo; it tapers to default width only to reach minimum-size pins.

Step 3 (route coloring-aware). On multi-patterned layers, track the conflict graph as segments are placed; price or forbid moves that would create an odd cycle. Assign masks (color) at the end, or leave the layout provably colorable for the mask tool.

Watch it work: rules and colors on one layer

Default tracks, then an NDR (Non-Default Rule) wire and its footprint, then the same tracks under two-mask coloring: alternating masks, an odd-cycle conflict, its resolution by re-routing, and the SADP (Self-Aligned Double Patterning) alternative.

Pros, cons, and the trade-off

Is it actually used today?

The evidence for non-default rules and multi-patterning-aware routing comes from the LEF (Library Exchange Format) and DEF (Design Exchange Format) standards, open-source router support, and the requirements of advanced-node processes.

• Open source: NDRs (Non-Default Rules) are part of the LEF (Library Exchange Format) and DEF (Design Exchange Format) standards, and TritonRoute honours NONDEFAULTRULE nets in its search; the open-source flow does not target multi-patterned nodes, so coloring-aware routing has no open reference implementation.
• Commercial: documented for NDRs (rule definition and per-net assignment are standard flow steps). Coloring-aware routing is required at every LELE (Litho-Etch-Litho-Etch) node and is documented at the feature level; the internal conflict-graph handling is proprietary.
• The process: every node below roughly 20 nm has used some form of multi-patterning on its densest layers until EUV (Extreme Ultraviolet) lithography relaxed it on some layers; the routing constraint follows the process.