US5521837A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Timing driven method for laying out a user's circuit onto a programmable integrated circuit device
Assignee: Xilinx Inc
•
Filing: 1995-01-19
•
Granted: 1996-05-28
•
Expires: 2015-01-19
Abstract
Abstract The present invention provides suggested delay limits for use by layout tools which cause a programmable integrated circuit device to implement a logic design. The suggested delay limits can be used by such tools as an initial placement algorithm, a placement improvement algorithm, and a routing algorithm for evaluating and guiding potential layouts. The suggested delay limits take into account characteristics of the programmable device being used by estimating lower bound delays for each connection in a logic design, and take into account any previously achieved delays or achievable delays for each connection in calculating the suggested limits. Results of routing benchmark designs using the novel suggested limits show improved timing performance for all benchmark cases tested.
Inventors
- 👤 Jon A. Frankle
- 👤 Mon-Ren Chene
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 08:58
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; G06F30/394
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
153 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: specifying said logic design in machine readable form; placing each of said logic elements into one of said logic blocks; estimating lower bound connection delays L(c) for connections in said logic design; selecting delay limits U(c) for each of said connections, each of said delay limits being selected to be greater than or equal to a corresponding one of said lower bound connection delays; routing said connections wiring segments of said logic device to connect said logic elements which have been placed in said logic blocks, for which actual delays D(c) result, said routing step being performed such that at least some of said delay limits U(c) are not exceeded by said actual delays D(c).
Claim 2
Independent Claim
153 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: specifying said logic design in machine readable form; placing each of said logic elements into one of said logic blocks; estimating lower bound connection delays L(c) for connections in said logic design; selecting delay limits U(c) for each of said connections, each of said delay limits being selected to be greater than or equal to a corresponding one of said lower bound connection delays; routing said connections wiring segments of said logic device to connect said logic elements which have been placed in said logic blocks, for which actual delays D(c) result, said routing step being performed such that at least some of said delay limits U(c) are not exceeded by said actual delays D(c).
Claim 3
Dependent Claim
59 words
A method for laying out a logic design onto a logic device as in claim 1 comprising the further step, after said step of routing of said connections along wiring segments, of: deleting any completed routes which do not meet said revised delay limits, and routing unrouted connections in order of decreasing ratio of lower bound to delay limit.
Claim 4
Independent Claim
189 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: specifying said logic design in machine readable form; estimating lower bound connection delays L(c) for connections in said logic design; selecting delay limits U(c) for each of said connections, each of said delay limits being selected to be greater than or equal to a corresponding one of said lower bound connection delays; performing a layout step for which actual or estimated actual delays D(c) result, said layout Step being performed such that at least some of said delay limits U(c) are not exceeded by said actual or estimated actual delays D(c); computing said actual or estimated actual delays D(c); computing revised delay limits Ur(c), said revised delay limits being a function of said lower bounds L(c) and said actual or estimated actual delays D(c); performing a next layout step on said logic design using said revised delay limits Ur(c): and completing the layout of said logic design onto said logic device.
Claim 5
Independent Claim
189 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: specifying said logic design in machine readable form; estimating lower bound connection delays L(c) for connections in said logic design; selecting delay limits U(c) for each of said connections, each of said delay limits being selected to be greater than or equal to a corresponding one of said lower bound connection delays; performing a layout step for which actual or estimated actual delays D(c) result, said layout Step being performed such that at least some of said delay limits U(c) are not exceeded by said actual or estimated actual delays D(c); computing said actual or estimated actual delays D(c); computing revised delay limits Ur(c), said revised delay limits being a function of said lower bounds L(c) and said actual or estimated actual delays D(c); performing a next layout step on said logic design using said revised delay limits Ur(c): and completing the layout of said logic design onto said logic device.
Claim 6
Dependent Claim
58 words
A method for laying out a logic design onto a logic device as in claim 3 in which each of said revised delay limits is a function of slack S(c) for that connection, slack S(c) being the difference between earliest required signal arrival time R(c) of that connection and latest actual signal arrival time A(c) of that connection.
Claim 7
Dependent Claim
52 words
A method for laying out a logic design onto a logic device as in claim 4 in which said revised delay limits are computed from the formula Ur(c)=D(c)+f(c) * S(c) where Ur(c) represents said revised delay limits; f(c) is a fraction less than or equal to 1; and S(c) is said slack.
Claim 8
Dependent Claim
66 words
A method for laying out a logic design onto a logic device as in claim 5 comprising the steps performed after said step of computing revised delay limits of iteratively: again calculating said slacks S(c); and if said slacks S(c) are not sufficiently near zero, further revising said revised delay limits by the formula Ur(c).sub.new =Ur(c).sub.old +f(c) * S(c) until said slacks are sufficiently near zero.
Claim 9
Dependent Claim
55 words
A method for laying out a logic design onto a logic device as in claim 5 in which said fraction f(c) is computed from the formula f(c)=weight(c)/max (weight(p)) where weight(c)=D(c)-L(c); weight(p)=Σ weight(c) for all connections c on a path p; and max (weight(p)) is weight(p) on the path with maximum weight that includes connection c.
Claim 10
Dependent Claim
30 words
A method for laying out a logic design onto a logic device as in claim 3 in which said layout step comprises selecting a route to implement each said connection.
Claim 11
Dependent Claim
59 words
A method for laying out a logic design onto a logic device as in claim 8 comprising the further steps, after said step of computing revised delay limits, of: deleting any completed routes which do not meet said revised delay limits, and routing unrouted connections in order of decreasing ratio of said estimated delay D(c) to delay limit U(c).
Claim 12
Dependent Claim
29 words
A method for laying out a logic design onto a logic device as in claim 3 in which said layout step comprises placing logic elements in corresponding logic blocks.
Claim 13
Dependent Claim
45 words
A method for laying out a logic design onto a logic device as in claim 10 comprising the further step after said step of computing revised delay limits of placing logic elements in corresponding logic blocks so as not to violate said revised delay limits.
Claim 14
Independent Claim
151 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: a) specifying said logic design in machine readable form; b) selecting delay limits U(c) for each of said connections; c) performing an initial placement step for which estimated delays D(c) result, said initial placement step being performed using a modified min-cut partitioning algorithm which determines whether a logic element shall be moved across a cut line based on the following objectives: 1) minimizing the number of connections to said logic element crossing said cut line, and 2) minimizing the number of said connections to said logic element for which said delay limit U(c) is exceeded by said estimated delay D(c); and e) completing the layout of said logic design onto said logic device.
Claim 15
Independent Claim
151 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: a) specifying said logic design in machine readable form; b) selecting delay limits U(c) for each of said connections; c) performing an initial placement step for which estimated delays D(c) result, said initial placement step being performed using a modified min-cut partitioning algorithm which determines whether a logic element shall be moved across a cut line based on the following objectives: 1) minimizing the number of connections to said logic element crossing said cut line, and 2) minimizing the number of said connections to said logic element for which said delay limit U(c) is exceeded by said estimated delay D(c); and e) completing the layout of said logic design onto said logic device.
Claim 16
Dependent Claim
40 words
A method for laying out a logic design as in claim 12 in which said objective (2) minimizes estimated delay on at least one path of which at least one of said connections to said logic element is a part.
Claim 17
Dependent Claim
28 words
A method for laying out a logic design as in claim 12 in which said objective (2) minimizes the sum of timing costs on connections to said element.
Claim 18
Dependent Claim
59 words
A method for laying out a logic design as in claim 14 in which each of said timing costs is a function of said delay limits U(c), and also a function of worse case delay w(c) of a connection which crosses said cut line and better case delay B(c) of a connection which does not cross said cut line.
Claim 19
Dependent Claim
61 words
A method for laying out a logic design as in claim 15 in which said worse timing cost W(c) and said better timing cost B(c) are functions of estimated delays computed by assuming that a route used by said connection is the fastest route available to that connection without using routing resources in said logic device specifically designated to be fast.
Claim 20
Dependent Claim
43 words
A method for laying out a logic design as in claim 15 wherein said function of worse case delay W(c) and better case delay B(c) is a function of the difference between said worse case delay W(c) and said better case delay B(c).
Claim 21
Dependent Claim
42 words
A method for laying out a logic design as in claim 17 in which said function of the difference, C delay (c), is determined as follows: if W(c)<U(c)/2, C.sub.delay (C)=0; if U(c)>W(c)>U(c)/2, C.sub.delay (c)=W(c)-B(c); and if W(c)>U(c), C.sub.delay (C)=W(c)-B(c)+(W(c)-(greater of B(c), U(c)).
Claim 22
Independent Claim
155 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: a) specifying said logic design in machine readable form; b) selecting delay limits U(c) for each of said connections; c) determining estimated delays D(c) for each of said connections; d) performing a placement improvement step comprising cycling at least three logic elements between a set of at least three positions, in which at least two of said logic elements are assigned to positions as a function of timing costs associated with connections attached to said at least two logic elements, timing cost cost(c) of each said connection being a function of: 1) a corresponding delay limit U(c), and 2) a corresponding estimated delay D(c); and e) completing the layout of said logic design onto said logic device.
Claim 23
Independent Claim
155 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: a) specifying said logic design in machine readable form; b) selecting delay limits U(c) for each of said connections; c) determining estimated delays D(c) for each of said connections; d) performing a placement improvement step comprising cycling at least three logic elements between a set of at least three positions, in which at least two of said logic elements are assigned to positions as a function of timing costs associated with connections attached to said at least two logic elements, timing cost cost(c) of each said connection being a function of: 1) a corresponding delay limit U(c), and 2) a corresponding estimated delay D(c); and e) completing the layout of said logic design onto said logic device.
Claim 24
Dependent Claim
46 words
A method for laying out a logic design as in claim 19 in which said estimated delay D(c) assumes a route for each connection c is the fastest route available to that connection without using routing resources in said logic device specifically designated to be fast.
Claim 25
Dependent Claim
39 words
A method for laying out a logic design as in claim 19 in which said function of timing costs includes the sum of said timing costs cost(c) for all connections to one of said at least two logic elements.
Claim 26
Dependent Claim
107 words
A method for laying out a logic design as in claim 19 in which each position selected for a logic element as a function of timing costs is selected from the formulas G.sub.x =Σ(cost(c) * X(c)/Σ(cost(c)) G.sub.y =Σ(cost(c) * Y(c)/Σ(cost(c)) where cost(c) is the timing cost of a connection c attached at one end to said logic element, X (c) is the X coordinate of the logic element at another end of said connection c, Y(c) is the Y coordinate of the logic element at another end of said connection c; and said summation Σ is performed over all connections c which connect to said logic element.
Claim 27
Dependent Claim
82 words
A method for laying out a logic design as in claim 22 in which each of said timing costs cost (c) is equal to a set value F when said estimated delay D(c) is equal to said delay limit U(c), decreases to zero as a first function of the difference D(c) - U(c) for estimated delay D(c) less than U(c), and increases as a second function of estimated delay D(c) minus delay limit U(c) for estimated delay greater than said delay limit.
Claim 28
Dependent Claim
28 words
A method for laying out a logic design as in claim 23 in which said first function is F+D(c)-U(c), and said second function is F+(2 * (D(c)-U (c))).
Claim 29
Independent Claim
142 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: specifying said logic design in machine readable form; selecting delay limits U(c) for each of said connections; performing a layout step for which estimated delays D(c) result, said layout step being performed such that at least some of said delay limits U(c) are not exceeded by said estimated delays D(c); computing said estimated delays D(c); computing revised delay limits Ur(c) for each of said connections, said revised delay limits being a function of said estimated delays D(c); performing a next layout step on said logic design using said revised delay limits Ur(c); and completing the layout of said logic design onto said logic device.
Claim 30
Independent Claim
142 words
A method for laying out a logic design made up of logic elements and connections onto a logic device having logic blocks, wire segments, and means for connecting said wire segments to form routes, comprising the steps of: specifying said logic design in machine readable form; selecting delay limits U(c) for each of said connections; performing a layout step for which estimated delays D(c) result, said layout step being performed such that at least some of said delay limits U(c) are not exceeded by said estimated delays D(c); computing said estimated delays D(c); computing revised delay limits Ur(c) for each of said connections, said revised delay limits being a function of said estimated delays D(c); performing a next layout step on said logic design using said revised delay limits Ur(c); and completing the layout of said logic design onto said logic device.
Claim 31
Dependent Claim
97 words
A method for laying out a logic design as in claim 25 comprising the further step of: estimating lower bound connection delays L(c) for connections in said logic design; and in which said step of selecting delay limits U(c) for each of said connections is performed such that each of said delay limits is selected to be greater than or equal to a corresponding one of said lower bound connection delays; and said step of computing revised delay limits Ur(c) is performed such that said revised delay limits are also a function of said lower bounds L(c).
References Cited (Backward Citations)
US3617714A
Cited
US4593363A
Cited
US4630219A
Cited
US4924430A
Cited
US5053980A
Cited
US5187784A
Cited
US5144563A
Cited
US5095454A
Cited
US5218551A
Cited
US5239493A
Cited
US5197015A
Cited
US5237514A
Cited
US5224056A
Cited
US5251197A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-28 | 1999-11-27 | 2000-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-28 | 2003-11-27 | 2004-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-28 | 2007-11-27 | 2008-05-28 | $7700.00 | Window Closed / Lapsed |