Fast pattern matching

• US 8,769,474 B1
• Filed: 10/18/2010
• Issued: 07/01/2014
• Est. Priority Date: 08/18/2004
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Gennari, Frank E., Lai, Ya-Chieh, Moskewicz, Matthew W., Lam, Michael C., McIntyre, Gregory R.
• Primary Examiner(s): DO, THUAN V
• Application Number:
  US12/907,003
• Time in Patent Office: 1,352 Days
• Field of Search: 716/55, 716/132, 716/139
• US Class Current: 716/139
• CPC Class Codes: G06F 2119/18 Manufacturability analysis or optimisation for manufacturability
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

Disclosed are methods, systems, and articles of manufacture for using pattern matching with an integrated circuit layout including recognizing shapes within the IC layout, identifying features for the shapes, and extracting situations for the respective features. The method may further include simulating the situations to determine a set of situations for modification based on an OPC requirement, modifying the set of situations to improve satisfaction of the OPC requirement, and reintegrating the modified set of situations into the IC layout. The method may also include simulating a subset of the extracted situations to determine aerial images of the subset, and tiling the subset of situations to form a larger aerial image. The method may also include removing overlap from a window based on the situations extracted for the window, calculating a density for each of the situations, and calculating a density for the window based on the density.

Claims

1. A computer implemented method for using pattern matching with an integrated circuit layout, comprising:

using at least one processor to perform a process, the process comprising;

determining a canonical set of situations from a set of situations larger than the canonical set;

matching a pattern to a situation for the integrated circuit layout to perform design rule check by searching through the canonical set of canonical situations, rather than searching through the integrated circuit layout; and

adjusting a portion of the integrated circuit layout, wherein the portion of the integrated circuit layout includes one or more electronic circuit design components associated with the situation.

2. The computer implemented method of claim 1, further comprising:

identifying one or more situations for the integrated circuit layout.

3. The computer implemented method of claim 2, wherein the act of identifying the one or more situations comprises:

identifying one or more features;

extracting and storing configurations based at least in part on the one or more features;

merging configurations and removing overlap to make the configurations canonical;

computing hash values for the configurations;

resolving collisions of the hash values; and

storing hash values after the resolving collisions.

4. The computer implemented method of claim 1, further comprising:

extracting the situation based at least in part on a radius of extraction that is chosen so that the pattern fits within the situation regardless of orientation.

5. The computer implemented method of claim 1, wherein the act of adjusting the portion of the integrated circuit layout includes automatically replacing an original layout portion with a new layout portion, the original layout portion corresponding to the situation.

6. The computer implemented method of claim 5, further comprising:

accessing an image-based rule-based OPC library that includes the pattern and the new layout portion.

7. The computer implemented method of claim 1, wherein the act of adjusting the portion of the integrated circuit layout comprises replacing an original layout portion with a new layout portion, in which the original layout portion corresponds to the situation, and the pattern represents a failed portion of a manufactured pattern.

8. A system for using pattern matching with an integrated circuit layout, comprising:

a computing system that comprises at least one processor and is at least to;

determine a canonical set of situations from a set of situations larger than the canonical set;

match a pattern to a situation for the integrated circuit layout to perform design rule check by searching through the canonical set of canonical situations, rather than searching through the integrated circuit layout; and

adjust a portion of the integrated circuit layout, wherein the portion of the integrated circuit layout includes one or more electronic circuit design components associated with the situation.

9. The system of claim 8, the computing system is further to:

identify one or more situations for the integrated circuit layout.

10. The system of claim 9, in which the computing system that is to identify the one or more situations is further to:

identify the one or more features;

extract and store configurations based at least in part on the one or more features;

merge configurations and remove overlap to make the configurations canonical;

compute hash values for the configurations;

resolve collisions of the hash values; and

store hash values after the resolving collisions.

11. The system of claim 8, the computing system is further to:

extract the situation based at least in part on a radius of extraction that is chosen so that the pattern fits within the situation regardless of orientation.

12. The system of claim 8, wherein the computing system that is to adjust the portion of the integrated circuit layout is further to automatically replace an original layout portion with a new layout portion, the original layout portion corresponding to the situation.

13. The system of claim 12, wherein the computing system further to at least:

access an image-based rule-based OPC library that includes the pattern and the new layout portion.

14. The system of claim 8, wherein the computing system that is to perform the portion of the integrated circuit layout is further to replace an original layout portion with a new layout portion, in which the original layout portion corresponds to the situation, and the pattern represents a failed portion of a manufactured pattern.

15. An article of manufacture comprising a non-transitory computer readable storage medium having stored thereupon a sequence of instructions which, when executed by a processor of a computing system, causes the computing system to perform a process for using pattern matching with an integrated circuit layout, the process comprising:

determining a canonical set of situations from a set of situations larger than the canonical set;

matching a pattern to a situation for the integrated circuit layout to perform design rule check by searching through the canonical set of canonical situations, rather than searching through the integrated circuit layout; and

adjusting a portion of the integrated circuit layout, wherein the portion of the integrated circuit layout includes one or more electronic circuit design components associated with the situation.

16. The article of manufacture of claim 15, the process further comprising:

identifying one or more situations for the integrated circuit layout.

17. The article of manufacture of claim 16, wherein the process for identifying the one or more situations comprises:

identifying the one or more features;

extracting and storing configurations based at least in part on the one or more features;

merging configurations and removing overlap to make the configurations canonical;

computing hash values for the configurations;

resolving collisions of the hash values; and

storing hash values after the resolving collisions.

18. The article of manufacture of claim 15, the process further comprising:

extracting the situation based at least in part on a radius of extraction that is chosen so that the pattern fits within the situation regardless of orientation.

19. The article of manufacture of claim 15, wherein the process for adjusting the portion of the integrated circuit layout comprises automatically replacing an original layout portion with a new layout portion, the original layout portion corresponding to the situation.

20. The article of manufacture of claim 19, the process further comprising:

accessing an image-based rule-based OPC library that includes the pattern and the new layout portion.