Timing optimization for multisource nets: Characterization and optimal repeater insertion

This paper presents new results in the area of timing optimization for mult isource nets. The augmented RC-diameter (ARD) is suggested as a natural and practical performance measure and a linear time algorithm for computing th e ARD of a multisource net is presented, Building on the ARD measure, He ch aracterize the multisource optimization problem in terms of operations on p iece-wise linear functions. This characterization is then used to develop a n algorithm for optimal repeater insertion: for a given multisource topolog y the algorithm efficiently identities an optimal assignment of repeaters t o prescribed insertion points under the "min cost timing feasible'' problem formulation. The algorithm has been implemented and computational results demonstrate the viability of the approach.