Comparison of triple patterning decomposition algorithms using aperiodic tiling patterns

Double patterning has gained prominence as the most likely methodology to help keep Moore's law going towards 22nm 1/2 pitch lithography. However, most designs cannot be blindly shrunk to run using only two patterning layers and a variety of constraints must be imposed on designs to allow for correct decomposition. These constraints are more onerous for the contact layer than for line/space patterns because they more easily form odd cycles on the 2D plane, which cannot be broken using polygon cutting. As this can adversely limit packing density, especially in bit cells, a triple patterning decomposition capability could be attractive for the contact layer. Pattern decomposition for contacts can be likened to coloring a map where minimum spaces between contacts are replaced with borders. It is well known that 4 colors can color any map [5,6], but it is an NP-complete problem to compute the minimum number of colors needed to color any given map [7]. This should place an upper limit on the scalability of any algorithm able to color large networks. A variety of test patterns that are known 3-colorable are needed to compare suitable algorithms. It has been proved that a set of aperiodic tiling known as "Penrose Tiles" is 3-colorable [8]. This paper compares the scalability of different coloring algorithms using a variety of contact patterns based on Penrose Tiles.