Optimal timing-driven cloning under linear delay model

1. A computer-implemented method of cloning an original gate in a circuit design, comprising:

receiving a description of the circuit design which includes locations for sources and sinks of the original gate, by executing first instructions in a computer system;

iteratively partitioning the sinks into different sets of clusters wherein the original gate is assigned to a first one of the clusters in a given set and at least one cloned gate is assigned to at least a second one of the clusters in the given set, by executing second instructions in the computer system;

for each set of clusters, computing a figure of merit for a location of the cloned gate which optimizes timing based on delay that is proportional to a distance between the cloned gate location and the location of a given sink in the second cluster, by executing third instructions in the computer system;

selecting one of the sets of clusters having a highest figure of merit as a best solution, by executing fourth instructions in the computer system; and

storing the description of the circuit design with a final location of the cloned gate corresponding to the best solution, by executing fifth instructions in the computer system.

2. The method of claim 1 wherein the description includes a location for the original gate, and further comprising changing the location of the original gate to a new location which optimizes timing based on delay that is proportional to the distance between the new location and the location of a given sink in the first cluster, by executing sixth instructions in the computer system.

3. The method of claim 1 wherein the sinks are partitioned using boundaries of Voronoi polygons defined by a diamond region surrounding the original gate.

4. The method of claim 1 wherein the figure of merit is worst slack.

5. The method of claim 1 wherein the figure of merit is a sum of slacks at the sinks in the second cluster.

6. The method of claim 1 wherein the figure of merit is a combination of worst slack and a sum of slacks at the sinks in the second cluster.

7. A computer system comprising:

one or more processors which process program instructions;

a memory device connected to said one or more processors; and

program instructions residing in said memory device which receive a description of a circuit design having locations for sources and sinks of an original gate, iteratively partition the sinks into different sets of clusters wherein the original gate is assigned to a first one of the clusters in a given set and at least one cloned gate is assigned to at least a second one of the clusters in the given set, for each set of clusters compute a figure of merit for a location of the cloned gate which optimizes timing based on delay that is proportional to a distance between the cloned gate location and the location of a given sink in the second cluster, select one of the sets of clusters having a highest figure of merit as a best solution, and store the description of the circuit design with a final location of the cloned gate corresponding to the best solution.

8. The computer system of claim 7 wherein the description includes a location for the original gate, and said program instructions further change the location of the original gate to a new location which optimizes timing based on delay that is proportional to the distance between the new location and the location of a given sink in the first cluster.

9. The computer system of claim 7 wherein the sinks are partitioned using boundaries of Voronoi polygons defined by a diamond region surrounding the original gate.

10. The computer system of claim 7 wherein the figure of merit is worst slack.

11. The computer system of claim 7 wherein the figure of merit is a sum of slacks at the sinks in the second cluster.

12. The computer system of claim 7 wherein the figure of merit is a combination of worst slack and a sum of slacks at the sinks in the second cluster.

13. A computer program product comprising:

a computer-readable storage medium; and

program instructions residing in said storage medium which, when executed by a computer, receive a description of a circuit design having locations for sources and sinks of an original gate, iteratively partition the sinks into different sets of clusters wherein the original gate is assigned to a first one of the clusters in a given set and at least one cloned gate is assigned to at least a second one of the clusters in the given set, for each set of clusters compute a figure of merit for a location of the cloned gate which optimizes timing based on delay that is proportional to a distance between the cloned gate location and the location of a given sink in the second cluster, select one of the sets of clusters having a highest figure of merit as a best solution, and store the description of the circuit design with a final location of the cloned gate corresponding to the best solution.

14. The computer program product of claim 13 wherein the description includes a location for the original gate, and said program instructions further change the location of the original gate to a new location which optimizes timing based on delay that is proportional to the distance between the new location and the location of a given sink in the first cluster.

15. The computer program product of claim 13 wherein the sinks are partitioned using boundaries of Voronoi polygons defined by a diamond region surrounding the original gate.

16. The computer program product of claim 13 wherein the figure of merit is worst slack.

17. The computer program product of claim 13 wherein the figure of merit is a sum of slacks at the sinks in the second cluster.

18. The computer program product of claim 13 wherein the figure of merit is a combination of worst slack and a sum of slacks at the sinks in the second cluster.