US7036101B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for scalable interconnect solution
Assignee: Cadence Design Systems Inc
•
Filing: 2002-02-07
•
Granted: 2006-04-25
•
Expires: 2022-02-07
Abstract
Abstract An innovative routing method for an integrated circuit design layout. The layout can include design netlists and library cells. A multiple-level global routing can generate topological wire for each net. An area oriented graph-based detail routing on the design can be performed. A post route optimization after the detail routing can be performed to further improve the routing quality. Some methods can be single threaded all or some of the time, and/or multi-threaded some or all of the time.
Inventors
- 👤 Limin He
- 👤 So-Zen Yao
- 👤 Wenyong Deng
- 👤 Jing Chen
- 👤 Liang-Jih Chao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 07:28
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
145 words
A method of routing an integrated circuit (IC) design, comprising: accessing the IC design including a plurality of objects having at least two metal routing layers; accessing a first level for the IC design, wherein the first level of the IC design is partitioned into a first plurality of partitions, and the plurality of objects of the IC design are among the first plurality of partitions; and forming a second level for the IC design, including: partitioning the first level of the IC design into a second plurality of partitions, wherein one or more partitions of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions; and within each partition of the second plurality of partitions, interconnecting objects substantially independently of other partitions of the second plurality of partitions using the at least two metal routing layers.
Claim 2
Independent Claim
145 words
A method of routing an integrated circuit (IC) design, comprising: accessing the IC design including a plurality of objects having at least two metal routing layers; accessing a first level for the IC design, wherein the first level of the IC design is partitioned into a first plurality of partitions, and the plurality of objects of the IC design are among the first plurality of partitions; and forming a second level for the IC design, including: partitioning the first level of the IC design into a second plurality of partitions, wherein one or more partitions of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions; and within each partition of the second plurality of partitions, interconnecting objects substantially independently of other partitions of the second plurality of partitions using the at least two metal routing layers.
Claim 3
Dependent Claim
17 words
The method of claim 1 , wherein the routing is multithreaded at least at a first time.
Claim 4
Dependent Claim
18 words
The method of claim 1 , wherein the routing is single threaded at least at a first time.
Claim 5
Dependent Claim
25 words
The method of claim 1 , wherein one or more partitions of the first plurality of partitions has no objects of the plurality of objects.
Claim 6
Dependent Claim
25 words
The method of claim 1 , wherein every partition of the first plurality of partitions has one or more objects of the plurality of objects.
Claim 7
Dependent Claim
24 words
The method of claim 1 , wherein the interconnecting of objects substantially independently is subject to boundary conditions of the second plurality of partitions.
Claim 8
Dependent Claim
64 words
The method of claim 1 , wherein the interconnecting of objects substantially independently is subject to a first partition of the second plurality of partitions locking at least a net shared by at least the first partition and a second partition of the second plurality of partitions to prevent a change of the net by the second partition of the second plurality of partitions.
Claim 9
Dependent Claim
28 words
The method of claim 1 , wherein each partition of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions.
Claim 10
Dependent Claim
28 words
The method of claim 1 , wherein each of the first level and the second level of the IC design includes the at least two metal routing layers.
Claim 11
Dependent Claim
43 words
The method of claim 1 , wherein the first level of the IC design at least includes one layer of the at least two metal routing layers, and the second level of the IC design includes the at least two metal routing layers.
Claim 12
Dependent Claim
18 words
The method of claim 1 , wherein the plurality of objects are cells of an IC cell library.
Claim 13
Dependent Claim
16 words
The method of claim 1 , wherein the interconnecting of objects is a graph based routing.
Claim 14
Dependent Claim
24 words
The method of claim 1 , wherein the interconnecting of objects is a combination of an area based routing and a graph based routing.
Claim 15
Dependent Claim
51 words
The method of claim 1 , wherein the interconnecting of objects within the second plurality of partitions is a graph based routing, the interconnecting of objects between the second plurality of partitions is an area-based routing, and the interconnecting of objects between the first plurality of partitions is an area-based routing.
Claim 16
Dependent Claim
105 words
The method of claim 1 , further comprising: prior to the interconnecting of objects in each partition of the second plurality of partitions at the second level, forming a third level of the IC design, including partitioning the second level of the IC design into a third plurality of partitions, wherein one or more partitions of the second plurality of partitions is represented by at least two partitions of the third plurality of partitions; and within each partition of the third plurality of partitions, interconnecting objects substantially independently of other partitions of the third plurality of partitions using the at least two metal routing layers.
Claim 17
Dependent Claim
60 words
The method of claim 15 , further comprising: after the interconnecting of objects in each partition of the second plurality of partitions at the second level, within each partition of the first plurality of partitions at the first level, interconnecting objects substantially independently of other partitions of the first plurality of partitions using the at least two metal routing layers.
Claim 18
Dependent Claim
17 words
The method of claim 1 , wherein the at least two metal routing layers are an alloy.
Claim 19
Dependent Claim
22 words
The method of claim 1 , wherein at least two partitions of the first plurality of partitions have differing shapes or sizes.
Claim 20
Independent Claim
170 words
A method of routing an integrated circuit (IC) design, comprising: accessing the IC design including a plurality of objects having at least two metal routing layers; accessing a first level for the IC design, wherein the first level of the IC design is partitioned into a first plurality of partitions, and the plurality of objects of the IC design are among the first plurality of partitions; and forming a second level for the IC design, including: partitioning the first level into a second plurality of partitions, wherein one or more partitions of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions; allotting the second plurality of partitions among a plurality of areas, such that each area of the plurality of areas includes one or more partitions of the second plurality of partitions; and within each area of the plurality of areas, interconnecting objects substantially independently of other areas of the plurality of areas using the at least two metal routing layers.
Claim 21
Independent Claim
170 words
A method of routing an integrated circuit (IC) design, comprising: accessing the IC design including a plurality of objects having at least two metal routing layers; accessing a first level for the IC design, wherein the first level of the IC design is partitioned into a first plurality of partitions, and the plurality of objects of the IC design are among the first plurality of partitions; and forming a second level for the IC design, including: partitioning the first level into a second plurality of partitions, wherein one or more partitions of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions; allotting the second plurality of partitions among a plurality of areas, such that each area of the plurality of areas includes one or more partitions of the second plurality of partitions; and within each area of the plurality of areas, interconnecting objects substantially independently of other areas of the plurality of areas using the at least two metal routing layers.
Claim 22
Dependent Claim
17 words
The method of claim 19 , wherein the routing is multithreaded at least at a first time.
Claim 23
Dependent Claim
18 words
The method of claim 19 , wherein the routing is single threaded at least at a first time.
Claim 24
Dependent Claim
25 words
The method of claim 19 , wherein one or more partitions of the first plurality of partitions has no objects of the plurality of objects.
Claim 25
Dependent Claim
25 words
The method of claim 19 , wherein every partition of the first plurality of partitions has one or more objects of the plurality of objects.
Claim 26
Dependent Claim
24 words
The method of claim 19 , wherein the interconnecting of objects substantially independently is subject to boundary conditions of the second plurality of partitions.
Claim 27
Dependent Claim
23 words
The method of claim 19 , wherein the interconnecting of objects substantially independently is subject to boundary conditions of the plurality of areas.
Claim 28
Dependent Claim
64 words
The method of claim 19 , wherein the interconnecting of objects substantially independently is subject to a first partition of the second plurality of partitions locking at least a net shared by at least the first partition and a second partition of the second plurality of partitions to prevent a change of the net by the second partition of the second plurality of partitions.
Claim 29
Dependent Claim
61 words
The method of claim 19 , wherein the interconnecting of objects substantially independently is subject to a first area of the plurality of areas locking at least a net shared by at least the first area and a second area of the plurality of areas to prevent a change of the net by the second area of the plurality of areas.
Claim 30
Dependent Claim
28 words
The method of claim 19 , wherein each of the first level and the second level of the IC design includes the at least two metal routing layers.
Claim 31
Dependent Claim
43 words
The method of claim 19 , wherein the first level of the IC design at least includes one layer of the at least two metal routing layers, and the second level of the IC design includes the at least two metal routing layers.
Claim 32
Dependent Claim
18 words
The method of claim 19 , wherein the plurality of objects are cells of an IC cell library.
Claim 33
Dependent Claim
24 words
The method of claim 19 , wherein the interconnecting of objects is an area-oriented graph based routing by an area-oriented multi-threaded graph-based detail router.
Claim 34
Dependent Claim
34 words
The method of claim 19 , wherein the interconnecting of objects is a combination of a grid based routing by a grid based router and a graph based routing by a graph based router.
Claim 35
Dependent Claim
17 words
The method of claim 19 , wherein the at least two metal routing layers are an alloy.
Claim 36
Dependent Claim
22 words
The method of claim 19 , wherein at least two partitions of the first plurality of partitions have differing shapes or sizes.
Claim 37
Independent Claim
230 words
A method of routing an integrated circuit (IC) design, comprising: parsing IC design information including a plurality of cells of a cell library to support at least two metal wire routing layers for the IC design; receiving a design netlist to access a first level for the IC design, wherein the first level of the IC design is partitioned into a first plurality of partitions, and the plurality of cells of the IC design are among the first plurality of partitions; generating a topological wiring between the first plurality of partitions at the first level of the IC design using at least one layer of the at least two metal wire routing layers; and forming a second level for the IC design, including partitioning the first level of the IC design into a second plurality of partitions, wherein each of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions, generating a wiring between the second plurality of partitions at the second level of the IC design using at least one layer of the at least two metal wire routing layers, and generating a detailed wiring using a graph-based routing within each of the second plurality of partitions to interconnect the cells substantially independently of other partitions of the second plurality of partitions using the at least two metal wire routing layers.
Claim 38
Independent Claim
230 words
A method of routing an integrated circuit (IC) design, comprising: parsing IC design information including a plurality of cells of a cell library to support at least two metal wire routing layers for the IC design; receiving a design netlist to access a first level for the IC design, wherein the first level of the IC design is partitioned into a first plurality of partitions, and the plurality of cells of the IC design are among the first plurality of partitions; generating a topological wiring between the first plurality of partitions at the first level of the IC design using at least one layer of the at least two metal wire routing layers; and forming a second level for the IC design, including partitioning the first level of the IC design into a second plurality of partitions, wherein each of the first plurality of partitions is represented by at least two partitions of the second plurality of partitions, generating a wiring between the second plurality of partitions at the second level of the IC design using at least one layer of the at least two metal wire routing layers, and generating a detailed wiring using a graph-based routing within each of the second plurality of partitions to interconnect the cells substantially independently of other partitions of the second plurality of partitions using the at least two metal wire routing layers.
Claim 39
Dependent Claim
41 words
The method of claim 35 , wherein the IC design information of the cells includes a blockage within a first cell, and the generating of the detailed wiring using the graph-based routing is responsive to the blockage within the first cell.
Claim 40
Dependent Claim
18 words
The method of claim 35 , wherein the at least two metal wire routing layers are an alloy.
Claim 41
Dependent Claim
22 words
The method of claim 35 , wherein at least two partitions of the first plurality of partitions have differing shapes or sizes.
Claim 42
Dependent Claim
32 words
The method of claim 35 , wherein the topological wiring between the first plurality of partitions at the first level of the IC design is generated using an area based global routing.
Claim 43
Dependent Claim
31 words
The method of claim 35 , wherein the topological wiring between the first plurality of partitions at the first level of the IC design is generated using a grid-based global routing.
Claim 44
Dependent Claim
30 words
The method of claim 40 , wherein the wiring between the second plurality of partitions at the second level of the IC design is generated using the grid-based global routing.
Claim 45
Dependent Claim
29 words
The method of claim 40 , wherein the wiring between the second plurality of partitions at the second level of the IC design is generated using the graph-based routing.
References Cited (Backward Citations)
US4612618A
Cited
US4688072A
Cited
US5583788A
Cited
US5761664A
Cited
US5640327A
Cited
US5875117A
Cited
US5629860A
Cited
US5877091A
Cited
US5841664A
Cited
US5793643A
Cited
US5798936A
Cited
US5847965A
Cited
US5987086A
Cited
US6002857A
Cited
US5980093A
Cited
US5930500A
Cited
US5905669A
Cited
US6230304B1
Cited
US6249902B1
Cited
US6175950B1
Cited
US6269469B1
Cited
US20010018759A1
Cited
US6289495B1
Cited
US6651232B1
Cited
WO2000065489A1
Cited
US6207479B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-04-24 | 2009-10-24 | 2010-04-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-04-24 | 2013-10-24 | 2014-04-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-04-24 | 2017-10-24 | 2018-04-25 | $7700.00 | Window Closed / Lapsed |