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

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.