Timing optimization for multi-source nets: Characterization and optimal repeater insertion

This paper presents new results in the area of timing optimization for multi-source nets. The Augmented RC-Diameter (ARD) is proposed as a natural and practical performance metric and a linear time algorithm for computing the ARD of a multi-source net is presented. Building on the ARD, an algorithm for optimal repeater insertion a's presented: for a given multi-source topology the algorithm efficiently identifies an optimal assignment of repeaters to prescribed insertion points under the ''min cost timing feasible'' problem formulation. The algorithm has been implemented and preliminary experimental results are promising.