TL;DR
As semiconductor manufacturing pushes to smaller nodes (14nm and beyond), triple patterning lithography (TPL) becomes essential but presents significant layout decomposition challenges. This paper introduces an iterative "layout compliance" framework that combines automatic decomposition with targeted manual modification, aiming to accelerate the design closure process and ensure TPL-friendly layouts.
What Problem Does This Paper Address?
The relentless scaling of semiconductor manufacturing to 14nm and beyond necessitates advanced lithography techniques like triple patterning lithography (TPL) to print smaller features. A critical bottleneck in TPL is layout decomposition, the process of dividing a design's geometric patterns into multiple masks. This decomposition is an NP-hard problem, meaning finding an optimal solution is computationally intractable for large designs. Traditional approaches involve iterative cycles of automatic decomposition and manual designer intervention. However, these methods are slow and can leave designers with many unresolved conflicts, hindering design closure. This paper addresses the need for a faster, more efficient, and designer-friendly approach to achieve TPL-compliant layouts by integrating layout modification directly into the decomposition flow.
Methods
The authors propose a novel iterative layout compliance framework that goes beyond traditional layout decomposition. The core of their approach involves three main steps:
- Fast Initial Layout Decomposition: This step uses a linear-time algorithm (inspired by previous work) to perform an initial color assignment of layout patterns to masks. Unlike more computationally expensive methods like Integer Linear Programming (ILP) or Semidefinite Programming (SDP), this initial decomposition is very fast. It aims to assign colors while identifying potential conflicts.
- Layout Modification (Native Conflict Removal): The initial decomposition can identify specific "native conflicts," often arising from local structures like four-cliques. Designers can then manually modify the layout to resolve these specific issues. The framework is designed to help designers pinpoint these problematic areas and suggests modifications.
- Incremental Layout Decomposition (Color Re-assignment): After manual modifications, the framework performs incremental re-assignment of colors in localized regions. This step efficiently resolves any remaining conflicts without re-processing the entire chip, making the process much faster than starting from scratch.
Key to their approach are two strategies for the initial decomposition: "color-friendly rules" which leverage observed patterns in dense layouts, and "peer selection" which processes multiple coloring orders simultaneously to find a better solution.
Datasets
Not discussed in the paper. The paper focuses on a general framework and algorithms, demonstrating its application with examples and referencing existing industrial practices.
Key Insights and Ideas
- TPL is fundamentally different from DPL: Unlike double patterning, where conflict and stitch minimization can be done sequentially, TPL requires a more integrated approach because detecting TPL compliance itself is NP-hard. There's "no shortcut any more."
- Native conflicts are key: The paper highlights that many TPL conflicts, especially "native" ones, stem from local geometric structures (like four-cliques), not just long chains of features as in DPL. This localization offers opportunities for targeted fixes.
- Iteration is crucial, but needs to be smart: The traditional iterative approach is necessary due to NP-hardness, but the authors' innovation lies in making these iterations incremental and integrating layout modification to accelerate convergence.
- Designer-friendliness matters: The framework aims to provide designers with actionable information (identifying conflicts and suggesting fixes) rather than just a list of unresolvable problems.
Key Results
The paper emphasizes the efficiency and speed of their proposed framework. They claim their initial layout decomposition has linear runtime complexity, making it significantly faster than ILP or SDP-based methods, especially for large designs. While not providing specific quantitative speedup numbers for the entire framework in the abstract, they state that their incremental approach allows for quick solutions for selected portions of the layout after modifications. Figure 12 visually supports this claim, showing their method's runtime scaling much better with the number of nodes compared to ILP and SDP. They also demonstrate the framework's ability to remove "four-clique structures" and show an example of its application in a cache array for a MIPS microprocessor.
Limitations and Future Work
- NP-hardness remains: The fundamental NP-hardness of the problem means that optimal solutions are still not guaranteed, and the framework relies on heuristics and approximations.
- Designer intervention: While the framework aims to reduce manual effort, it still relies on designers to perform layout modifications for native conflicts. The paper doesn't quantify the extent of this intervention.
- Future Work: The authors believe their work will "stimulate more future research into the layout compliance problem," suggesting that further advancements in iterative decomposition and integrated layout modification are needed. They also mention the need for better trade-offs between runtime and solution quality, which is a persistent challenge in this field.
Summary updated