US6543043B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Inter-region constraint-based router for use in electronic design automation
Assignee: Cadence Design Systems Inc
•
Filing: 2000-06-01
•
Granted: 2003-04-01
•
Expires: 2020-06-01
Abstract
Abstract A system and method for routing wires using an automated circuit design tool includes a process for order negotiation to adjust the ordering of wires back and forth between conduits by considering both inter-region and intra-region constraints on the layout of the wires. Order negotiation is preferably carried out by looking both forward and backward during the processing of channels, and by flexibly accounting for intra-region, crosstalk, and grouping constraints, as well as conduit exit constraints. Pairs of nets within a conduit are classified in different categories, including (1) having internal constraints, and (2) not having internal constraints. Nets having internal constraints are generally used in order negotiation for limited purposes (e.g., breaking a loop), whereas nets having no internal constraints are generally used in order negotiation for a variety of other purposes as well, including improving the layout of other conduits.
Inventors
- 👤 Xiao-Dong Wang
- 👤 David Chyan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:16
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
142 words
In an electronic design automation system, a method for placement and routing, comprising the steps of: receiving a netlist file comprising a specification of logic cell instances and nets connecting said logic cell instances; placing said logic cell instances in a circuit layout by giving said logic cell instances specific coordinate locations in said circuit layout, said step of placing said logic cell instances comprising the step of defining a plurality of conduits separating said logic cell instances; locating said nets in said conduits; identifying a set of constraints associated with the nets placed in said conduits; and for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, regardless of whether said other nearby conduits were previously processed or are as yet unprocessed.
Claim 2
Dependent Claim
142 words
In an electronic design automation system, a method for placement and routing, comprising the steps of: receiving a netlist file comprising a specification of logic cell instances and nets connecting said logic cell instances; placing said logic cell instances in a circuit layout by giving said logic cell instances specific coordinate locations in said circuit layout, said step of placing said logic cell instances comprising the step of defining a plurality of conduits separating said logic cell instances; locating said nets in said conduits; identifying a set of constraints associated with the nets placed in said conduits; and for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, regardless of whether said other nearby conduits were previously processed or are as yet unprocessed.
Claim 3
Dependent Claim
35 words
The method of claim 1 , wherein said step of identifying said set of constraints associated with the nets placed in said conduits comprises the step of identifying one or more conduit exit vertical constraints.
Claim 4
Dependent Claim
34 words
The method of claim 1 , wherein said step of identifying said set of constraints associated with the nets placed in said conduits comprises the step of identifying one or more inter-regional vertical constraints.
Claim 5
Dependent Claim
41 words
The method of claim 1 , wherein said step of identifying said set of constraints associated with the nets placed in said conduits comprises the step of identifying both intra-region and inter-region constraints associated with the nets placed in said conduits.
Claim 6
Dependent Claim
18 words
The method of claim 4 , wherein said intra-region constraints comprise at least vertical constraints and horizontal constraints.
Claim 7
Dependent Claim
24 words
The method of claim 5 , further comprising the step of generating a constraint graph for said intra-region constraints and for said inter-region constraints.
Claim 8
Dependent Claim
78 words
The method of claim 4 , wherein said step of, for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, comprises the step of, for each conduit, associating the nets placed therein with one or more tracks in the conduit based upon both said intra-region constraints and said inter-region constraints relating to the conduit and said other nearby conduits.
Claim 9
Dependent Claim
71 words
The method of claim 1 , wherein said step of, for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, comprises the steps of identifying a cost value for breaking a constraint for each conduit affected by said constraint, and selecting the conduit with the lowest cost value for breaking said constraint.
Claim 10
Dependent Claim
25 words
The method of claim 8 , wherein said cost value for a conduit is inversely proportional to a number of free tracks in the conduit.
Claim 11
Dependent Claim
172 words
A computer readable medium having stored therein one or more sequences of instructions for performing placement and routing functions in an electronic design automation system, said one or more sequences of instructions causing one or more processors to perform a plurality of acts, said acts comprising: receiving a netlist file comprising a specification of logic cell instances and nets connecting said logic cell instances; placing said logic cell instances in a circuit layout by giving said logic cell instances specific coordinate locations in said circuit layout, said act of placing said logic cell instances comprising the act of defining a plurality of conduits separating said logic cell instances; locating said nets in said conduits; identifying a set of constraints associated with the nets placed in said conduits; and for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, regardless of whether said other nearby conduits were previously processed or are as yet unprocessed.
Claim 12
Dependent Claim
172 words
A computer readable medium having stored therein one or more sequences of instructions for performing placement and routing functions in an electronic design automation system, said one or more sequences of instructions causing one or more processors to perform a plurality of acts, said acts comprising: receiving a netlist file comprising a specification of logic cell instances and nets connecting said logic cell instances; placing said logic cell instances in a circuit layout by giving said logic cell instances specific coordinate locations in said circuit layout, said act of placing said logic cell instances comprising the act of defining a plurality of conduits separating said logic cell instances; locating said nets in said conduits; identifying a set of constraints associated with the nets placed in said conduits; and for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, regardless of whether said other nearby conduits were previously processed or are as yet unprocessed.
Claim 13
Dependent Claim
37 words
The computer readable medium of claim 10 , wherein said act of identifying said set of constraints associated with the nets placed in said conduits comprises the act of identifying one or more conduit exit vertical constraints.
Claim 14
Dependent Claim
36 words
The computer readable medium of claim 10 , wherein said act of identifying said set of constraints associated with the nets placed in said conduits comprises the act of identifying one or more inter-regional vertical constraints.
Claim 15
Dependent Claim
43 words
The computer readable medium of claim 10 , wherein said act of identifying said set of constraints associated with the nets placed in said conduits comprises the act of identifying both intra-region and inter-region constraints associated with the nets placed in said conduits.
Claim 16
Dependent Claim
20 words
The computer readable medium of claim 13 , wherein said intra-region constraints comprise at least vertical constraints and horizontal constraints.
Claim 17
Dependent Claim
26 words
The computer readable medium of claim 14 , wherein said acts further comprise generating a constraint graph for said intra-region constraints and for said inter-region constraints.
Claim 18
Dependent Claim
80 words
The computer readable medium of claim 4 , wherein said act of, for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, comprises the act of, for each conduit, associating the nets placed therein with one or more tracks in the conduit based upon both said intra-region constraints and said inter-region constraints relating to the conduit and said other nearby conduits.
Claim 19
Dependent Claim
73 words
The computer readable medium of claim 10 , wherein said act of, for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, comprises the acts of identifying a cost value for breaking a constraint for each conduit affected by said constraint, and selecting the conduit with the lowest cost value for breaking said constraint.
Claim 20
Dependent Claim
27 words
The computer readable medium of claim 17 , wherein said cost value for a conduit is inversely proportional to a number of free tracks in the conduit.
Claim 21
Dependent Claim
128 words
In an electronic design automation system wherein a netlist file is received for placing and routing, said netlist file comprising a specification of logic cell instances and nets connecting said logic cell instances, said logic cell instances being placed in a circuit layout such that a plurality of conduits between said logic cell instances are defined, a method for routing, comprising the steps of: locating said nets in said conduits; identifying a set of constraints associated with the nets placed in said conduits; and for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, regardless of whether said other nearby conduits were previously processed or are as yet unprocessed.
Claim 22
Dependent Claim
128 words
In an electronic design automation system wherein a netlist file is received for placing and routing, said netlist file comprising a specification of logic cell instances and nets connecting said logic cell instances, said logic cell instances being placed in a circuit layout such that a plurality of conduits between said logic cell instances are defined, a method for routing, comprising the steps of: locating said nets in said conduits; identifying a set of constraints associated with the nets placed in said conduits; and for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, regardless of whether said other nearby conduits were previously processed or are as yet unprocessed.
Claim 23
Dependent Claim
35 words
The method of claim 19 , wherein said step of identifying said set of constraints associated with the nets placed in said conduits comprises the step of identifying one or more conduit exit vertical constraints.
Claim 24
Dependent Claim
34 words
The method of claim 19 , wherein said step of identifying said set of constraints associated with the nets placed in said conduits comprises the step of identifying one or more inter-regional vertical constraints.
Claim 25
Dependent Claim
41 words
The method of claim 1 , wherein said step of identifying said set of constraints associated with the nets placed in said conduits comprises the step of identifying both intra-region and inter-region constraints associated with the nets placed in said conduits.
Claim 26
Dependent Claim
78 words
The method of claim 22 , wherein said step of, for each conduit, associating the nets placed therein with one or more tracks in the conduit using constraint information for both the conduit being processed and other nearby conduits, comprises the step of, for each conduit, associating the nets placed therein with one or more tracks in the conduit based upon both said intra-region constraints and said inter-region constraints relating to the conduit and said other nearby conduits.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-03-31 | 2006-09-30 | 2007-04-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-31 | 2010-09-30 | 2011-04-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-31 | 2014-09-30 | 2015-04-01 | $7700.00 | Window Closed / Lapsed |