Decentralized dynamically scheduled parallel static timing analysis

Abstract

A method for performing a parallel static timing analysis in which multiple processes independently update a timing graph without requiring communication through a central coordinator module. Local processing queues are used to reduce locking overhead without causing excessive load imbalance. A parallel analysis is conducted on a circuit design represented by a timing graph formed by a plurality of interconnected nodes, the method including: using a computer for creating a shared work queue of ready to process independent nodes; assigning the independent nodes from the work queue to at least two parallel computation processes, simultaneously performing node analysis computations thereof; and modifying the circuit design by updating values of the processed independent nodes obtained from the node analysis, the at least two parallel computation processes independently updating the shared work queue to process a new plurality of independent nodes.