Layout Decomposition and Legalization for Double-Patterning Technology

The use of multiple-patterning (MP) optical lithography for sub-20 nm technologies has inevitably become slow to adopt the next generation of lithography systems. The biggest technical challenge of MP is failure to reach a manufacturable layout-coloring solution, especially in dense layouts. This paper offers a postlayout solution for the removal of conflicts, i.e., patterns that cannot be assigned to different masks without violating spacing rules. The proposed method essentially consists of three steps: 1) layout coloring; 2) exposure layers; 3) geometric rules definition; and 4) layout legalization using compaction and MP rules as constraints. The method is general and can be used for different MP technologies, including lithography-etch, lithography-etch double-patterning (DP), triple patterning/MP (i.e., multiple litho-etch steps), and self-aligned DP (SADP). For demonstration purposes, we apply the proposed method in this paper to remove conflicts in DP. We offer an $O(n)$ layout-coloring heuristic algorithm for DP, which is up to $80\times$ faster than the integer linear program-based approach. The conflict-removal problem is formulated as a linear program, which permits an extremely fast runtime (less than 1 min in real time for macro layouts). The method was tested on standard cells and macro layouts from a commercial 22-nm library designed without any MP awareness. For many cells, the method removes all conflicts without any area increase. For some complex cells and macros, the method still removes all conflicts but with a modest 6% average increase in area.