Design closure driven delay relaxation based on convex cost network flow

ABSTRACT

Design closure becomes hard to achieve at physical layout stage due to the emergence of long global interconnects. Consequently, interconnect planning needs to be integrated in high level synthesis. Delay relaxation that assigns extra clock latencies to functional resources at RTL (Register Transfer Level) can be leveraged. In this paper we propose a general formulation for design closure driven delay relaxation problem. We show that the general formulation can be transformed into a convex cost integer dual network flow problem and solved in polynomial time using the convex cost-scaling algorithm in [1]. Experimental results validate the efficiency of the approach.

REFERENCES

• 1: Ravindra K. Ahuja , Dorit S. Hochbaum , James B. Orlin, Solving the Convex Cost Integer Dual Network Flow Problem, Management Science, v.49 n.7, p.950-964, July 2003 [doi>10.1287/mnsc.49.7.950.16384]
• 2: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 3: Jason Cong , Yiping Fan , Guoling Han , Xun Yang , Zhiru Zhang, Architectural Synthesis Integrated with Global Placement for Multi-Cycle Communication, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.536, November 09-13, 2003 [doi>10.1109/ICCAD.2003.35]
• 4: S. Ghiasi , E. Bozorgzadeh , S. Choudhuri , M. Sarrafzadeh, A unified theory of timing budget management, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.653-659, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382657]
• 5: Andrew V. Goldberg, An efficient implementation of a scaling minimum-cost flow algorithm, Journal of Algorithms, v.22 n.1, p.1-29, Jan. 1997 [doi>10.1006/jagm.1995.0805]
• 6: A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
• 7: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: C. E. Leiserson, F. M. Rose, and J. B. Saxe. Optimizing synchronous circuitry by retiming. In Advanced Research in VLSI: Proc. of the Third Caltech Conf., pages 86--116, Rockville, MD, 1983. Computer Science Press.
• 9: C. Lin and H. Zhou. Wire retiming as fixpoint computation. IEEE TVLSI, 13(12):1340--1348, December 2005.
• 10: C. Lin and H. Zhou. Optimal wire retiming without binary search. IEEE TCAD, 25(9):1577--1588, September 2006.
• 11: D. G. Luenberger. Linear and nonlinear programming. Addison-Wesley, Reading, Massachusetts, 1984.
• 12: R. Nair, C. L. Berman, P. S. Hauge, and E. J. Yoffa. Generation of Performance Constraints for Layout. IEEE TCAD, 8(8):860--874, August 1989.
• 13: Vidyasagar Nookala , Sachin S. Sapatnekar, A method for correcting the functionality of a wire-pipelined circuit, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996724]
• 14: L. Singhal , E. Bozorgzadeh, Fast timing closure by interconnect criticality driven delay relaxation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.792-797, November 06-10, 2005, San Jose, CA
• 15: Ankur Srivastava , Seda Ogrenci Memik , Bo-Kyung Choi , Majid Sarrafzadeh, Achieving Design Closure Through Delay Relaxation Parameter, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.54, November 09-13, 2003 [doi>10.1109/ICCAD.2003.24]
• 16: Chao-Yang Yeh , Malgorzata Marek-Sadowska, Minimum-Area Sequential Budgeting for FPGA, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.813, November 09-13, 2003 [doi>10.1109/ICCAD.2003.95]
• 17: H. Zhou and C. Lin. Retiming for wire pipelining in system-on-chip. IEEE TCAD, 23(9):1338--1345, September 2004.