Algorithms for simultaneous consideration of multiple physical synthesis transforms for timing closure

ABSTRACT

We propose a post-placement physical synthesis algorithm that can apply multiple circuit synthesis and placement transforms on a placed circuit to improve the critical path delay under area constraints by simultaneously considering the benefits and costs of all transforms (as opposed to considering them sequentially after applying each transform). The circuit transforms we employ include, but are not limited to, incremental placement, two types of buffer insertion, cell resizing and cell replication. The problem is modeled as a min-cost network flow problem, in which nodes represent circuit transform options. By carefully determining the structure of the network graph and the cost of each arc, a set of near-optimal transform options can be obtained as those whose corresponding nodes in the network graph have the min-cost flow passing through them. We also tie the transform selection network graph to a detailed placement network graph with TD arc costs for cell movements. This enables our algorithms to incorporate considerations of detailed placement cost for each synthesis transform along with the basic cost of applying the transform in the circuit. We have tested our algorithms on three sets of benchmarks under 3--10% area increase constraints, and obtained up to 48% and an average of 27.8% timing improvement. Our average improvement is relatively 40% better (8.2% better by an absolute measure) than applying the same set of transforms in a good sequential order that is used in many current techniques. Considering only synthesis transforms (no replacement), our technique is relatively 50% better than the sequential approach.

REFERENCES

• 1: R. Ahuja, et al., "A Network Simplex Algorithm with O(n) Consecutive Degenerate Pivots", Operations Research Letters (ORL), pp. 1417--1436, 1995.
• 2: T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1998.
• 3: Olivier Coudert, Gate sizing for constrained delay/power/area optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.465-472, Dec. 1997 [doi>10.1109/92.645073]
• 4: Wilm Donath , Prabhakar Kudva , Leon Stok , Lakshmi Reddy , Andrew Sullivan , Kanad Chakraborty , Paul Villarrubia, Transformational placement and synthesis, Proceedings of the conference on Design, automation and test in Europe, p.194-201, March 27-30, 2000, Paris, France [doi>10.1145/343647.343732]
• 5: Shantanu Dutt , Huan Ren , Fenghua Yuan , Vishal Suthar, A network-flow approach to timing-driven incremental placement for ASICs, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233577]
• 6: J. Fishburn and A. Dunlop, "Tilos: A posynomial programming approach to transistor sizing," ICCAD'85, pp. 326--328, 1985.
• 7: Shiyan Hu , Mahesh Ketkar , Jiang Hu, Gate sizing for cell library-based designs, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278690]
• 8: Yanbin Jiang , Sachin S. Sapatnekar , Cyrus Bamji , Juho Kim, Interleaving buffer insertion and transistor sizing into a single optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.4, p.625-633, Dec. 1998 [doi>10.1109/92.736136]
• 9: Lalgudi N. Kannan , Peter R. Suaris , Hong-Gee Fang, A methodology and algorithms for post-placement delay optimization, Proceedings of the 31st annual conference on Design automation, p.327-332, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196399]
• 10: D. Kim, and P. Pardalos, "A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure", ORL, pp. 195--203, 1999.
• 11: Combining Technology Mapping with Post-Placement Resynthesis for Performance Optimization, Proceedings of the International Conference on Computer Design, p.616, October 05-05, 1998
• 12: H. Ren and S. Dutt, "A Network-Flow Based Cell Sizing Algorithm", The International Workshop on Logic Synthesis, pp. 7--14, 2008.
• 13: Ankur Srivastava , Ryan Kastner , Chunhong Chen , Majid Sarrafzadeh, Timing driven gate duplication, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.42-51, January 2004 [doi>10.1109/TVLSL2003.820527]
• 14: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree network for minimal Elmore delay," Proc. IEEE Int. Symp. Circuits Syst., pp. 865--868, 1990.
• 15: Wonjoon Choi , Kia Bazargan, Incremental Placement for Timing Optimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.463, November 09-13, 2003 [doi>10.1109/ICCAD.2003.84]
• 16: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Timing-driven placement using design hierarchy guided constraint generation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.177-180, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774598]