Synopsys, Inc.
HYBRID EVOLUTIONARY ALGORITHM FOR TRIPLE-PATTERNING

Abstract:

A method is presented for layout decomposition including creating a first graph representative of an integrated circuit layout to be multiple-patterned, when a computer is invoked to decompose the layout, and decomposing each of a first subset of a multitude of sub-graphs into at least three sets when a valid coloring solution is returned for the layout. The multitude of sub-graphs is created from the first graph by dividing the first graph. The method further includes approximately decomposing each of the first subset into at least three sets using a hybrid evolutionary algorithm when the hybrid evolutionary algorithm does not return a valid coloring solution for the layout, and forming a colored graph representative of the layout by merging the at least three sets to generate one of at least three colors for each one of a multitude of vertices of the first graph.