Introduction
As semiconductor manufacturing advances toward 11nm and sub-10nm nodes, traditional single-exposure lithography faces insurmountable physical limitations. Features at these scales are positioned too closely to be printed accurately in one pass. To overcome this, Multiple Patterning Lithography (MPL) has emerged as a critical solution, splitting dense layouts into several sparser masks that are printed sequentially.
This paper introduces a comprehensive framework for Layout Decomposition in Quadruple Patterning Lithography (QPL). The goal is to assign every feature in a design to one of $K$ masks (where $K=4$ or more) while minimizing manufacturing conflicts—where features on the same mask are closer than the minimum coloring distance—and "stitches," which occur when a single feature must be split across masks, potentially impacting yield.
A Multi-Pronged Decomposition Framework
The proposed framework addresses the NP-hard complexity of QPL through a structured pipeline that balances optimality with computational efficiency. The process begins with graph construction and division before proceeding to sophisticated color assignment algorithms.
1. Graph Representation and Division
The layout is first modeled as a graph where vertices represent polygonal shapes. "Conflict edges" connect shapes that violate distance constraints, while "stitch edges" denote potential split points. To handle large-scale designs, the authors employ Gomory-Hu (GH) trees to identify "3-cuts." These cuts allow the graph to be divided into independent components that can be solved separately and merged using a "color rotation" technique to maintain global consistency.
2. SDP-based Color Assignment
For high-quality results, the framework utilizes Semidefinite Programming (SDP). In this approach, the four available colors are mapped to four unit vectors in 3D space. By maximizing the distance between vectors representing adjacent vertices, the solver identifies a continuous solution that is subsequently mapped back to discrete mask assignments using a backtrack-based refinement.
3. Linear Color Assignment
Recognizing that SDP can be computationally intensive for massive layouts, the authors developed a Linear Color Assignment heuristic. This three-stage process involves simplifying the graph through vertex removal, applying greedy assignment rules based on "color-friendly" patterns, and performing a final post-refinement pass. This method offers a significant speedup while maintaining acceptable conflict levels.
Key Insights and Results
Modern dense layouts are often "non-planar," containing complex sub-structures like $K_5$ cliques that cannot be resolved by the classic Four-Color Theorem alone. The authors found that in these ultra-dense environments, "color-friendly" rules—where certain nearby features are intentionally assigned the same color—can actually reduce overall conflicts by freeing up space for other neighbors.
Experimental evaluations using industry-standard benchmarks (scaled to 20nm half-pitch) demonstrated the framework's effectiveness:
- Scalability: The SDP+Backtrack method provided near-optimal solutions in minutes, whereas traditional Integer Linear Programming (ILP) solvers frequently timed out.
- Efficiency: The Linear Color Assignment algorithm achieved a 200x speedup over the SDP approach with only a marginal (15%) increase in conflicts.
- Future-Proofing: The framework successfully extended to Pentuple Patterning ($K=5$), where the Linear algorithm proved particularly robust in minimizing conflicts for ultra-dense designs.
Conclusion
This work provides the first comprehensive solution for QPL layout decomposition, offering a vital tool for sub-10nm chip manufacturing. While the Linear algorithm presents a trade-off by introducing slightly more stitches, its speed and scalability make it a viable candidate for future technology nodes. Future research may focus on "decomposition-aware" physical design to further minimize native conflicts before the decomposition stage begins.
Summary updated