Patent US6397372B1 successfully refreshed from Google Patents.
US6397372B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cell based parallel verification of an integrated circuit design
Assignee: Mentor Graphics Corp
•
Filing: 1999-01-19
•
Granted: 2002-05-28
•
Expires: 2019-01-19
Abstract
Abstract An EDA tool is provided with the ability to determine a cell based parallel verification order for a plurality of hierarchically organized design cells of an integrated circuit design, and the ability to verify the design cells in accordance with the cell based parallel verification order, with at least some of the design cells being verified in parallel. In one embodiment, the EDA tool is also provided with the ability to re-express a design cell of the IC design in terms of a number of newly formed intervening constituent design cells, with the new intervening constituent design cells being formed in accordance with a number of metrics profiling placements of original constituent design cells of the design cell.
Inventors
- 👤 Zeki Bozkus
- 👤 Laurence W. Grodd
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 10:32
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
101 words
A method comprising: receiving a hierarchical organization for a plurality of design cells comprising an integrated circuit design, said hierarchical organization defining at least two layers of design cells, a higher layer in the hierarchical organization corresponding to parent design cells, said parent design cells having data dependencies on respective child design cells corresponding to one or more lower layers in the hierarchical organization; and reordering the hierarchical organization into a verification order to increase distances between positions in the verification order corresponding to the child design cells and positions in the verification order corresponding to the respective parent design cells.
Claim 2
Independent Claim
101 words
A method comprising: receiving a hierarchical organization for a plurality of design cells comprising an integrated circuit design, said hierarchical organization defining at least two layers of design cells, a higher layer in the hierarchical organization corresponding to parent design cells, said parent design cells having data dependencies on respective child design cells corresponding to one or more lower layers in the hierarchical organization; and reordering the hierarchical organization into a verification order to increase distances between positions in the verification order corresponding to the child design cells and positions in the verification order corresponding to the respective parent design cells.
Claim 3
Dependent Claim
76 words
The method of claim 1 wherein reordering the hierarchical organization comprises: generating a topological order to define topological relationships between sets of child/parent design cells; generating a sequential order for the plurality of design cells wherein all design cells from each layer of the hierarchical organization are sequentially listed in the sequential order; and switching positions among design cells in the sequential order to increase the distances in the verification order without violating the topological relationships.
Claim 4
Dependent Claim
26 words
The method of claim 2 wherein the topological order comprises a depth-first sort list which numbers design cells based on layer positions in the hierarchical organization.
Claim 5
Dependent Claim
41 words
The method of claim 2 wherein the sequential order comprises a breadth-first sort list which sequentially numbers the plurality of design cells starting with a first cell in a first layer and ending with a last cell in a last layer.
Claim 6
Dependent Claim
56 words
The method of claim 2 wherein switching positions without violating the topological relationships comprises: locating a position corresponding to a first parent design cell; and moving the position corresponding to the first parent design cell to a later verification position without passing a position corresponding to a parent design cell of the first parent design cell.
Claim 7
Dependent Claim
51 words
The method of claim 2 wherein switching positions without violating the topological relationships comprises: locating a position corresponding to a first parent design cell; and moving the position corresponding to the first parent design cell to a later verification position without passing a position corresponding to a higher order topological layer.
Claim 8
Dependent Claim
48 words
The method of claim 1 wherein the distances in the verification order between the positions corresponding to the child design cells and the positions corresponding to the respective parent design cells provide a lower probability of data dependencies between subsequently ordered design cells compared to the hierarchical organization.
Claim 9
Dependent Claim
32 words
The method of claim 1 further comprising: providing the plurality of design cells for verification according to the verification order, multiple design cells having no data dependencies to be verified in parallel.
Claim 10
Dependent Claim
74 words
The method of claim 8 wherein providing the plurality of design cells comprises: dispatching a first m design cells in the verification order to a verification queue, n design cells that have no data dependencies to be selected, verified, and dequeued from the queue in parallel; and iteratively dispatching a next m-n design cells in the verification order as design cells are selected, verified, and dequeued until a last design cells has been dispatched.
Claim 11
Dependent Claim
94 words
The method of claim 8 wherein providing the plurality of design cells comprises: examining the plurality of design cells in the verification order for data dependencies; dispatching for verification a first design cell determined to have no data dependencies; removing the dispatched design cell from further examination; and repeatedly examining remaining ones of the plurality of design cells in the verification order for data dependencies, dispatching for verification a first design cell among the remain ones to have no data dependencies, and removing the dispatched design cells until a last design cell is dispatched.
Claim 12
Dependent Claim
60 words
The method of claim 8 herein providing the plurality of design cells comprises: selecting up to n design cells having no data dependencies in the verification order; dispatching the up to n design cells; waiting for the up to n design cells to be verified in parallel; and repeatedly selecting, dispatching, and waiting until a last design cell is dispatched.
Claim 13
Dependent Claim
36 words
The method of claim 1 further comprises: injecting a number of new intervening constituent design cells to re-express a design cell in terms of the newly injected intervening constituent design cells before reordering the hierarchical organization.
Claim 14
Dependent Claim
31 words
The method of claim 12 , wherein injecting the new intervening constituent design cells comprises a selected one of a number of pattern based recognition techniques and a placement based technique.
Claim 15
Dependent Claim
40 words
The method of claim 13 , wherein the placement based technique comprises: determining a number of metrics to profile placements of constituent design cells of the design cell; and generating the new intervening constituent design cells using the determined metrics.
Claim 16
Dependent Claim
113 words
A machine readable medium having stored thereon machine executable instructions to implement a method comprising: receiving a hierarchical organization for a plurality of design cells comprising an integrated circuit design, said hierarchical organization defining at least two layers of design cells, a higher layer in the hierarchical organization corresponding to parent design cells, said parent design cells having data dependencies on respective child design cells corresponding to one or more lower layers in the hierarchical organization; and reordering the hierarchical organization into a verification order to increase distances between positions in the verification order corresponding to the child design cells and positions in the verification order corresponding to the respective parent design cells.
Claim 17
Dependent Claim
113 words
A machine readable medium having stored thereon machine executable instructions to implement a method comprising: receiving a hierarchical organization for a plurality of design cells comprising an integrated circuit design, said hierarchical organization defining at least two layers of design cells, a higher layer in the hierarchical organization corresponding to parent design cells, said parent design cells having data dependencies on respective child design cells corresponding to one or more lower layers in the hierarchical organization; and reordering the hierarchical organization into a verification order to increase distances between positions in the verification order corresponding to the child design cells and positions in the verification order corresponding to the respective parent design cells.
Claim 18
Dependent Claim
78 words
The machine readable medium of claim 15 wherein reordering the hierarchical organization comprises: generating a topological order to define topological relationships between sets of child/parent design cells; generating a sequential order for the plurality of design cells wherein all design cells from each layer of the hierarchical organization are sequentially listed in the sequential order; and switching positions among design cells in the sequential order to increase the distances in the verification order without violating the topological relationships.
Claim 19
Dependent Claim
28 words
The machine readable medium of claim 16 wherein the topological order comprises a depth-first sort list which numbers design cells based on layer positions in the hierarchical organization.
Claim 20
Dependent Claim
43 words
The machine readable medium of claim 16 wherein the sequential order comprises a breadth-first sort list which sequentially numbers the plurality of design cells starting with a first cell in a first layer and ending with a last cell in a last layer.
Claim 21
Dependent Claim
58 words
The machine readable medium of claim 16 wherein switching positions without violating the topological relationships comprises: locating a position corresponding to a first parent design cell; and moving the position corresponding to the first parent design cell to a later verification position without passing a position corresponding to a parent design cell of the first parent design cell.
Claim 22
Dependent Claim
53 words
The machine readable medium of claim 16 wherein switching positions without violating the topological relationships comprises: locating a position corresponding to a first parent design cell; and moving the position corresponding to the first parent design cell to a later verification position without passing a position corresponding to a higher order topological layer.
Claim 23
Dependent Claim
50 words
The machine readable medium of claim 15 wherein the distances in the verification order between the positions corresponding to the child design cells and the positions corresponding to the respective parent design cells provide a lower probability of data dependencies between subsequently ordered design cells compared to the hierarchical organization.
Claim 24
Dependent Claim
34 words
The machine readable medium of claim 15 further comprising: providing the plurality of design cells for verification according to the verification order, multiple design cells having no data dependencies to be verified in parallel.
Claim 25
Dependent Claim
76 words
The machine readable medium of claim 22 wherein providing the plurality of design cells comprises: dispatching a first m design cells in the verification order to a verification queue, n design cells that have no data dependencies to be selected, verified, and dequeued from the queue in parallel; and iteratively dispatching a next m-n design cells in the verification order as design cells are selected, verified, and dequeued until a last design cells has been dispatched.
Claim 26
Dependent Claim
96 words
The machine readable medium of claim 22 wherein providing the plurality of design cells comprises: examining the plurality of design cells in the verification order for data dependencies; dispatching for verification a first design cell determined to have no data dependencies; removing the dispatched design cell from further examination; and repeatedly examining remaining ones of the plurality of design cells in the verification order for data dependencies, dispatching for verification a first design cell among the remain ones to have no data dependencies, and removing the dispatched design cells until a last design cell is dispatched.
Claim 27
Dependent Claim
62 words
The machine readable medium of claim 22 wherein providing the plurality of design cells comprises: selecting up to n design cells having no data dependencies in the verification order; dispatching the up to n design cells; waiting for the up to n design cells to be verified in parallel; and repeatedly selecting, dispatching, and waiting until a last design cell is dispatched.
Claim 28
Dependent Claim
38 words
The machine readable medium of claim 15 further comprises: injecting a number of new intervening constituent design cells to re-express a design cell in terms of the newly injected intervening constituent design cells before reordering the hierarchical organization.
Claim 29
Dependent Claim
33 words
The machine readable medium of claim 26 , wherein injecting the new intervening constituent design cells comprises a selected one of a number of pattern based recognition techniques and a placement based technique.
Claim 30
Dependent Claim
42 words
The machine readable medium of claim 27 , wherein the placement based technique comprises: determining a number of metrics to profile placements of constituent design cells of the design cell; and generating the new intervening constituent design cells using the determined metrics.
Claim 31
Dependent Claim
135 words
A computer system comprising: a computer readable storage medium to store computer executable instructions; and one or more processors coupled to the computer readable medium to execute the instructions, executing said instructions to cause the processors to receive a hierarchical organization for a plurality of design cells comprising an integrated circuit design, said hierarchical organization defining at least two layers of design cells, a higher layer in the hierarchical organization corresponding to parent design cells, said parent design cells having data dependencies on respective child design cells corresponding to one or more lower layers in the hierarchical organization; and reorder the hierarchical organization into a verification order to increase distances between positions in the verification order corresponding to the child design cells and positions in the verification order corresponding to the respective parent design cells.
Claim 32
Dependent Claim
135 words
A computer system comprising: a computer readable storage medium to store computer executable instructions; and one or more processors coupled to the computer readable medium to execute the instructions, executing said instructions to cause the processors to receive a hierarchical organization for a plurality of design cells comprising an integrated circuit design, said hierarchical organization defining at least two layers of design cells, a higher layer in the hierarchical organization corresponding to parent design cells, said parent design cells having data dependencies on respective child design cells corresponding to one or more lower layers in the hierarchical organization; and reorder the hierarchical organization into a verification order to increase distances between positions in the verification order corresponding to the child design cells and positions in the verification order corresponding to the respective parent design cells.
Claim 33
Dependent Claim
81 words
The computer system of claim 29 wherein to reorder the hierarchical organization, the processor are to: generate a topological order to define topological relationships between sets of child/parent design cells; generate a sequential order for the plurality of design cells wherein all design cells from each layer of the hierarchical organization are sequentially listed in the sequential order; and switch positions among design cells in the sequential order to increase the distances in the verification order without violating the topological relationships.
Claim 34
Dependent Claim
61 words
The computer system of claim 30 wherein to switch positions without violating the topological relationships, the processors are to: locate a position corresponding to a first parent design cell; and move the position corresponding to the first parent design cell to a later verification position without passing a position corresponding to a parent design cell of the first parent design cell.
Claim 35
Dependent Claim
56 words
The computer system of claim 30 wherein to switch positions without violating the topological relationships, the processors are to: locate a position corresponding to a first parent design cell; and move the position corresponding to the first parent design cell to a later verification position without passing a position corresponding to a higher order topological layer.
Claim 36
Dependent Claim
49 words
The computer system of claim 29 wherein the distances in the verification order between the positions corresponding to the child design cells and the positions corresponding to the respective parent design cells provide a lower probability of data dependencies between subsequently ordered design cells compared to the hierarchical organization.
Claim 37
Dependent Claim
40 words
The computer system of claim 29 wherein executing the instructions further causes the processors to: provide the plurality of design cells for verification according to the verification order, multiple design cells having no data dependencies to be verified in parallel.
Claim 38
Dependent Claim
79 words
The computer system of claim 34 wherein to provide the plurality of design cells, the processors are to: dispatch a first m design cells in the verification order to a verification queue, n design cells that have no data dependencies to be selected, verified, and dequeued from the queue in parallel; and iteratively dispatch a next m-n design cells in the verification order as design cells are selected, verified, and dequeued until a last design cells has been dispatched.
Claim 39
Dependent Claim
99 words
The computer system of claim 34 wherein to provide the plurality of design cells, the processors are to: examine the plurality of design cells in the verification order for data dependencies; dispatch for verification a first design cell determined to have no data dependencies; remove the dispatched design cell from further examination; and repeatedly examine remaining ones of the plurality of design cells in the verification order for data dependencies, dispatch for verification a first design cell among the remain ones to have no data dependencies, and remove the dispatched design cells until a last design cell is dispatched.
Claim 40
Dependent Claim
65 words
The computer system of claim 34 wherein to provide the plurality of design cells, the processors are to: select up to n design cells having no data dependencies in the verification order; dispatch the up to n design cells; wait for the up to n design cells to be verified in parallel; and repeatedly select, dispatch, and wait until a last design cell is dispatched.
References Cited (Backward Citations)
US5497334A
Cited
US6113647A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-05-27 | 2005-11-26 | 2006-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-05-27 | 2009-11-26 | 2010-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-05-27 | 2013-11-26 | 2014-05-28 | $7700.00 | Window Closed / Lapsed |