US5883813A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic generation of phase shift masks using net coloring
Assignee: International Business Machines Corp
•
Filing: 1997-03-04
•
Granted: 1999-03-16
•
Expires: 2017-03-04
Abstract
Abstract According to the preferred embodiment, a method is provided for automatically coloring VLSI design elements for the purpose of assigning binary properties to the elements. The preferred method is particularly applicable for use generating phase shift mask designs from VLSI CAD datasets. The preferred method uses net coloring to automatically generate a data set of colored elements. The preferred method is not dependent on the order in which the elements are operated upon. The preferred method has the additional advantage of being able to automatically detect conflicts that prevent the VLSI design from being optimally colored. The preferred method is equally applicable to hierarchical VLSI databases with nested components and traditional flat databases. When applied the hierarchical databases, the preferred method provides element coloring with minimal data flattening required.
Inventors
- 👤 Young O. Kim
- 👤 Mark A. Lavin
- 👤 Lars W. Liebmann
- 👤 Glenwood S. Weinert
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 19:21
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
130 words
A method for assigning a binary property to circuit elements, the method comprising the steps of: a) providing a list of intrusion pairs, each of said intrusion pairs comprising a first element and a second element which intrude according to predefined rules; b) checking a net database for elements of one of said list of intrusion pairs and returning a net and a color of elements found in said net database; c) coloring said intrusion pair of elements such that said first element and said second element comprise opposite colors; d) assigning said first element and said second element to a net and adding said net to said net database; and e) performing steps b) through d) until all intrusion pairs in said list of intrusion pairs is operated upon.
Claim 2
Independent Claim
130 words
A method for assigning a binary property to circuit elements, the method comprising the steps of: a) providing a list of intrusion pairs, each of said intrusion pairs comprising a first element and a second element which intrude according to predefined rules; b) checking a net database for elements of one of said list of intrusion pairs and returning a net and a color of elements found in said net database; c) coloring said intrusion pair of elements such that said first element and said second element comprise opposite colors; d) assigning said first element and said second element to a net and adding said net to said net database; and e) performing steps b) through d) until all intrusion pairs in said list of intrusion pairs is operated upon.
Claim 3
Dependent Claim
46 words
The method of claim 1 wherein the steps of coloring and assigning said first element and said second element to a net comprises coloring said first element the opposite color of said second element and assigning said first element to the net of said second element.
Claim 4
Dependent Claim
88 words
The method of claim 1 wherein the steps of coloring and assigning said first element and said second element to a net comprises combining a first net containing said first element with a second net containing said second element when said intrusion pair comprises two found elements of different colors and wherein the steps of coloring and assigning comprises reversing the color of said first net and combining said reversed first net with said second net when said intrusion pair comprises two found elements of the same color.
Claim 5
Dependent Claim
20 words
The method of claim 1 wherein said elements comprise mask shapes and wherein said color represents mask shape phase shift.
Claim 6
Dependent Claim
16 words
The method of claim 1 wherein said CAD elements comprise a nested set of mask shapes.
Claim 7
Dependent Claim
36 words
The method of claim 5 wherein said net database comprises a contains-list, wherein said contains-list includes a list of mask shapes and other nets contained in each net in said net database and wherein said contained-in-list.
Claim 8
Dependent Claim
26 words
The method of claim 6 wherein said net database comprises a contained-in-list, wherein said contained-in-list includes representation of nets that are part of higher level nets.
Claim 9
Dependent Claim
20 words
The method of claim 1 further comprising the step of generating a phase shift mask design from said net database.
Claim 10
Independent Claim
159 words
A method for coloring a binary property and forming a nested net database of colored VLSI elements with minimal data flattening in a hierarchical CAD dataset, the method comprising the steps of: a) providing a nested list of intrusion pairs of elements; b) selecting an intrusion pair of elements from said nested list, said intrusion pair including a element instance and a second element instance; c) checking said nested net database of colored elements for said first element instance and said second element instance and returning a net number and a color of any found element instance; d) coloring said element instances in said selected intrusion pair such that said first element instance has a color opposite said second element instance and adding said first element instance to a net with said second element instance in said nested net database; and e) performing steps b) through d) until all intrusion pairs in said intrusion pair list are operated upon.
Claim 11
Independent Claim
159 words
A method for coloring a binary property and forming a nested net database of colored VLSI elements with minimal data flattening in a hierarchical CAD dataset, the method comprising the steps of: a) providing a nested list of intrusion pairs of elements; b) selecting an intrusion pair of elements from said nested list, said intrusion pair including a element instance and a second element instance; c) checking said nested net database of colored elements for said first element instance and said second element instance and returning a net number and a color of any found element instance; d) coloring said element instances in said selected intrusion pair such that said first element instance has a color opposite said second element instance and adding said first element instance to a net with said second element instance in said nested net database; and e) performing steps b) through d) until all intrusion pairs in said intrusion pair list are operated upon.
Claim 12
Dependent Claim
156 words
The method of claim 9 wherein the step of coloring said element instances comprises: i) coloring said first element instance a first color and coloring said second element instance a second color and assigning said intrusion pair to a new net when said intrusion pair comprises two unfound elements; ii) coloring said first element instance the opposite color of said second element instance and assigning said first element instance to the net of said second element instance shape when said intrusion pair comprises an unfound element instance and a found element instance; and iii) combining a first net containing said first element instance with a second net containing said second element instance when said intrusion pair comprises two found element instances of different colors and comprises reversing the color of said first net and combining said reversed first net with said second net when said intrusion pair comprises two found element instances of the same color.
Claim 13
Dependent Claim
23 words
The method of claim 9 wherein said element instances comprise mask shape instances and wherein said color comprises mask shape instance phase shift.
Claim 14
Dependent Claim
33 words
The method of claim 9 wherein said nested net database comprises a contains-list, wherein said contains-list includes a list of shape instances and other nets contained in each net in said nested database.
Claim 15
Dependent Claim
63 words
The method of claim 9 wherein said nested net database comprises a contained-in-list, wherein said contained-in-list includes representation of net instances that are part of higher level nets, and wherein said contained-in-list includes the number of instances of the net that could be represented at an associated node and the number of instances of the net that are represented at an associated node.
Claim 16
Dependent Claim
47 words
The method of claim 9 wherein the step of checking said nested net database for said first element instance and said second element instance comprises determining if the whole path to said first element instance and said second element instance is located in said nested net database.
Claim 17
Dependent Claim
21 words
The method of claim 9 further comprising the step of generating a phase shift mask design from said nested net database.
Claim 18
Independent Claim
328 words
A method for phase coloring mask shapes and forming a nested database of colored mask shapes with minimal data flattening in a hierarchical CAD dataset, the method comprising the steps of: a) providing a nested list of intrusion pairs of shapes; b) selecting an intrusion pair of shapes from said nested list, said intrusion pair including a first shape instance and a second shape instance; c) checking said nested database of colored shapes for said first shape instance and said second shape instance and returning a net number and a color of any found shape instance; d) coloring said shape instances in said selected intrusion pair and assigning said shape instances to a net in said nested database, and wherein i) the step of coloring shape instances and assigning shape instances to a net comprises coloring said first shape instance a first color and coloring said second shape instance a second color and assigning said intrusion pair to a new net when said intrusion pair comprises two unfound shapes; ii) the step of coloring shape instances and assigning shape instances to a net comprises coloring said first shape instance the opposite color of said second shape instance and assigning said first shape instance to the net of said second shape instance shape when said intrusion pair comprises an unfound shape instance and a found shape instance; iii) the step of coloring and assigning shape instances to a net comprises combining a first net containing said first shape with a second net containing said second shape when said intrusion pair comprises two found shapes of different colors and wherein the step of coloring and assigning shape instances to a net comprises reversing the color of said first net and combining said reversed first net with said second net when said intrusion pair comprises two found shapes of the same color; and e) performing steps b) through d) until all intrusion pairs in said intrusion pair list are operated upon.
Claim 19
Independent Claim
328 words
A method for phase coloring mask shapes and forming a nested database of colored mask shapes with minimal data flattening in a hierarchical CAD dataset, the method comprising the steps of: a) providing a nested list of intrusion pairs of shapes; b) selecting an intrusion pair of shapes from said nested list, said intrusion pair including a first shape instance and a second shape instance; c) checking said nested database of colored shapes for said first shape instance and said second shape instance and returning a net number and a color of any found shape instance; d) coloring said shape instances in said selected intrusion pair and assigning said shape instances to a net in said nested database, and wherein i) the step of coloring shape instances and assigning shape instances to a net comprises coloring said first shape instance a first color and coloring said second shape instance a second color and assigning said intrusion pair to a new net when said intrusion pair comprises two unfound shapes; ii) the step of coloring shape instances and assigning shape instances to a net comprises coloring said first shape instance the opposite color of said second shape instance and assigning said first shape instance to the net of said second shape instance shape when said intrusion pair comprises an unfound shape instance and a found shape instance; iii) the step of coloring and assigning shape instances to a net comprises combining a first net containing said first shape with a second net containing said second shape when said intrusion pair comprises two found shapes of different colors and wherein the step of coloring and assigning shape instances to a net comprises reversing the color of said first net and combining said reversed first net with said second net when said intrusion pair comprises two found shapes of the same color; and e) performing steps b) through d) until all intrusion pairs in said intrusion pair list are operated upon.
Claim 20
Dependent Claim
62 words
The method of claim 16 wherein said nested database comprises a contains-list, wherein said contains-list includes a list of shape instances and other nets contained in each net in said nested database and wherein the step of coloring said shape instances in said selected intrusion pair and assigning said shape instances to a net in said nested database comprises updating said contains-list.
Claim 21
Dependent Claim
92 words
The method of claim 16 wherein said nested database comprises a contained-in-list, wherein said contained-in-list includes representation of net instances that are part of higher level nets, and wherein said contained-in-list includes the number of instances of the net that could be represented at an associated node and the number of instances of the net that are represented at an associated node and wherein the step of coloring said shape instances in said selected intrusion pair and assigning said shape instances to a net in said nested database comprises updating said contained-in-list.
Claim 22
Dependent Claim
48 words
The method of claim 16 wherein the step of checking said nested database of colored shapes for said first shape instance and said second shape instance comprises determining if the whole path to said first shape instance and said second shape instance is located in said nested database.
Claim 23
Dependent Claim
19 words
The method of claim 16 further comprising the step of generating a phase shifted mask from said nested database.
References Cited (Backward Citations)
US5270796A
Cited
US5432044A
Cited
US5442714A
Cited
US5441834A
Cited
US5481473A
Cited
US5497334A
Cited
US5519628A
Cited
US5528508A
Cited
US5487962A
Cited
US5537648A
Cited
US5468578A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |