Optimal timing-driven cloning under linear delay model

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.