HIGHLY THREADED STATIC TIMER

• US 20090327985A1
• Filed: 06/26/2008
• Published: 12/31/2009
• Est. Priority Date: 06/26/2008
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Rubin, Steven M., Garreton, Gilda, Mains, Robert E., Chen, George J.
• Granted Patent: US 7,958,474 B2
• Time in Patent Office: Days
• US Class Current: 716/113
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

Various methods and apparatus for executing a multithreaded algorithm that performs a static timing analysis of an integrated circuit chip (chip) include logic for traversing the chip to identify a plurality of components (cells or nodes) within a chip circuit of the chip. A waveform graph is defined for the identified nodes. One or more virtual graphs are generated from the waveform graph. The plurality of nodes in the one or more virtual graphs are processed using multiple threads to obtain quadruplet of time domain dataset values representing the different modes of propagation for each node. A timing check is performed at an end node of the virtual graphs using the quadruplet of time domain dataset values to determine any timing violation within the chip design.

Claims

1. A method for executing a multithreaded algorithm to perform a static timing analysis of a chip, comprising:

traversing the chip to identify a plurality of components within a logic circuit of the chip, each of the plurality of components including a plurality of nodes;

defining a waveform graph for the plurality of nodes;

generating a first and a second virtual graph from the waveform graph;

assigning the first virtual graph for running an early mode propagation;

assigning the second virtual graph for running a late mode propagation;

processing the plurality of nodes in the first and the second virtual graphs independently using a first and a second thread to compute arrival time domain dataset values at each of the plurality of nodes;

performing a timing check at end point nodes in each of the first and the second virtual graphs using the time domain dataset values to determine any timing violations within the chip circuit; and

processing the plurality of nodes in the first and the second virtual graphs independently using a third and a fourth thread to compute required time domain dataset values at each of the plurality of nodes.

2. The method of claim 1, wherein the processing further including,

a. identifying a corner case;

and

b. computing arrival time and required time domain dataset values for each of the nodes in the first and second virtual graphs for the identified corner case,

wherein the timing check is performed for the corner case after the computation of the arrival time at each of the plurality of nodes and prior to the computation of the required time at each of the plurality of nodes.

3. The method of claim 1, wherein performing a timing check further including,

identifying end point nodes in each of the first and second virtual graphs;

and

performing the timing check at the end point nodes using cross computation to determine any timing violation within the chip circuit of the chip,

wherein the cross computation is performed by exchanging timing information associated with the end point nodes of the first virtual graph and the end point nodes of the second virtual graph, the timing information including time domain dataset values.

4. A method for executing a multithreaded algorithm to perform a static timing analysis of a chip, comprising:

traversing the chip to identify a plurality of components within a logic circuit of the chip, each of the plurality of components including a plurality of nodes;

defining a waveform graph for the plurality of nodes;

generating a first and a second virtual graph from the waveform graph;

assigning the first virtual graph for running an early mode propagation;

assigning the second virtual graph for running a late mode propagation;

processing the plurality of nodes in the first and the second virtual graphs independently using a plurality of threads to compute time domain dataset values at each of the plurality of nodes; and

performing a timing check at end nodes in each of the first and the second virtual graphs using the time domain dataset values to determine any timing violations within the chip circuit.

5. The method of claim 4, wherein obtaining the time domain dataset values further including,

capturing independent waveform information representing different time domain dataset values associated with each of early mode propagation and late mode propagation at each node,

wherein the waveforms associated with early mode propagation provides information related to minimum rise, minimum fall, and wherein the waveforms associated with late mode propagation provides information related to maximum rise and maximum fall.

6. The method of claim 4, wherein the processing further including,

identifying a corner case;

and

computing time domain dataset values for each of the nodes in the first and second virtual graphs for the identified corner case.

7. The method of claim 6, wherein each node is associated with a plurality of time domain dataset values for the corner case.

8. The method of claim 4, wherein performing a timing check further including,

identifying end point nodes in each of the first and second virtual graph;

and

performing the timing check at the end point nodes using cross computation to determine any timing violation within the chip circuit of the chip.

9. The method of claim 8, wherein cross computation is performed by exchanging timing information associated with the end point nodes of the first virtual graph and the end point nodes of the second virtual graph, the timing information including time domain dataset values.

10. The method of claim 6, wherein the time domain dataset values for each node depends on the time domain dataset values of a corresponding preceding node in each of the first and second virtual graphs for the corner case.

11. The method of claim 4, wherein the processing of the plurality of nodes includes a forward propagation processing and a backward propagation processing, the forward propagation processing computing an arrival time and the backward propagation processing computing a required time at each node of the first and second virtual graph.

12. The method of claim 11, wherein the forward propagation processing or the backward propagation processing at the first and second virtual graphs is performed concurrently using multiple threads.

13. The method of claim 11, wherein forward propagation processing and backward propagation processing at the first or second virtual graph is performed sequentially.

14. The method of claim 13, wherein forward propagation processing and backward propagation processing at each of the first or second virtual graph is performed using distinct threads.

15. The method of claim 4, wherein generating a virtual graph further including,

tagging the time domain dataset value associated with each node with a buffer information of a clock header node from which the node emerged.

16. The method of claim 15, wherein the processing of the nodes further including,

detecting a convergence node at the first and second virtual graphs for the corner case where a plurality of nodes converge, each of the plurality of nodes converging at the convergence node emerging from a single clock header node;

identifying a worse time domain dataset value at the convergence node by comparing the time domain dataset values associated with each of the converging nodes in the first and second virtual graph;

retaining the identified worse time domain dataset value at the convergence node; and

pruning the remaining time domain dataset values at the convergence node in the first and second virtual graphs, wherein the pruning is done based on the tag associated with the time domain dataset values for respective node of the first and second virtual graphs.

17. A method for executing a multithreaded algorithm to perform a static timing analysis of a chip, comprising:

traversing the chip to identify a plurality of components with in a chip circuit of the chip, each of the plurality of components including a plurality of nodes;

defining a waveform graph for the plurality of nodes;

generating a virtual graph identifying one or more domains in the waveform graph, each of the domains representing a unique transmission path from a clock header node through plurality of nodes associated with the clock header node of the waveform graph;

processing the plurality of nodes in each of the domains in the virtual graph using multiple threads to obtain time domain dataset values at each node, each thread assigned to process the plurality of nodes in each domain; and

performing a timing check to determine any timing violation within the chip circuit.

18. The method of claim 17, wherein the processing further including,

identifying a corner case;

and

computing time domain dataset values for each of the nodes in each of the domains of the virtual graph for the identified corner case.

19. The method of claim 18, wherein generating a virtual graph further including,

tagging each of the time domain dataset values at each node with a buffer information of a clock header node associated with the node, the tagging identifying the domain of the virtual graph to which the node belongs.

20. The method of claim 19, wherein processing the plurality of nodes further including,

detecting a convergence node where a plurality of nodes of a domain converge in the virtual graph, each of the plurality of nodes converging at the convergence node emerging from a single clock header node of the domain;

identifying a worse case time domain dataset value at the convergence node by comparing the time domain dataset values associated with each of the converging nodes in the virtual graph;

retaining the identified worse case time domain dataset value at the convergence node; and

pruning the remaining time domain dataset values at the convergence node in the virtual graph, wherein the pruning is done based on the tag associated with each of the time domain dataset values at the convergence node within the domain of the virtual graph.

21. The method of claim 17, wherein the processing of the plurality of nodes includes a forward propagation processing to compute an arrival time and a backward propagation processing for computing a required time at each node and wherein the forward propagation processing of the domains performed concurrently using multiple threads after propagation of a clock domain associated with the virtual graph.

22. A method for executing a multithreaded algorithm to perform a static timing analysis of a chip, comprising:

traversing the chip to identify a plurality of components with in a chip circuit of the chip, each of the plurality of components including a plurality of nodes;

defining a waveform graph for the plurality of nodes;

generating a first and second virtual graphs from the waveform graph;

defining one or more domains within each of the first and second virtual graphs, each of the domains representing a signal transmission path through plurality of nodes associated with a single header node at the first and second virtual graphs;

assigning the first virtual graph for running an early mode propagation;

assigning the second virtual graph for running a late mode propagation;

processing the plurality of nodes in each of the domains in the first and the second virtual graphs independently using a plurality of threads to obtain time domain dataset values at each of the plurality of nodes, each of the plurality of threads assigned to process a domain; and

performing a timing check at the first and second virtual graphs to determine any timing violations within the chip circuit.

23. The method of claim 22, wherein the processing further includes a forward propagation processing to compute an arrival time and a backward propagation processing to compute a required time at each node.

24. The method of claim 23, wherein the processing further including propagating a clock domain at each of the first and the second virtual graphs prior to forward propagation processing and backward propagation processing.

25. The method of claim 22, wherein the processing further including,

identifying a corner case;

and

computing time domain dataset values for each of the nodes in the first and second virtual graphs for the identified corner case, the time domain dataset values from the first virtual graph associated with early mode propagation and the time domain dataset values from the second virtual graph associated with late mode propagation.

26. The method of claim 22, wherein the processing of the nodes further including,

detecting a convergence node wherein a plurality of nodes of a domain within the first and the second virtual graphs converge, each of the plurality of nodes converging at the convergence node within the domain emerging from a single clock header;

identifying a worse case time domain dataset value at the convergence node by comparing the time domain dataset values associated with each of the converging nodes of the domain in the first and second virtual graph;

retaining the identified worse case time domain dataset value at the convergence node; and

pruning the remaining time domain dataset values at the convergence node in the domain in each of the first and the second virtual graphs, wherein the pruning is done based on a tag associated with the time domain dataset values for the respective node in the domain of the first and second virtual graphs.