Functional timing analysis for characterization of virtual component blocks

• US 7,346,872 B2
• Filed: 09/24/2002
• Issued: 03/18/2008
• Est. Priority Date: 12/29/1998
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Palmero, Robert J., Mortazavi, Mohammad S., Sakallah, Karem A., Yalcin, Hakan, Bamji, Cyrus
• Primary Examiner(s): Chiang; Jack
• Assistant Examiner(s): Memula; Suresh
• Application Number:
  US10/255,119
• Publication Number:
  US 20030140324A1
• Time in Patent Office: 2,002 Days
• Field of Search: 716/6
• US Class Current: 716/108
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A system and method for performing a timing analysis on virtual component blocks or other circuit models is provided wherein functional information obtained from the circuit'"'"'s control inputs and their useful combinations is used to improve accuracy. The control inputs and data inputs for a circuit block are identified. Each functionally meaningful or useful control input combination is applied to the circuit block, and the topological delay for the data inputs are determined only along the paths that are not blocked by the control inputs. The delays along paths that are blocked are ignored. The analysis is further augmented by determining the topological delay for all paths originating at control inputs, without regard to blocking of paths, so as to reduce the chance for possible underestimation of delays from the data inputs. A final timing model may include the combination of maximum delays along data paths for each combination of control inputs, and maximum delays along paths originating from each of the control inputs. The delay analysis may account for different input slews and load capacitances, and the results may be expressed in tabular or matrix form. A useful technique for condensing time delay information (whether scalar or tabular in form) is also provided, to simplify timing characterization of a virtual component block or circuit model. Delay tables or matrixes that are “close” (i.e., within a specified tolerance) may be combined into a single table or matrix.

Claims

1. A method of merging a set of delay tables, each of said delay tables comprising as elements a plurality of delay values, said method comprising the steps of:

merging into a new delay table a group of delay tables whose elements fall within a specified tolerance of the elements in similar relative positions of all other delay tables within the group, wherein said delay tables are merged based on a closeness with respect to the specified tolerance;

selecting as elements for the new delay table a maximum of all the elements in similar relative positions of all the delay tables in the group;

calculating, individually for each delay table, an aggregate sum of all of the elements in the delay table; and

selecting a set of closeness candidates for a given delay table based upon said specified tolerance and a size of said given delay table, said set of closeness candidates including said group of delay tables.

2. The method of claim 1, wherein the selected elements have maximum delay values.

3. The method of claim 1, wherein the selected elements have minimum delay values.

4. The method of claim 1 wherein the aggregate sum for the given delay table T comprises:

$\mathrm{sum}<br><br>\left(T\right)=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br><br><br>\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br><br><br>t_{\mathrm{ij}}<br><br>$

where m is a number of different input slews and n is a number of load capacitances.

5. The method of claim 1 further comprising:

ordering the set of delay tables in decreasing size of the aggregate sum for each delay table to generate an ordered set of delay tables.

6. The method of claim 1 wherein the set of closeness candidates for the given delay table T^x comprises:

sum(T^x)−

sum(T^k)≦

m·

n·

TOL

where m is a number of different input slews, n is a number of different load capacitances, T^x is a current delay table, T^k represents all remaining delay tables, and TOL represents a tolerance delay.

7. A method of merging a set of tables into a reduced set of tables, each of said tables comprising a plurality of elements, said method comprising the steps of:

comparing each element of a given table to a corresponding element in a same relative position in one or more of said set of tables;

merging said given table with one or more of said set of tables when all elements of said given table fall within a specified tolerance of the corresponding element in the same relative position in one or more of said set of tables, wherein the tables are merged based on a closeness with respect to the specified tolerance, thereby generating a merged table;

selecting elements of said merged table from said given table and one or more of said set of tables merged with said given table, the selected elements comprising either each element having a maximum value when compared against elements in the same relative position in said given table and one or more of said set of tables, or else each having a minimum value when compared against elements in the same relative position in said given table and one or more of said set of tables;

calculating for said given table, an aggregate sum of all of the elements in the given delay table; and

selecting a set of closeness candidates for said given delay table based upon said specified tolerance and a size of said given delay table, said set of closeness candidates including said set of tables.

8. The method of claim 7 wherein the aggregate sum for the given delay table T comprises:

$\mathrm{sum}<br><br>\left(T\right)=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br><br><br>\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br><br><br>t_{\mathrm{ij}}<br><br>$

where m is a number of different input slews and n is a number of load capacitances.

9. The method of claim 7 further comprising:

ordering the set of tables in decreasing size of the aggregate sum for each delay table to generate an ordered set of delay tables.

10. The method of claim 7 wherein the set of closeness candidates for the given delay table T^x comprises:

sum(T^x)−

sum(T^k)≦

m·

n·

TOL

where m is a number of different input slews, n is a number of different load capacitances, T^x is a current delay table, T^k represents all remaining delay tables, and TOL represents a tolerance delay.

11. A computer readable medium having stored therein one or more sequences of instructions for merging delay tables, each of said delay tables comprising as elements a plurality of delay values, said one or more sequences of instructions causing one or more processors to perform a plurality of acts, said acts comprising:

receiving said delay tables;

merging into a new delay table a group of delay tables whose elements fall within a specified tolerance of the elements in similar relative positions of all other delay tables within the group, wherein the delay tables are merged based on a closeness with respect to the specified tolerance;

selecting as elements for the new delay table a maximum of all the elements in similar relative positions of all the delay tables in the group;

calculating, individually for each delay table, an aggregate sum of all of the elements in the delay table; and

selecting a set of closeness candidates for a given delay table based upon said specified tolerance and a size of said given delay table, said set of closeness candidates including said group of delay tables.

12. The computer readable medium of claim 11, wherein said acts further comprise:

sequentially ordering said plurality of delay tables based upon the aggregate sum of all the elements for each delay table.

13. The computer readable medium of claim 11, wherein the selected elements have maximum delay values.

14. The computer readable medium of claim 11, wherein the selected elements have minimum delay values.

15. An apparatus for merging a set of delay tables, each of said delay tables comprising as elements a plurality of delay values, said apparatus comprising:

means for merging into a new delay table a group of delay tables whose elements fall within a specified tolerance of the elements in similar relative positions of all other delay tables within the group, wherein the delay tables are merged based on a closeness with respect to the specified tolerance;

means for selecting as elements for the new delay table a maximum of all the elements in similar relative positions of all the delay tables in the group;

means for calculating, individually for each delay table, an aggregate sum of all of the elements in the delay table; and

means for selecting a set of closeness candidates for a given delay table based upon said specified tolerance and a size of said given delay table, said set of closeness candidates including said group of delay tables.

16. The apparatus of claim 15, wherein the selected elements have maximum delay values.

17. The apparatus of claim 15, wherein the selected elements have minimum delay values.

18. The apparatus of claim 15 wherein the aggregate sum for the given delay table T comprises:

$\mathrm{sum}<br><br>\left(T\right)=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br><br><br>\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br><br><br>t_{\mathrm{ij}}<br><br>$

where m is a number of different input slews and n is a number of load capacitances.

19. The apparatus of claim 15 further comprising:

means for ordering the set of delay tables in decreasing size of the aggregate sum for each delay table to generate an ordered set of delay tables.