Early planning for clock skew scheduling during register binding

ABSTRACT

Design decisions made during high-level synthesis usually have great impacts on the later design stages. In this paper, We present a general framework, which plans for the clock skew scheduling in physical design stages during register binding in high-level synthesis. Our proposed technique pursues the optimality of the native objective functions of the register binding problem. At the same time, it ensures not invalidating the subsequent clock skew scheduling for optimizing the clock period. We use the switching power as the native objective of our register binding problem. The problem is first formulated as a MILP problem. An acceleration scheme based on the concept of weakly compatible edge set(WCES) is proposed to speed up the MILP solver to obtain the optimal solution. Then, we present our heuristic algorithm to reduce the running time further. The experimental results show that on average our acceleration scheme can speed up the solver by 8.6 times, and our heuristic is 70 times faster than the solver with a 5.25% degradation of the native objective. The minimum and maximum degradation among our benchmark set are 0.82% and 12.2% respectively.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 3: Deming Chen , Jason Cong, Register binding and port assignment for multiplexer optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: R. B. Deokar and S. S. Sapatnekar. A graph-theoretic approach to clock skew optimization. In ISCAS, 1994.
• 6: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 7: Express Group@UCSB. http://express.ece.ucsb.edu/benchamrk.
• 8: Shih-Hsu Huang , Chun-Hua Cheng , Yow-Tyng Nieh , Wei-Chieh Yu, Register binding for clock period minimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147026]
• 9: I-Min Liu , Tan-Li Chou , Adnan Aziz , D. F. Wong, Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion, Proceedings of the 2000 international symposium on Physical design, p.33-38, May 2000, San Diego, California, United States [doi>10.1145/332357.332370]
• 10: Kaushik Ravindran , Andreas Kuehlmann , Ellen Sentovich, Multi-Domain Clock Skew Scheduling, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.801, November 09-13, 2003 [doi>10.1109/ICCAD.2003.100]
• 11: Q. Zhao , C. A. J. van Eijk , C. A. Alba Pinto , J. A. G. Jess, Register Binding for Predicated Execution in DSP Applications, Proceedings of the 13th symposium on Integrated circuits and systems design, p.113, September 18-24, 2000