US7096445B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-orthogonal structures and space tiles for layout, placement, and routing of an integrated circuit
Assignee: Cadence Design Systems Inc
•
Filing: 2003-01-14
•
Granted: 2006-08-22
•
Expires: 2023-01-14
Abstract
Abstract Disclosed is an improved approach for maintaining the structures for objects in a layout. A single type of structure is maintained that can be used to store or track a polygon of any shape, as long as the shape possesses a supported number of sides. The structure is capable of supporting irregular polygons or objects having angled edges. In one approach, the structure maintains information about each polygon as if that polygon is an octagon. Therefore, any polygon having eight or less orthogonal or diagonal sides can be supported using this structure.
Inventors
- 👤 Steven Lee Pucci
- 👤 Eric Martin Nequist
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:38
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
110 words
A method for implementing a layout of an integrated circuit, comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape, the at least eight data values identify locations of corresponding sides along a perpendicular axis to the sides, and in which at least one of the at least eight data values corresponds to a zero length side, in which the octagon shape is a degenerate octagon having less than eight sides.
Claim 2
Independent Claim
110 words
A method for implementing a layout of an integrated circuit, comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape, the at least eight data values identify locations of corresponding sides along a perpendicular axis to the sides, and in which at least one of the at least eight data values corresponds to a zero length side, in which the octagon shape is a degenerate octagon having less than eight sides.
Claim 3
Independent Claim
59 words
A method for implementing a layout of an integrated circuit, comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure in which the octagon-based structure comprises one or more data elements to identify neighboring objects with respect to the one or more objects.
Claim 4
Independent Claim
59 words
A method for implementing a layout of an integrated circuit, comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure in which the octagon-based structure comprises one or more data elements to identify neighboring objects with respect to the one or more objects.
Claim 5
Dependent Claim
18 words
The method of claim 2 in which neighboring objects are tracked along each edge of the octagon-based structure.
Claim 6
Dependent Claim
27 words
The method of claim 3 in which relational information is maintained for a non-orthogonal edge between one of the one or more objects and its neighboring object.
Claim 7
Dependent Claim
16 words
The method of claim 3 further comprising: identifying a routing path based upon tracking neighboring objects.
Claim 8
Dependent Claim
14 words
The method of claim 5 in which the neighboring objects are free space tiles.
Claim 9
Dependent Claim
15 words
The method of claim 5 in which the routing path is a non-orthogonal routing path.
Claim 10
Independent Claim
61 words
A method for implementing a layout of an integrated circuit, comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure in which at least two objects are merged together into a single shape, wherein a single octagon-based structure is used to track the single shape.
Claim 11
Independent Claim
61 words
A method for implementing a layout of an integrated circuit, comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure in which at least two objects are merged together into a single shape, wherein a single octagon-based structure is used to track the single shape.
Claim 12
Dependent Claim
58 words
The method of claim 8 further comprising: identifying the at least two objects to merge; confirming that the at least two objects share a common edge; verifying that edges to sum together in the single shape are properly aligned; verifying that the single shape has a supported number of sides; and confirming that the single shape is convex.
Claim 13
Independent Claim
33 words
The method of claims 1 , 2 or 8 in which the one or more objects comprise a space tile that is based upon a contour of an existing shape in the layout.
Claim 14
Independent Claim
25 words
The method of claims 1 , 2 or 8 in which at least one of the one or more objects has less than eight sides.
Claim 15
Dependent Claim
30 words
The method of claim 2 in which the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape.
Claim 16
Dependent Claim
30 words
The method of claim 8 in which the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape.
Claim 17
Dependent Claim
31 words
The method of claim 1 , 12 or 13 in which the at least eight data values identify angle information for at least one of the sides of the octagon shape.
Claim 18
Dependent Claim
18 words
The method of claim 14 in which the angle information is implicit based upon a default angle value.
Claim 19
Dependent Claim
126 words
A computer program product comprising a computer usable medium having executable code to execute a process for implementing a layout of an integrated circuit, the process comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape, the at least eight data values identify locations of corresponding sides along a perpendicular axis to the sides, and in which at least one of the at least eight data values corresponds to a zero length side, in which the octagon shape is a degenerate octagon having less than eight sides.
Claim 20
Dependent Claim
126 words
A computer program product comprising a computer usable medium having executable code to execute a process for implementing a layout of an integrated circuit, the process comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape, the at least eight data values identify locations of corresponding sides along a perpendicular axis to the sides, and in which at least one of the at least eight data values corresponds to a zero length side, in which the octagon shape is a degenerate octagon having less than eight sides.
Claim 21
Dependent Claim
29 words
The computer program product of claim 16 in which the at least eight data values identify angle information for at least one of the sides of the octagon shape.
Claim 22
Independent Claim
114 words
A system for implementing a layout of an integrated circuit, comprising: means for identifying one or more objects to be placed on an integrated circuit layout; means for tracking each of the one or more objects using an octagon-based structure, the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape, the at least eight data values identify locations of corresponding sides along a perpendicular axis to the sides, and in which at least one of the at least eight data values corresponds to a zero length side, in which the octagon shape is a degenerate octagon having less than eight sides.
Claim 23
Independent Claim
114 words
A system for implementing a layout of an integrated circuit, comprising: means for identifying one or more objects to be placed on an integrated circuit layout; means for tracking each of the one or more objects using an octagon-based structure, the octagon-based structure maintains at least eight data values, with the at least eight data values corresponding to sides of an octagon shape, the at least eight data values identify locations of corresponding sides along a perpendicular axis to the sides, and in which at least one of the at least eight data values corresponds to a zero length side, in which the octagon shape is a degenerate octagon having less than eight sides.
Claim 24
Dependent Claim
27 words
The system of claim 18 in which the at least eight data values identify angle information for at least one of the sides of the octagon shape.
Claim 25
Dependent Claim
75 words
A computer program product comprising a computer usable medium having executable code to execute a process for implementing a layout of an integrated circuit, the process comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, in which the octagon-based structure comprises one or more data elements to identify neighboring objects with respect to the one or more objects.
Claim 26
Dependent Claim
75 words
A computer program product comprising a computer usable medium having executable code to execute a process for implementing a layout of an integrated circuit, the process comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, in which the octagon-based structure comprises one or more data elements to identify neighboring objects with respect to the one or more objects.
Claim 27
Dependent Claim
20 words
The computer program product of claim 20 in which neighboring objects are tracked along each edge of the octagon-based structure.
Claim 28
Independent Claim
63 words
A system for implementing a layout of an integrated circuit, comprising: means for identifying one or more objects to be placed on an integrated circuit layout; means for tracking each of the one or more objects using an octagon-based structure, in which the octagon-based structure comprises one or more data elements to identify neighboring objects with respect to the one or more objects.
Claim 29
Independent Claim
63 words
A system for implementing a layout of an integrated circuit, comprising: means for identifying one or more objects to be placed on an integrated circuit layout; means for tracking each of the one or more objects using an octagon-based structure, in which the octagon-based structure comprises one or more data elements to identify neighboring objects with respect to the one or more objects.
Claim 30
Dependent Claim
18 words
The system of claim 22 in which neighboring objects are tracked along each edge of the octagon-based structure.
Claim 31
Dependent Claim
77 words
A computer program product comprising a computer usable medium having executable code to execute a process for implementing a layout of an integrated circuit, the process comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, in which at least two objects are merged together into a single shape, wherein a single octagon-based structure is used to track the single shape.
Claim 32
Dependent Claim
77 words
A computer program product comprising a computer usable medium having executable code to execute a process for implementing a layout of an integrated circuit, the process comprising: identifying one or more objects to be placed on an integrated circuit layout; tracking each of the one or more objects using an octagon-based structure, in which at least two objects are merged together into a single shape, wherein a single octagon-based structure is used to track the single shape.
Claim 33
Dependent Claim
35 words
The computer program product of claims 16 , 20 or 24 in which the one or more objects comprise a space tile that is based upon a contour of an existing shape in the layout.
Claim 34
Dependent Claim
27 words
The computer program product of claims 16 , 20 or 24 in which at least one of the one or more objects has less than eight sides.
Claim 35
Dependent Claim
64 words
The computer program product of claim 24 , wherein the process further comprising: identifying the at least two objects to merge; confirming that the at least two objects share a common edge; verifying that edges to sum together in the single shape are properly aligned; verifying that the single shape has a supported number of sides; and confirming that the single shape is convex.
Claim 36
Independent Claim
65 words
A system for implementing a layout of an integrated circuit, comprising: means for identifying one or more objects to be placed on an integrated circuit layout; means for tracking each of the one or more objects using an octagon-based structure, in which at least two objects are merged together into a single shape, wherein a single octagon-based structure is used to track the single shape.
Claim 37
Independent Claim
65 words
A system for implementing a layout of an integrated circuit, comprising: means for identifying one or more objects to be placed on an integrated circuit layout; means for tracking each of the one or more objects using an octagon-based structure, in which at least two objects are merged together into a single shape, wherein a single octagon-based structure is used to track the single shape.
Claim 38
Independent Claim
33 words
The system of claims 18 , 22 or 28 in which the one or more objects comprise a space tile that is based upon a contour of an existing shape in the layout.
Claim 39
Independent Claim
25 words
The system of claims 18 , 22 or 28 in which at least one of the one or more objects has less than eight sides.
Claim 40
Dependent Claim
68 words
The system of claim 28 further comprising: means for identifying the at least two objects to merge; means for confirming that the at least two objects share a common edge; means for verifying that edges to sum together in the single shape are properly aligned; means for verifying that the single shape has a supported number of sides; and means for confirming that the single shape is convex.
References Cited (Backward Citations)
US5157618A
Cited
US4933889A
Cited
JPH03127277A
Cited
US5689433A
Cited
US5617322A
Cited
US5550748A
Cited
US5822214A
Cited
US5774696A
Cited
US5911061A
Cited
US6035108A
Cited
US6484305B1
Cited
US6128767A
Cited
US6301686B1
Cited
US6317864B1
Cited
US6230306B1
Cited
US6289495B1
Cited
US6253363B1
Cited
US6247853B1
Cited
US6166441A
Cited
US6324675B1
Cited
US6349403B1
Cited
US6412097B1
Cited
US6701306B1
Cited
US6625611B1
Cited
US20020059194A1
Cited
US20020170027A1
Cited
US20030088841A1
Cited
US20020199165A1
Cited
US6952815B2
Cited
US20020157075A1
Cited
US20030121015A1
Cited
US6957410B2
Cited
US20020166105A1
Cited
US20020174412A1
Cited
US20030005399A1
Cited
US6680150B2
Cited
US20030023935A1
Cited
US6829757B1
Cited
US6785874B2
Cited
US20030115566A1
Cited
US20030066042A1
Cited
US20030070152A1
Cited
US6668365B2
Cited
US6845495B2
Cited
US6976237B1
Cited
US20040044980A1
Cited
US20040139417A1
Cited
US6948146B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-08-21 | 2010-02-20 | 2010-08-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-08-21 | 2014-02-20 | 2014-08-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-08-21 | 2018-02-20 | 2018-08-22 | $7700.00 | Window Closed / Lapsed |