Distributed static timing analysis

A method of performing an incremental timing update in a distributed static timing analysis of a network of logic circuits comprising interconnected nodes, comprising the steps of:

• partitioning said network into a plurality of partitions, each partition including a subset of said nodes;
• assigning each of said partitions to a separate process for determining timing values for nodes in each partition;
• introducing a change to a partition, wherein said change has an effect on said timing values;
• inhibiting inputs affecting timing values from processes associated with partitions different from said changed partition;
• analyzing the effects of a change in one of said different partitions while said inhibition is active;
• performing an incremental update, corresponding to said change, of the timing values for said changed partition;
• after said incremental update is performed, releasing said inhibited inputs,
• processing said inputs;
• and
• outputting timing values resulting from said processing step to processes of related partitions.

A method for detecting global loops in a network of logic circuits comprising interconnected nodes, during a distributed static timing analysis of said network, said method comprising the steps of:

• dividing said network into at least first and second partitions, said network including a global loop between said first and second partitions;
• performing first and second processes for determining timing values for nodes in said first and second partitions, respectively;
• establishing a communication mechanism between said first and second processes;
• and
• using said communication mechanism to detect and break said global loop, to determine timing values for nodes included in said global loop.

A computer-usable medium storing computer-executable instructions, said instructions when executed implementing a process of distributed static timing analysis of a network of logic circuits comprising interconnected predecessor nodes and successor nodes, wherein predecessor nodes provide signals characterized by timing values to successor nodes, said process comprising the steps of:

• partitioning said network into a plurality of partitions, each partition comprising a subset of said predecessor and successor nodes;
• executing a separate timing analysis process for each of said partitions, each of said processes executing substantially in parallel;
• and
• issuing, to at least a first of said processes corresponding to a first partition containing a successor node, a request for timing information for said successor node,
• wherein said first request initiates a depth-first search (DFS) of predecessor nodes of said successor node to respond to said request.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of distributed static timing analysis of a network of logic circuits comprising interconnected predecessor nodes and successor nodes, wherein predecessor nodes provide signals characterized by timing values to successor nodes, said method steps comprising:

• partitioning said network into a plurality of partitions, each partition comprising a subset of said predecessor and successor nodes;
• executing a separate timing analysis process for each of said partitions, each of said processes executing substantially in parallel;
• and
• issuing, to at least a first of said processes corresponding to a first partition containing a successor node, a request for timing information for said successor node,
• wherein said request initiates a depth-first search (DFS) of predecessor nodes of said successor node to respond to said request.