Method for performing pattern decomposition for a full chip design

A non-transitory computer readable storage medium having stored thereon a computer program for decomposing a target pattern containing features to be printed on a wafer, into multiple patterns, when executed, causing a computer to perform the steps of:

• segmenting said target pattern into a plurality of patches;
• for each of said plurality of patches, identifying critical features within each patch which violate minimum spacing requirements;
• identifying one or more critical groups in each patch having identified critical features, wherein said critical groups respectively comprise a plurality of features including one or more of said identified critical features;
• generating a critical group graph for each of said plurality of patches having critical features, said critical group graph of a given patch linking together the critical groups and thereby defining a coloring scheme for said critical groups in said given patch, wherein said respective plurality of features within a single critical group share the same color;
• identifying critical groups in said plurality of patches that have features extending into adjacent patches;
• generating a global critical group graph for said target pattern, including stitching together said critical group graphs of each of said plurality of patches, and inserting graph edges between said critical groups that have said features extending into adjacent patches;
• and
• coloring said features in said target pattern in accordance with said global critical group graph by assigning a color to each of said critical groups.

A device manufacturing method comprising the steps of:

• (a) providing a substrate that is at least partially covered by a layer of radiation-sensitive material;
• (b) providing a projection beam of radiation using an imaging system;
• (c) using patterns on masks to endow the projection beam with patterns in its cross-section;
• (d) projecting the patterned beam of radiation onto a target portion of the layer of radiation-sensitive material,
• wherein in step (c), providing a pattern on a mask includes the steps of:
• segmenting a target pattern into a plurality of patches;
• for each of said plurality of patches, identifying critical features within each patch which violate minimum spacing requirements;
• identifying one or more critical groups in each patch having identified critical features, wherein said critical groups respectively comprise a plurality of features including one or more of said identified critical features;
• generating a critical group graph for each of said plurality of patches having critical features, said critical group graph of a given patch linking together the critical groups and thereby defining a coloring scheme for said critical groups in said given patch, wherein said respective plurality of features within a single critical group share the same color;
• identifying critical groups in said plurality of patches that have features extending into adjacent patches;
• generating a global critical group graph for said target pattern, including stitching together said critical group graphs of each of said plurality of patches, and inserting graph edges between said critical groups that have said features extending into adjacent patches;
• and
• coloring said features in said target pattern in accordance with said global critical group graph by assigning a color to each of said critical groups.

A computer-implemented method for forming masks for use in a photolithography process for imaging a target pattern containing features to be printed on a wafer, comprising the steps of:

• segmenting said target pattern into a plurality of patches;
• for each of said plurality of patches, identifying critical features within each patch which violate minimum spacing requirements;
• identifying one or more critical groups in each patch having identified critical features, wherein said critical groups respectively comprise a plurality of features including one or more of said identified critical features;
• generating a critical group graph for each of said plurality of patches having critical features, said critical group graph of a given patch linking together the critical groups and thereby defining a coloring scheme for said critical groups in said given patch, wherein said respective plurality of features within a single critical group share the same color;
• identifying critical groups in said plurality of patches that have features extending into adjacent patches;
• generating a global critical group graph for said target pattern, including stitching together said critical group graphs of each of said plurality of patches, and inserting graph edges between said critical groups that have said features extending into adjacent patches;
• and
• coloring said features in said target pattern in accordance with said global critical group graph by assigning a color to each of said critical groups,
• wherein one or more of the steps of segmenting, identifying, generating a critical group graph, generating a global critical group graph and coloring are implemented using a computer.