Patent Document ID: 7707530
Application ID: 11941105
Patent Status: 1

Claim One:
1. In a computing device, a method for optimizing the timing-driven placement of one or more movable gates of a circuit in a physical synthesis flow, the computing device performs the method comprising: identifying at least one movable gate based on at least one selection criteria; generating a set of legalized candidate locations corresponding to at least one identified movable gate; generating a disjunctive timing graph based on the generated set of legalized candidate locations; determining an optimal location of at least one movable gate using a recursive branch-and-bound search of said disjunctive timing graph, wherein the recursive branch-and-bound search prunes at least one gate assignment when an upper bound on a worst-case negative slack value is not realizable from a partial gate assignment; and storing the optimal location of said at least one movable gate in the computing device, wherein a relaxed variation of static timing analysis (RSTA) is performed for internal nodes associated with a non-pruned partial gate assignment to obtain the upper bound on the worst-case negative slack value.