Timing driven method for laying out a user's circuit onto a programmable integrated circuit device
First Claim
1. 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).
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
26 Claims
-
1. 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). - View Dependent Claims (2)
-
-
3. 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. - View Dependent Claims (4, 5, 6, 7, 8, 9, 10, 11)
-
6. 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
space="preserve" listing-type="equation">Ur(c).sub.new =Ur(c).sub.old +f(c) * S(c)until said slacks are sufficiently near zero.
-
- 7. 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
- space="preserve" listing-type="equation">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; andmax (weight(p)) is weight(p) on the path with maximum weight that includes connection c.
-
-
8. 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.
-
9. 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).
-
-
10. 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.
-
11. 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.
-
12. 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. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
-
19. 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. - View Dependent Claims (20, 21, 22, 23, 24)
-
23. 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. -
24. 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))).
-
-
25. 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. - View Dependent Claims (26)
-
Specification