US5651012A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Implementation of half-path joining in a system for global performance analysis of a latch-based design
Assignee: Advanced Micro Devices Inc
•
Filing: 1996-08-12
•
Granted: 1997-07-22
•
Expires: 2016-08-12
Abstract
Abstract Critical speed paths through a latch-based logic circuit must contain at least one latch-to-latch combinational delay which exceeds the nominal phase time of the circuit. To identify this set of paths through latch-to-latch delays greater than the nominal phase time of the circuit (i.e., through interesting tLLs), a half-path joining approach is employed. Backward half-paths from fixed timing points forward through the network defined by a latch abstraction of the circuit to an interesting tLL are multiplicatively joined with forward half-paths from the interesting tLL forward to other fixed timing points to form a set of fixed-point-to-fixed-point (F2F) paths through the interesting tLL. Timing analysis is performed on the set of F2F paths to identify those which represent critical speed paths through the circuit. The half-path joining approach is improved by performing timing analysis on the half-paths prior to combining. Based on the results of half-path timing analysis, the number of half-paths, and therefore the number of F2F paths resulting from a multiplicative joining of half-paths, is greatly reduced. One approach is to discard any half-path which is guaranteed to meet a target frequency. An enhancement is to identify at most two backward and two forward half-paths by identifying the worst half-path in each direction based on optimistic and pessimistic assumptions concerning time borrowing across the join point. A further enhancement is to perform only the pessimistic timing analysis. Although the purely pessimistic approach tends to favor failing path segments near the join point, any failing path segment which is "missed" because of the optimization is guaranteed to be found in another timing check because the "missed" segment must itself contain an interesting tLL.
Inventors
- 👤 Robert F. Jones, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 21:34
CPC Classifications
G; G01; G01R; G01R31/00; G01R31/28; G01R31/317; G01R31/3181; G01R31/3185; G01R31/318533; G01R31/318577; G01R31/31858; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33; G06F30/3308; G06F30/3312
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
206 words
A method for identifying critical paths in a latch-based logic circuit, the method comprising the steps of: selecting certain of a plurality of latch-to-latch delays (tLL) from a first data structure representing a latch abstraction of the circuit, the selected tLLs being those which exceed a nominal phase time predetermined in accordance with a target frequency for the circuit; for each selected tLL, performing a forward search of paths represented in the first data structure, the forward search generating a second data structure of forward half-paths from the selected tLL forward to first fixed timing points; performing timing analysis on each of the forward half-paths; performing a backward search of paths represented in the first data structure, the backward search generating a third data structure of backward half-paths from the selected tLL backward to second fixed timing points; performing timing analysis on each of the backward half-paths; and combining a first subset of the forward half-paths from the second data structure with a second subset of the backward half-paths from the third data structure to form a third subset of fixed timing point to fixed timing point (F2F) paths represented in the first data structure; and performing timing analysis on the third subset of F2F paths.
Claim 2
Independent Claim
206 words
A method for identifying critical paths in a latch-based logic circuit, the method comprising the steps of: selecting certain of a plurality of latch-to-latch delays (tLL) from a first data structure representing a latch abstraction of the circuit, the selected tLLs being those which exceed a nominal phase time predetermined in accordance with a target frequency for the circuit; for each selected tLL, performing a forward search of paths represented in the first data structure, the forward search generating a second data structure of forward half-paths from the selected tLL forward to first fixed timing points; performing timing analysis on each of the forward half-paths; performing a backward search of paths represented in the first data structure, the backward search generating a third data structure of backward half-paths from the selected tLL backward to second fixed timing points; performing timing analysis on each of the backward half-paths; and combining a first subset of the forward half-paths from the second data structure with a second subset of the backward half-paths from the third data structure to form a third subset of fixed timing point to fixed timing point (F2F) paths represented in the first data structure; and performing timing analysis on the third subset of F2F paths.
Claim 3
Dependent Claim
27 words
A method, as recited in claim 1, wherein the first and second subsets are substantially limited to those half paths not guaranteed to meet the target frequency.
Claim 4
Dependent Claim
57 words
A method, as recited in claim 1, wherein the for each selected tLL step further includes: discarding half paths guaranteed to meet the target frequency, the first and second subsets represented in respective second and third data structures being substantially limited to remaining, undiscarded ones of the half-paths from respective forward and backward half-path timing analysis steps.
Claim 5
Dependent Claim
29 words
A method, as recited in claim 1, wherein one of the first and second subsets is substantially limited to those half paths not guaranteed to meet the target frequency.
Claim 6
Dependent Claim
57 words
A method, as recited in claim 1, wherein the for each selected tLL step further includes: discarding half paths guaranteed to meet the target frequency, one of the first and second subsets represented in respective second and third data structures being substantially limited to remaining, undiscarded ones of the half-paths from the respective half-path timing analysis step.
Claim 7
Dependent Claim
60 words
A method, as recited in claim 1, wherein the first and second subsets are respectively limited to: N forward half paths having the N lowest limit frequencies based on pessimistic assumptions concerning time borrowing across the selected tLL; and M backward half paths having the M lowest limit frequencies based on pessimistic assumptions concerning time borrowing across the selected tLL.
Claim 8
Dependent Claim
98 words
A method, as recited in claim 1, wherein the for each selected tLL step further includes: discarding substantially all but N forward half paths having the N lowest limit frequencies based on pessimistic assumptions concerning time borrowing across the selected tLL, and discarding substantially all but M half paths having the M lowest limit frequencies based on pessimistic assumptions concerning time borrowing across the selected tLL, wherein first and second subsets represented in respective second and third data structures are substantially limited to remaining, undiscarded ones of the half-paths from respective forward and backward half-path timing analysis steps.
Claim 9
Dependent Claim
38 words
A method, as recited in claim 1, wherein one of the first and second subsets is limited to N half paths having the N lowest limit frequencies based on pessimistic assumptions concerning time borrowing across the selected ILL.
Claim 10
Dependent Claim
82 words
A method, as recited in claim 1, wherein one of the first and second subsets is substantially limited to first and second half-paths, the first half-path being a half-path of the respective forward or backward half-paths having a lowest limit frequency based on optimistic assumptions concerning time borrowing across the selected tLL, and the second half-path being a half-path of the respective forward or backward half-paths having a lowest limit frequency based on pessimistic assumptions concerning time borrowing across the selected tLL.
Claim 11
Dependent Claim
90 words
A method, as recited in claim 1, wherein both the first and second subsets are substantially limited to respective pairs of half-paths, one half-path of each pair of half-paths being a half-path of the respective forward or backward half-paths having a lowest limit frequency based on optimistic assumptions concerning time borrowing across the selected tLL, and the other half-path of each pair of half-paths being a half-path of the respective forward or backward half-paths having a lowest limit frequency based on pessimistic assumptions concerning time borrowing across the selected tLL.
Claim 12
Dependent Claim
44 words
A method, as recited in claim 10, wherein the first and second subset combining step combines opposing forward and backward half-paths at the selected ILL; and wherein the third subset of F2F paths is substantially limited to four F2F paths through the selected tLL.
Claim 13
Dependent Claim
74 words
A method, as recited in claim 1, wherein the for each selected tLL step further includes: discarding substantially all but the worst forward and backward half paths evaluated in accordance with optimistic and pessimistic assumptions concerning time borrowing across the selected tLL, the first and second subsets represented in respective second and third data structures being substantially limited to two remaining, undiscarded half-paths from each of the forward and backward half-path timing analysis steps.
Claim 14
Dependent Claim
50 words
A method, as recited in claim 1, one of the first and second subsets is substantially limited to a single half-path, the single half-path being a half-path of the respective forward or backward half-paths having a lowest limit frequency based on pessimistic assumptions concerning time borrowing across the selected tLL.
Claim 15
Dependent Claim
43 words
A method, as recited in claim 1, the first and second subsets are each substantially limited to a single half-path of the respective forward or backward half-paths having a lowest limit frequency based on pessimistic assumptions concerning time borrowing across the selected tLL.
Claim 16
Dependent Claim
44 words
A method, as recited in claim 1, wherein the first and second subset combining step combines opposing forward and backward half-paths at the selected tLL; and wherein the third subset of F2F paths is substantially limited to one F2F paths through the selected tLL.
Claim 17
Dependent Claim
73 words
A method, as recited in claim 1, wherein the for each selected tLL step further includes: discarding substantially all but the worst forward and backward half paths evaluated in accordance with pessimistic assumptions concerning time borrowing across the selected tLL, the first and second subsets represented in respective second and third data structures being substantially limited to a single remaining, undiscarded half-path from each of the forward and backward half-path timing analysis steps.
Claim 18
Dependent Claim
87 words
A method, as recited in claim 1, further comprising the step of: generating a latch abstraction of the circuit, wherein the latch abstraction includes a plurality of latch elements, a plurality of the fixed timing points, and a plurality of the latch-to-latch delay (tLL) arcs, the latch abstraction representing a network of paths through the circuit wherein individual ones of the tLL arcs are coupled between ones of the latch elements and the fixed timing points to correspond to the structure and timing behavior of the circuit.
Claim 19
Dependent Claim
14 words
A computer program implementing the method of claim 1, encoded on computer readable media.
Claim 20
Dependent Claim
28 words
A plurality of independently executable computer programs implementing the method of claim 1, the independently executable computer programs coupled by data storage and encoded on computer readable media.
Claim 21
Independent Claim
148 words
A method for reducing computational load in a computer-implemented system for identification of critical paths in a latch-based logic circuit, the method comprising the steps of: selecting certain of a plurality of latch-to-latch delays (tLL) from a data structure representing a latch abstraction of the circuit, the selected tLLs being those which exceed a nominal phase time for the circuit; performing timing analysis on opposing forward and backward half-paths selected from the data structure, the selected forward and backward half-paths emanating from the selected tLLs, the timing analysis generating a limit frequency for the forward and backward half-paths; discarding a number of the half-paths in accordance with a predetermined limit frequency criterion; and performing timing analysis on substantially only fixed timing point to fixed timing point (F2F) paths resulting from the combination of remaining, undiscarded opposing forward and backward half-paths joined at corresponding ones of the selected tLLs.
Claim 22
Independent Claim
148 words
A method for reducing computational load in a computer-implemented system for identification of critical paths in a latch-based logic circuit, the method comprising the steps of: selecting certain of a plurality of latch-to-latch delays (tLL) from a data structure representing a latch abstraction of the circuit, the selected tLLs being those which exceed a nominal phase time for the circuit; performing timing analysis on opposing forward and backward half-paths selected from the data structure, the selected forward and backward half-paths emanating from the selected tLLs, the timing analysis generating a limit frequency for the forward and backward half-paths; discarding a number of the half-paths in accordance with a predetermined limit frequency criterion; and performing timing analysis on substantially only fixed timing point to fixed timing point (F2F) paths resulting from the combination of remaining, undiscarded opposing forward and backward half-paths joined at corresponding ones of the selected tLLs.
Claim 23
Dependent Claim
27 words
A method, as recited in claim 20, wherein the predetermined limit frequency criterion is whether or not a particular half-path is guaranteed to meet the target frequency.
Claim 24
Dependent Claim
47 words
A method, as recited in claim 20, wherein the predetermined limit frequency criterion is whether or not a particular half-path is a worst half-path emanating from the selected tLL in a particular direction when evaluated in accordance with pessimistic assumptions concerning time borrowing across the selected tLL.
Claim 25
Dependent Claim
38 words
A method, as recited in claim 20, wherein the predetermined limit frequency criterion is whether or not a particular half-path is one of a plurality of N worst half-paths emanating from the selected tLL in a particular direction.
Claim 26
Dependent Claim
76 words
A method, as recited in claim 20, wherein the predetermined limit frequency criterion is whether or not a particular half-path is one of a worst half-path emanating from the selected tLL in a particular direction when evaluated in accordance with optimistic assumptions concerning time borrowing across the selected tLL; and a worst half-path emanating from the selected tLL in the particular direction when evaluated in accordance with pessimistic assumptions concerning time borrowing across the selected ILL.
Claim 27
Dependent Claim
265 words
In a system for identifying critical paths in a latch-based logic circuit wherein the network structure and timing behavior of the circuit is represented in data storage as a latch abstraction having a plurality of latch elements, a plurality of fixed timing points, a plurality of latch-to-latch delay (tLL) arcs, and a network of paths therethrough, a timing analysis component comprising: selecting means coupled to the data storage for selecting and indicating those of the tLLs which exceed a nominal phase time of the circuit; forward and backward searching means coupled to the data storage for searching through the network of paths represented in the latch abstraction and coupled to the selecting means for receiving selected tLL indications, the forward searching means generating for each selected tLL, a plurality of forward half-paths from the selected ILL forward to first ones of the fixed timing points, the backward searching means generating for each selected tLL, a plurality of backward half-paths from the selected ILL backward to second ones of the fixed timing points; means for selectively joining ones of the forward half-paths and ones of the backward half-paths to form a plurality of candidate fixed-point-to-fixed-point (F2F) paths through selected ones of the tLLs, the selective joining means coupled to the forward and backward searching means to receive forward and backward half-paths; and F2F path timing means coupled the selective joining means to receive F2F paths, the F2F path timing means computing a limit frequency for each F2F path and providing an indication of those paths for which the limit frequency is less than the target frequency.
Claim 28
Dependent Claim
265 words
In a system for identifying critical paths in a latch-based logic circuit wherein the network structure and timing behavior of the circuit is represented in data storage as a latch abstraction having a plurality of latch elements, a plurality of fixed timing points, a plurality of latch-to-latch delay (tLL) arcs, and a network of paths therethrough, a timing analysis component comprising: selecting means coupled to the data storage for selecting and indicating those of the tLLs which exceed a nominal phase time of the circuit; forward and backward searching means coupled to the data storage for searching through the network of paths represented in the latch abstraction and coupled to the selecting means for receiving selected tLL indications, the forward searching means generating for each selected tLL, a plurality of forward half-paths from the selected ILL forward to first ones of the fixed timing points, the backward searching means generating for each selected tLL, a plurality of backward half-paths from the selected ILL backward to second ones of the fixed timing points; means for selectively joining ones of the forward half-paths and ones of the backward half-paths to form a plurality of candidate fixed-point-to-fixed-point (F2F) paths through selected ones of the tLLs, the selective joining means coupled to the forward and backward searching means to receive forward and backward half-paths; and F2F path timing means coupled the selective joining means to receive F2F paths, the F2F path timing means computing a limit frequency for each F2F path and providing an indication of those paths for which the limit frequency is less than the target frequency.
Claim 29
Dependent Claim
100 words
A timing analysis component, as recited in claim 25, wherein the selective joining means comprise: half path timing means coupled to the forward and backward searching means, the half-path timing means determining a limit frequency for each of the forward and backward half-paths; and half-path joining means coupled between the half-path timing means and the F2F path timing means, the half-path joining means selectively joining ones of the forward half-paths and ones of the backward half-paths to form the plurality of candidate fixed-point-to-fixed-point (F2F) paths, the half-path joining means responsive to the limit frequency determined by the half-path timing means.
Claim 30
Dependent Claim
40 words
A timing analysis component, as recited in claim 25, wherein the half-path joining means filters out those half-paths guaranteed to meet the target frequency and multiplicatively joins only those forward and backward half-paths not guaranteed to meet the target frequency.
Claim 31
Dependent Claim
82 words
A timing analysis component, as recited in claim 25, wherein half-path limit frequencies are determined based on a pessimistic assumption that maximum net time borrowing is incurred at the prior/post phase latch across the selected tLL, and wherein the half-path joining means filters out substantially all but a single one of the forward and backward half-paths, half-path joining means providing a single F2F path comprising the forward half-path having the lowest limit frequency and the backward half-path having the lowest limit frequency.
Claim 32
Dependent Claim
41 words
A timing analysis component, as recited in claim 25, wherein one of the selecting means, the forward searching means, the backward searching means, the selective joining means, and the F2F path timing means comprise software executable on a general purpose processor.
Claim 33
Dependent Claim
37 words
A timing analysis component, as recited in claim 25, wherein one of the selecting means, the forward searching means, the backward searching means, the selective joining means, and the F2F path timing means comprise special purpose logic.
Claim 34
Dependent Claim
39 words
A timing analysis component, as recited in claim 25, wherein the forward searching means, the backward searching means, the selective joining means, and the F2F path timing means are coupled via intermediate data structures represented in the data storage.
Claim 35
Dependent Claim
20 words
A timing analysis component, as recited in claim 31, wherein the data storage includes memory- and file system-provided data storage.
References Cited (Backward Citations)
US5524244A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-21 | 2001-01-20 | 2001-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-21 | 2005-01-20 | 2005-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-21 | 2009-01-20 | 2009-07-22 | $7700.00 | Window Closed / Lapsed |