Method to identify geometrically non-overlapping optimization partitions for parallel timing closure

Abstract

A method is provided to speed up timing optimization after placement by parallelizing the optimization step. The method includes performing multiple partitions in the set of timing critical paths such that each partition can be optimized independently in a separate processor. To eliminate the need for inter-processor communication, conditions of timing independence and physical independence are imposed on each partition, thereby defining sub-sets of endpoints and paths associated therewith. The optimizing is performed in parallel by the processors, each of the processors optimizing timing of the paths associated with the endpoints in respective sub-sets. In a preferred embodiment, an endpoint graph is constructed from the list of critical paths, where the endpoint graph has at least one vertex representing critical paths associated with a given endpoint. The partitioning step then includes the step of partitioning the endpoint graph to define sub-sets of vertices.