Multiple patterning layout decomposition considering complex coloring rules

Patent metadata

Field	Value
Publication number	US-2017147740-A1
Application number	US-201615359579-A
Country	US
Kind code	A1
Filing date	Nov 22, 2016
Priority date	Nov 25, 2015
Publication date	May 25, 2017
Grant date	—

Abstract

A computer implemented method for decomposing a layout of a portion of an integrated circuit is presented. The layout includes a first multitude of polygons. The method includes constructing, using the computer, a first matrix representative of a first multitude of constraints. Each of the first multitude of constraints is between a different pair of the first multitude of polygons. The method includes solving, using the computer, the first matrix to thereby assign one of a multitude of masks to each different one of the first multitude of polygons, when the computer is invoked to decompose the layout.

First claim

What is claimed is:

1 . A computer implemented method for decomposing a layout of a portion of an integrated circuit, the layout including a first plurality of polygons, the method comprising:
constructing, using the computer, a first matrix representative of a first plurality of constraints, each of the first plurality of constraints being between a different pair of the first plurality of polygons; and solving, using the computer, the first matrix to thereby assign one of a plurality of masks to each different one of the first plurality of polygons, when the computer is invoked to decompose the layout.

2 . The computer-implemented method of claim 1 , wherein each one of the plurality of masks is associated with multiple patterning lithography.

3 . The computer-implemented method of claim 1 , wherein each one of the first plurality of constraints causes the pair of the first plurality of polygons to be assigned to different ones of the plurality of masks.

4 . The computer-implemented method of claim 1 , wherein the layout includes a second plurality of polygons, the method further comprising:
constructing, using the computer, the first matrix representative of a second plurality of constraints, each one of the second plurality of constraints being different from any one of the first plurality of constraints, wherein each one of the second plurality of constraints causes a pair of the second plurality of polygons to be assigned to different ones of the plurality of masks.

5 . The computer-implemented method of claim 1 , wherein the first matrix is an exact cover matrix.

6 . The computer-implemented method of claim 1 , wherein the first matrix is characterized by a dimension equal to the sum of a first number and a second number, wherein the first number is equal to a first count of the first plurality of polygons multiplied by a second count of the plurality of masks, wherein the second number is equal to a third count of the first plurality of constraints multiplied by the second count.

7 . The computer-implemented method of claim 1 , wherein the first matrix is characterized by a dimension equal to an integer value equal to the sum of a first number and a second number, wherein the first number is equal to a first count of the first plurality of polygons, wherein the second number is equal to a second count of the first plurality of constraints multiplied by a third count of the plurality of masks.

8 . The computer-implemented method of claim 1 , wherein the first matrix includes a first plurality of rows and a plurality of columns having a different orientation to the first plurality of rows, wherein one of a plurality of values is associated with an intersection between one of the first plurality of rows and one of the plurality of columns, wherein each of the plurality of values is a logical true value, wherein constructing the first matrix comprises:
constructing a second plurality of rows, wherein the second plurality of rows is a subset of the first plurality of rows such that each one of the second plurality of rows contains exactly one logical true value in each one of the plurality of columns.

9 . The computer-implemented method of claim 1 further comprising:
representing, using the computer, the first matrix as a Dancing Links data structure to solve the first matrix.

10 . The computer-implemented method of claim 1 further comprising:
forming, using the computer, data representative of a graph associated with the layout, wherein the graph includes a plurality of vertices and a plurality of edges, each one of the plurality of vertices being associated with a different one of the first plurality of polygons, each one of the plurality of edges being associated with a different one of the first plurality of constraints;
transforming, using the computer, the graph into the first matrix, wherein the first matrix includes a first plurality of columns, wherein each one of the first plurality of columns is associated with a different one of the first plurality of polygons; and
visiting, using the computer, the first plurality of columns in a breadth-first search order associated with the graph to solve the first matrix.

11 . The computer-implemented method of claim 1 , wherein the first matrix includes a first plurality of rows and a plurality of columns having a different orientation to the first plurality of rows, wherein one of a plurality of values is associated with an intersection between one of the first plurality of rows and one of the plurality of columns, wherein each one of the plurality of values is a logical true value, the method further comprising:
first choosing, using the computer, one of the first plurality of columns having exactly one logical true value at the intersection of the chosen one of the first plurality of columns and one of the first plurality of rows to solve the first matrix.

12 . The computer-implemented method of claim 1 further comprising:
detecting, using the computer, a first conflict when solving the first matrix provides no feasible solution, wherein the first conflict is one of the first plurality of constraints that prevents assigning one of the plurality of masks to one of the first plurality of polygons;
removing, using the computer, a representation of the first conflict from the first matrix thereby forming a second matrix if the first conflict is detected;
marking, using the computer, the detected first conflict as an exact first conflict;
continuing, using the computer, to solve the second matrix thereby avoiding starting from scratch; and
detecting, using the computer, a second conflict when solving the second matrix provides no feasible solution, wherein the second conflict is one of the first plurality of constraints that prevents assigning one of the plurality of masks to one of the first plurality of polygons.

13 . The computer-implemented method of claim 1 further comprising:
stitching, using the computer, at least one of the first plurality of polygons to form a second plurality of polygons when solving the first matrix provides no feasible solution;
constructing, using the computer, a second matrix representative of the first plurality of constraints and a second plurality of constraints, wherein each of the first plurality of constraints is between a different pair of the first plurality of polygons, wherein each of the second plurality of constraints is between a different pair of the second plurality of polygons; and
solving, using the computer, the second matrix to thereby assign one of a plurality of masks to each different one of the first plurality of polygons and to each different one of the second plurality of polygons.

14 . The computer-implemented method of claim 1 , wherein a count of the plurality of masks is greater than or equal to 3.

15 . The computer-implemented method of claim 1 , wherein the first plurality of polygons includes a first polygon, a second polygon, and a third polygon, wherein constructing the first matrix further comprises:
associating the first polygon with a first column of the matrix; associating the second polygon with a second column of the matrix; and associating the third polygon with a third column of the matrix.

16 . The computer-implemented method of claim 15 , wherein the first plurality of constraints includes a first constraint between the first polygon and the second polygon, and a second constraint between the first polygon and the third polygon, wherein constructing the first matrix further comprises:
associating a first plurality of

Assignees

• Synopsys Inc

Inventors

• Chang hua-yu

Classifications

• G06F2111/04

  Constraint-based CAD · CPC title

• G06F30/392 Primary

  Floor-planning or layout, e.g. partitioning or placement · CPC title

• G06F30/398 Primary

  Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36) · CPC title

• G03F7/70466

  Multiple exposures, e.g. combination of fine and coarse exposures, double patterning or multiple exposures for printing a single feature (stitching G03F7/70475) · CPC title

• G03F1/70 Primary

  Adapting basic layout or design of masks to lithographic process requirements, e.g., second iteration correction of mask patterns for imaging · CPC title