On Coloring and Colorability Analysis of Integrated Circuits with Triple and Quadruple Patterning Techniques

The continued delay of higher resolution alternatives for lithography, such as EUV, is forcing the continued adoption of multi-patterning solutions in new technology nodes, which include triple and quadruple patterning using several lithography-etch steps. In the design space each pattern of a multi-patterning solution is modeled as a color on a shape. Designers or EDA tools must determine the colors that each shape is assigned so that the relative position of any two shapes of the same color does not violate the design rules. This results in a shapes layout coloring problem which is formulated as the traditional k-coloring problem in a graph. Because color interactions cross cell boundaries, coloring of a flat (as opposed to hierarchical) design becomes necessary, tremendously increasing the size of the input graph. If a color conflict occurs, any attempt to fix it may cause a chain reaction propagating through the whole design space which makes any approach of the type color_greedily - fix_conflicts - loop_back infeasible. Given the situation, it is extremely desirable to have a set of design rules which provably guarantee k-colorability and admit a practical coloring algorithm. In this paper we formulate such sets of design rules for triple and quadruple patterning problems. For these sets of rules we provide proofs of colorability along with the coloring algorithms with the runtime upper bound of O(n·log n). We also show that our sets of design rules are almost tight in the sense that even a very small relaxation of the formulated rules leads to existence of not k-colorable designs.