multi-patterning decomposition
**Multi-Patterning Decomposition** is a **computational lithography process that mathematically assigns features of a single design layer to multiple sequential lithographic exposures, enabling printing of features below the resolution limit of available lithography tools by splitting dense patterns across color-coded masks** — the enabling technology that extended conventional 193nm DUV lithography through the 14nm, 10nm, and 7nm generations while EUV technology matured to production readiness.
**What Is Multi-Patterning Decomposition?**
- **Definition**: The computational process of partitioning design geometries into K color subsets such that no two same-color features are closer than the minimum single-pattern pitch, with each color group printed by a separate lithographic exposure and etch sequence.
- **Coloring as Graph Problem**: Decomposition is equivalent to graph coloring — features are nodes, conflicts (features too close to print together) are edges, and colors represent masks. Valid decomposition requires no adjacent nodes sharing a color.
- **NP-Hard Complexity**: Graph k-coloring is NP-complete in general; practical algorithms use heuristics and decomposition-aware design rules to make the problem tractable for full-chip layouts.
- **Stitch Points**: Where a single continuous conductor must be split across two masks, "stitches" create overlap regions where both masks print — introducing variability that must be managed by overlay control.
**Why Multi-Patterning Decomposition Matters**
- **Resolution Extension**: LELE (Litho-Etch-Litho-Etch) doubles the printable pitch — a 80nm single-pattern minimum pitch becomes 40nm effective pitch with 2-color decomposition using the same scanner.
- **EUV Delay Mitigation**: When EUV production was delayed by years, multi-patterning at 193nm extended the roadmap through multiple technology generations using installed DUV infrastructure.
- **Cost of Masks**: Each additional mask adds significant cost per wafer layer in production — decomposition must be thoroughly validated before committing to mask fabrication.
- **Design Rule Enforcement**: Decomposability requirements constrain design freedom — designers must follow decomposition-aware rules enforced during physical verification to guarantee manufacturability.
- **Overlay Criticality**: Pattern-to-pattern overlay between different exposure masks is the primary yield limiter — decomposition assignments must minimize sensitivity to overlay errors.
**Multi-Patterning Techniques**
**LELE (Litho-Etch-Litho-Etch)**:
- Pattern mask 1 → etch → pattern mask 2 → etch → final combined pattern.
- Most flexible — any 2-colorable layout works; overlay between mask 1 and 2 is the critical control parameter.
- Widely used for metal layers at 28nm and below; pitch halving with relaxed self-alignment requirements.
**SADP (Self-Aligned Double Patterning)**:
- Mandrel pattern → deposit conformal spacer film → strip mandrel → etch with spacers as mask.
- Pitch halving with superior overlay (spacers are self-aligned to mandrel — no mask-to-mask overlay error).
- Pattern pitch restrictions: most natural for periodic line-space patterns; complex layouts require careful design.
**SAQP (Self-Aligned Quadruple Patterning)**:
- Two successive rounds of SADP — 4× pitch multiplication from original mandrel pitch.
- Used for 7nm and 5nm metal layers targeting 18-24nm effective pitch from 48nm mandrel pitch.
**Decomposition Algorithms**
| Algorithm | Approach | Scalability |
|-----------|----------|-------------|
| **ILP (Integer Linear Programming)** | Exact minimum-stitch solution | Small layouts only |
| **Graph Heuristics** | Fast approximation with retries | Full-chip production |
| **ML-Assisted** | Learned decomposition policies | Emerging capability |
Multi-Patterning Decomposition is **the computational engineering that kept Moore's Law alive** — transforming the physics limitation of optical resolution into a solvable algorithmic problem that enabled semiconductor companies to continue shrinking features for a decade beyond what single-exposure 193nm lithography could achieve, buying time for EUV technology to reach production maturity.