Ultra-fast interconnect driven cell cloning for minimizing critical path delay Conference Paper uri icon


  • In a complete physical synthesis flow, optimization transforms, that can improve the timing on critical paths that are already well-optimized by a series of powerful transforms (timing driven placement, buffering and gate sizing) are invaluable. Finding such a transform is quite challenging, to say nothing of efficiency. This work explores innovative cloning (gate duplication) techniques to improve timing-closure in a physical synthesis environment. With a buffer-aware interconnect timing model, new polynomial-time optimal algorithms are proposed for timing-driven cloning, including both finding optimal sink partitions (identifying the fan-outs) for the original and the duplicated gates, as well as physical locations for both gates. In particular, we present an O(m)-time optimal algorithm to minimize the worst slack if the original gate is movable, and an O(m log m) algorithm if the original gate is fixed, where $m$ is the number of fan-outs. To the best of our knowledge, this work is the first one considering the timing-driven cloning problem under a buffer-aware interconnect delay model. For a hundred testcases in 45nm technology node, we demonstrate significant timing improvement due to our cloning techniques as compared to other existing timing-optimization transforms. Extensions to other factors, such as wirelength, FOM and placement obstacles are further discussed. Copyright 2010 ACM.

name of conference

  • Proceedings of the 19th international symposium on Physical design

published proceedings

  • Proceedings of the 19th international symposium on Physical design

author list (cited authors)

  • Li, Z., Papa, D. A., Alpert, C. J., Hu, S., Shi, W., Sze, C., & Zhou, Y.

citation count

  • 4

complete list of authors

  • Li, Zhuo||Papa, David A||Alpert, Charles J||Hu, Shiyan||Shi, Weiping||Sze, Cliff||Zhou, Ying

publication date

  • January 2010