multi patterning routing
**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**
| Rule | Description |
|------|------------|
| Same-color spacing | Segments same color: ≥2 × min pitch |
| Different-color spacing | Segments different color: ≥ 1 × min pitch |
| Color-dependent spacing | Some tools use fixed color → spacing depends on relative color |
| Self-conflict check | Every loop must be even-cycle colorable → DRC check |
**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.