Layout decomposition for Spacer-is-Metal (SIM) self-aligned double patterning

Self-aligned double patterning (SADP) has become a preferred double patterning technology, due to its better overlay controllability. Two types of layout decomposition schemes are used to define two-dimensional layout patterns in SADP: Spacer-is-Metal (SIM) and Spacer-is-Dielectric (SID), and SIM-type layout decomposition typically has higher decomposition flexibility (especially for gridless designs). While SID-type layout decomposition has been studied extensively, however, only one previous work extended a satisfiability-based SID-type decomposer to SIM-type layout decomposition; this SAT-based method is inefficient for large-scale designs and not applicable to non-decomposable layouts. This paper introduces an efficient graph-based SIM-type layout decomposition heuristic. The decomposition problem is first transformed into a constrained set-covering problem. Then, an efficient algorithm composed of a greedy heuristic followed by a partition-based solution refinement scheme is proposed to simultaneously minimize the conflicts on both core masks and cut masks. Experimental results show that the algorithm can efficiently derive a good decomposition solution with minimized pattern conflicts.