Multi-Patterning Aware Routing (MPO Routing) is the physical design routing methodology that assigns wires to specific lithographic masks (colors) while ensuring no two segments of the same color violate the minimum pitch of their shared patterning step — extending routing algorithms from two-dimensional wire placement to color-aware three-dimensional assignment that satisfies both electrical design rules and lithographic patterning constraints simultaneously. At 14nm and below, every critical metal layer uses SADP or SAQP, making MPO-aware routing essential for tapeout.

Multi-Patterning Coloring Fundamentals

• SADP creates alternating mask 1 (mandrel) and mask 2 (spacer) features.
• Two wires at minimum SADP pitch must be on DIFFERENT colors (different exposure steps).
• Two wires on the same color must be separated by at least 2× minimum pitch.
• Coloring problem: Assign color (mask ID) to each wire segment such that no same-color conflict exists.

Coloring Conflicts

• Same-layer conflict: Two segments too close (<2× min pitch) assigned same color → litho failure.
• Self-conflict: A single wire loop has an odd number of segments → cannot be 2-colored → requires a cut (extra mask).
• Odd cycle: 3 wires A-B-C where A conflicts with B, B conflicts with C, and C conflicts with A → odd cycle → requires cut mask.

Routing with MPO Constraints

Stage 1: Global Routing

• Route without color assignment — only connectivity and layer assignment.
• Estimate coloring complexity for each routing region → guide detailed routing.

Stage 2: Detailed Routing + Coloring

• Assign wires to tracks → simultaneously assign colors.
• Algorithm: Graph coloring → assign 2 colors such that adjacent segments have different colors.
• If graph is bipartite (all even cycles) → 2-colorable with no cuts.
• If graph has odd cycle → must add cut (reroute or insert a jog) to break odd cycle.

Cut Masks

• Cut mask: An additional lithography step that cuts (breaks) a spacer wire into two segments → resolves odd-cycle conflict.
• Each cut = one additional mask and etch step → adds cost.
• Design objective: Minimize cut count → reduce mask cost and complexity.
• EDA tools: Coloring + cut-minimization algorithms run during detailed routing or post-routing ECO.

SAQP Routing (4-Coloring)

• SAQP uses 4 different masks → 4-color problem.
• More flexible than SADP but more complex to assign.
• Track-based routing: Predefined color-to-track assignment (e.g., tracks 1,5,9... = color A; 2,6,10... = color B; etc.).
• Fixed-color track assignment simplifies routing but constrains which tracks routers can use.

Layer Assignment for MPO

• Different metal layers have different patterning schemes.
• M2/M3: SADP (2 colors); M4/M5: SADP; M6+: Single exposure (no coloring needed).
• Via between MPO layers: Must satisfy color rules at both layers → via-to-wire color compatibility check.

Design Rules for MPO

EDA Tool Support

• Cadence Innovus, Synopsys ICC2: Full MPO-aware routing with color assignment.
• Mentor Calibre: MPO DRC checking → detects same-color conflicts, odd cycles, un-resolvedcuts.
• Decomposition: Post-routing tool separates colored GDS into per-mask GDS files for mask house.

MPO-aware routing is the lithographic constraint that fundamentally changed physical design at advanced nodes — by forcing routing algorithms to simultaneously solve wire placement and coloring for multi-patterning, MPO routing transforms a two-dimensional problem into a higher-dimensional optimization that determines not just whether nets connect but whether the mask set can physically print the design, making color-aware routing a non-optional capability for any EDA flow targeting 7nm and below.