Incremental timing-driven, physical-synthesis using discrete optimization
View Patent ↗A method, data processing system and computer program product for optimizing the placement of logic gates of a subcircuit in a physical synthesis flow. A Path Smoothing utility identifies one or more movable gates based on at least one selection criteria. A set of legalized candidate locations corresponding to one or more identified movable gates is generated. A disjunctive timing graph based on the generated set of legalized candidate locations is then generated. An optimal location of one or more movable gate(s) is determined using a recursive branch-and-bound search and stored in the computing device.
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.
2. The method of claim 1 , wherein the selection criteria comprises at least one of:
identifying one or more critical gates in the circuit;
identifying one or more critical paths of the circuit; and
identifying one or more gates having the largest slack differential between an input timing point and an output timing point.
3. The method of claim 1 , wherein the set of legalized candidate locations is determined by a candidate location strategy, including at least one of: a cardinal direction approach, a legalized cardinal direction approach, and a nearest neighbor approach.
4. The method of claim 1 , wherein the disjunctive timing graph results from a combination of at least one optimization variable from among: gate placement, gate repowering, gate voltage threshold (V t ) assignment, and wire sizing.
5. The method of claim 1 , wherein a static timing analysis is not performed for internal nodes associated with a pruned gate assignment.
6. A data processing system comprising:
a processor;
a system memory coupled to the processor; and
a utility executing on the processor and having executable code for:
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 system memory, 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.
7. The data processing system of claim 6 , wherein the selection criteria comprises at least one of:
identifying one or more critical gates in the circuit;
identifying one or more critical paths of the circuit; and
identifying one or more gates having the largest slack differential between an input timing point and an output timing point.
8. The data processing system of claim 6 , wherein the set of legalized candidate locations is determined by a candidate location strategy, including at least one of: a cardinal direction approach, a legalized cardinal direction approach, and a nearest neighbor approach.
9. The data processing system of claim 6 , wherein the disjunctive timing graph results from a combination of at least one optimization variable from among: gate placement, gate repowering, gate voltage threshold (V t ) assignment, and wire sizing.
10. The data processing system of claim 6 , wherein a static timing analysis is not performed for internal nodes associated with a pruned gate assignment.
11. A computer program product comprising:
a computer storage device; and
program code on the computer storage device that when executed provides the functions of:
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 computer storage 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.
12. The computer program product of claim 11 , wherein code for implementing the selection criteria comprises code for:
identifying one or more critical gates in the circuit;
identifying one or more critical paths of the circuit; and
identifying one or more gates having the largest slack differential between an input timing point and an output timing point.
13. The computer program product of claim 11 , wherein the set of legalized candidate locations is determined by a candidate location strategy, including at least one of: a cardinal direction approach, a legalized cardinal direction approach, and a nearest neighbor approach.
14. The computer program product of claim 11 , wherein the disjunctive timing graph results from a combination of at least one optimization variable from among: gate placement, gate repowering, gate voltage threshold (V t ) assignment, and wire sizing.
15. The computer program product of claim 11 , wherein a static timing analysis is not performed for internal nodes associated with a pruned gate assignment.