US5550748A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Region search for delay routing and signal net matching
Assignee: Cadence Design Systems Inc
•
Filing: 1994-03-22
•
Granted: 1996-08-27
•
Expires: 2014-03-22
Abstract
Abstract A system and method performs signal net matching during delay routing. The delay router employs a region search for placing pseudo pins in a search region that will satisfy specified time delay constraints for a given signal net. The search region is an octagonal region defined by Manhattan detour lengths using derived wire length constraints as applied to a bounding box for the signal net. Any sequential router can be used to search the search region for free points. A first search phase finds delay paths to all free points in the search region from an arbitrary source pin. A second search phase then searches the search region for delay paths connecting a sink pin to one of the free points. Any delay path that connects the source and sink pin through a free point in the search region satisfies the time delay constraints. Dynamical routing can be implemented during the search phases as needed. Once all the signal nets have been routed, a group of signal nets to be matched is rerouted with the search region defined by the length of the longest routed path in the group. This ensures that all the signal nets in the group meet the specified time delay constraint.
Inventors
- 👤 Xiao-Ming Xiong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 11:46
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
153 words
A computer implemented method for routing a signal net having any number of pins and having maximum and minimum delay constraints, comprising of: a) defining a search region around the signal net such that a delay path coupling any pseudo pin placed in the search region between any two pins of the signal net satisfies the maximum and minimum delay constraints; b) locating a free point in the search region having a shortest delay path from a source pin of the signal net through the free point to a sink pin of the signal net; c) placing a pseudo pin at the free point; d) routing the signal net along a path including the shortest delay path from the source pin through the pseudo pin to the sink pin; e) selecting one of the at least one delay paths; and f) routing the signal net along a path including the selected delay path.
Claim 2
Dependent Claim
153 words
A computer implemented method for routing a signal net having any number of pins and having maximum and minimum delay constraints, comprising of: a) defining a search region around the signal net such that a delay path coupling any pseudo pin placed in the search region between any two pins of the signal net satisfies the maximum and minimum delay constraints; b) locating a free point in the search region having a shortest delay path from a source pin of the signal net through the free point to a sink pin of the signal net; c) placing a pseudo pin at the free point; d) routing the signal net along a path including the shortest delay path from the source pin through the pseudo pin to the sink pin; e) selecting one of the at least one delay paths; and f) routing the signal net along a path including the selected delay path.
Claim 3
Dependent Claim
76 words
The method of claim 1, further comprising: determining from a plurality of signal nets to be matched, a longest routed path in one of the plurality of signal nets; setting a net length constraint equal to a length of the longest routed path; and repeating a) through f) for each of the plurality of signal nets to be matched using the net length constraint to define the maximum and minimum delay constraints for the search region.
Claim 4
Dependent Claim
110 words
The method of claim 1, wherein defining a search region around the signal net, comprises: determining a signal net boundary surrounding the signal net, the signal net boundary defined by a plurality of coordinates; determining an estimated wire length for connecting the signal net; defining an outer search boundary as a function of the estimated wire length, the maximum delay constraint, and the coordinates of the signal net boundary; and defining defining an inner search boundary as a function of the estimated wire length, the minimum delay constraint, and the coordinates of the signal net boundary, wherein the search region comprises an area between the outer and inner search boundaries.
Claim 5
Dependent Claim
52 words
The method of claim 3 wherein determining an estimated wire length for connecting the signal net, comprises: defining, for ally number of pins in the signal net, a one-trunk Steiner tree connecting all pins of the signal net, the estimated wire length equal to a total length of the one-trunk Steiner tree.
Claim 6
Dependent Claim
52 words
The method of claim 3, wherein the outer search boundary comprises: all points having a distance from the signal net boundary equal to one half of a difference between a maximum wire length constraint and the estimated wire length, where the maximum wire length constraint is computed from the maximum delay constraint.
Claim 7
Dependent Claim
52 words
The method of claim 3, wherein the inner search boundary comprises: all points having a distance from the signal net boundary equal to one half of a difference between the minimum wire length constraint and the estimated wire length, where the minimum wire length constraint is computed from the minimum delay constraint.
Claim 8
Dependent Claim
27 words
The method of claim 1 wherein defining a search region further comprises segmenting the search region into a plurality of polygons prior to searching the search region.
Claim 9
Dependent Claim
104 words
The method of claim 1, wherein the step of locating comprises: a) searching the search region for at least one free point; b) searching from the source pin for a first delay path to the free point; c) searching from the sink pin for a second delay path to the free point; d) combining the first and second delay paths to a final delay path; e) repeating b) through d) until for each free point there is a final delay path connecting the free point to a source pin and a sink pin; and f) selecting the final delay path having a shortest length.
Claim 10
Dependent Claim
18 words
The method of claim 1, wherein the maximum delay constraint is not equal to the minimum delay constraint.
Claim 11
Dependent Claim
141 words
A delay router for delay routing a signal net having any number of pins, and further having maximum and minimum delay constraints, comprising: a net length estimator for determining an estimated wire length for connecting all of the pins of the signal net; a search region constructor for defining a search region around the signal net, such that a delay path coupling any pseudo pin placed in the search region between any two pins of the signal net satisfies the maximum and minimum delay constraints; a search engine for locating at least one delay path from a source pin of the signal net through a free point in the search region to a sink pin of the signal net; and a path selector for selecting a shortest delay path, wherein the search engine routes a path including the shortest delay path.
Claim 12
Dependent Claim
141 words
A delay router for delay routing a signal net having any number of pins, and further having maximum and minimum delay constraints, comprising: a net length estimator for determining an estimated wire length for connecting all of the pins of the signal net; a search region constructor for defining a search region around the signal net, such that a delay path coupling any pseudo pin placed in the search region between any two pins of the signal net satisfies the maximum and minimum delay constraints; a search engine for locating at least one delay path from a source pin of the signal net through a free point in the search region to a sink pin of the signal net; and a path selector for selecting a shortest delay path, wherein the search engine routes a path including the shortest delay path.
Claim 13
Dependent Claim
37 words
The delay router of claim 10 wherein the net length estimator creates a one-trunk Steiner tree connecting all pins of the signal net, the estimated wire length equal to a total length of the one-trunk Steiner tree.
Claim 14
Dependent Claim
20 words
The delay router of claim 10 wherein the search region constructor segments the search region into a plurality of polygons.
Claim 15
Dependent Claim
99 words
The delay router of claim 10 wherein the search engine searches the search region for at least one free point, performs a first search for a first delay path from the source pin to a first free point, performs a second search for a second delay path from the sink pin to the first free point, combines the first and second delay paths to form a final delay path, and repeats the first and second searches until for each free point there is a final delay path connecting the free point to a source pin and a sink pin.
Claim 16
Dependent Claim
95 words
The delay router of claim 10 wherein: the net length estimator determines a signal net boundary defined by a plurality of coordinates surrounding the signal net; and the search region constructor defines an outer search boundary as a function of the estimated wire length, the maximum delay constraint, and coordinates of the signal net boundary, and defines an inner search boundary as a function of the estimated wire length, the minimum delay constraint, and the coordinates of the signal net boundary, wherein the search region comprises an area between the outer and inner search boundaries.
Claim 17
Dependent Claim
53 words
The delay router of claim 14 wherein the outer search boundary comprises all points having a distance from the signal net boundary equal to one half of a difference between a maximum wire length constraint and the estimated wire length, where the maximum wire length constraint is computed from the maximum delay constraint.
Claim 18
Dependent Claim
53 words
The delay router of claim 14 wherein the inner search boundary comprises all points having a distance from the signal net boundary equal to one half of a difference between the minimum wire length constraint and the estimated wire length, where the minimum wire length constraint is computed from the minimum delay constraint.
Claim 19
Dependent Claim
57 words
The delay router of claim 10 further comprising: a net scheduler for scheduling a list of signal nets to be matched, and for setting a net length constraint to a length of a longest routed path, wherein the search region constructor defines the search region for each signal net to be matched using the net length constraint.
Claim 20
Dependent Claim
19 words
The delay router of claim 10, wherein the maximum delay constraint is not equal to the minimum delay constraint.
Claim 21
Dependent Claim
164 words
In a delay router for delay routing a signal net any number of pins, and having maximum and minimum delay constraints, a computer implemented method of defining a search region around the signal net for locating within the search region a free point at which to place a pseudo pin for routing between two pins of the signal net, comprising: determining a signal net boundary surrounding all of the pins of the signal net, the signal net boundary defined by a plurality of coordinates; determining an estimated wire length for connecting all of the pins of the signal net; defining an outer search boundary as a function of the estimated wire length, the maximum delay constraint, and the coordinates of the signal net boundary; and, defining an inner search boundary as a function of the estimated wire length, the minimum delay constraint, and the coordinates of the signal net boundary, wherein the search region comprises an area between the outer and inner search boundaries.
Claim 22
Dependent Claim
164 words
In a delay router for delay routing a signal net any number of pins, and having maximum and minimum delay constraints, a computer implemented method of defining a search region around the signal net for locating within the search region a free point at which to place a pseudo pin for routing between two pins of the signal net, comprising: determining a signal net boundary surrounding all of the pins of the signal net, the signal net boundary defined by a plurality of coordinates; determining an estimated wire length for connecting all of the pins of the signal net; defining an outer search boundary as a function of the estimated wire length, the maximum delay constraint, and the coordinates of the signal net boundary; and, defining an inner search boundary as a function of the estimated wire length, the minimum delay constraint, and the coordinates of the signal net boundary, wherein the search region comprises an area between the outer and inner search boundaries.
Claim 23
Dependent Claim
52 words
The method of claim 17, wherein the inner search boundary comprises: all points having a distance from the signal net boundary equal to one half of a difference between the minimum wire length constraint and the estimated wire length, where the minimum wire length constraint is computed from the minimum delay constraint.
Claim 24
Dependent Claim
18 words
The method of claim 19, wherein the maximum delay constraint is not equal to the minimum delay constraint.
Claim 25
Dependent Claim
43 words
The method of claim 19 wherein determining an estimated wire length for connecting the signal net, comprises: defining a one-trunk Steiner tree connecting all pins of the signal net, the estimated wire length equal to a total length of the one-trunk Steiner tree.
Claim 26
Dependent Claim
52 words
The method of claim 19, wherein the outer search boundary comprises: all points having a distance from the signal net boundary equal to one half of a difference between a maximum wire length constraint and the estimated wire length, where the maximum wire length constraint is computed from the maximum delay constraint.
References Cited (Backward Citations)
US4500963A
Cited
US4636965A
Cited
US5119317A
Cited
US5065355A
Cited
US5072402A
Cited
US5375069A
Cited
US5361214A
Cited
US5187671A
Cited
US5339253A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-27 | 2000-02-26 | 2000-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-27 | 2004-02-26 | 2004-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-27 | 2008-02-26 | 2008-08-27 | $7700.00 | Window Closed / Lapsed |