We have successfully developed a triple patterning decomposition methodology that can effectively decompose an entire layout block or a chip. Formulating a triple patterning decomposition problem into a graph 3-color problem, the system first builds a graph to represent the layout. It then tries to reduce and partition the graph without changing its 3-colorability property. To color the reduced graph, we adopt a hybrid approach with a fast heuristic for coloring and an exact coloring algorithm for backup and conflict verification.
Unlike an odd cycle in double patterning, a triple patterning coloring conflict can’t be represented in a single loop. Another challenge for triple patterning is then how to report errors that the user can effectively use to fix them. For this purpose, minimum fix guidance – minimum to fix a conflict, and maximal minimum fix guidance – maximal choices are presented.
