Clock Scheduling and Clocktree Construction for High Performance ASICS

ABSTRACT

In this paper we present a new method for clock schedulingand clocktree construction that improves the performance ofhigh-end ASICs significantly.First, we compute a clock schedule that yields the optimumcycle time and the best possible clock distribution with respectto early and late mode; in particular the number of criticaltests is minimized. Second, individual arrival time intervalsare computed for all endpoints of the clocktree. Finally, weconstruct a clocktree that realizes arrival times within theseintervals and exploits positive slacks to save power consumption.We demonstrate the superiority of our method to previousapproaches by experimental results on industrial ASICs withup to 194 000 registers and more than 160 clock domains. Weimproved the clock frequencies by 5-28% up to 1.033 GHz (in hardware).

REFERENCES

• 1: C. Albrecht , B. Korte , J. Schietke , J. Vygen, Cycle time and slack optimization for VLSI-chips, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.232-238, November 07-11, 1999, San Jose, California, United States
• 2: David Blaauw , Vladimir Zolotov , Savithri Sundareswaran , Chanhee Oh , Rajendran Panda, Slope propagation in static timing analysis, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 3: T.-H. Chao , J.-M. Ho , Y.-C. Hsu, Zero skew clock net routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.518-523, June 08-12, 1992, Anaheim, California, United States
• 4: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 5: Jason Cong , Andrew B. Kahng , Cheng-Kok Koh , C.-W. Albert Tsao, Bounded-skew clock and Steiner routing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.341-388, July 1998 [doi>10.1145/293625.293628]
• 6: [6] R. B. Deokar and S. S. Sapatnekar. A graph-theoretic approach to clock skew optimization. Proc. of the IEEE Int. Symp. on Circuits and Systems, 407-410, 1995.
• 7: [7] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269-271, 1959.
• 8: [8] M. Edahiro. Minimum skew and minimum path length routing in vlsi layout design. NEC Research and Development, 32(4), 569-575, 1991.
• 9: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 10: [10] S. Held. Algorithmen für Potential-Balancierungs-Probleme und Anwendungen im VLSI-Design. Diploma thesis. University of Bonn, 2001.
• 11: [11] R. B. Hitchcock, G. L. Smith, and D. D. Cheng. Timing analysis of computer hardware. IBM Journal of Research and Development 26, 100-105, 1982.
• 12: [12] I. S. Kourtev and E. G. Friedman. Simultaneous clock scheduling and buffered clock tree synthesis. Proc. of the IEEE Int. Symp. on Circuits and Systems, 1812-1815, 1997.
• 13: [13] I. S. Kourtev and E. G. Friedman. A quadratic programming approach to clock skew scheduling for reduced sensitivity to process parameter variations. Proc. of the IEEE International ASIC/SOC Conference, 210-215, 1999.
• 14: Ivan S. Kourtev , Eby G. Friedman, Timing optimization through clock skew scheduling, Kluwer Academic Publishers, Norwell, MA, 2000
• 15: M. Saitoh , M. Azuma , A. Takahashi, Clustering based fast clock scheduling for light clock-tree, Proceedings of the conference on Design, automation and test in Europe, p.240-245, March 2001, Munich, Germany
• 16: [16] K. A. Sakallah, T. N. Mudge, and O. A. Olukotun. checktc and mintc: Timing verification and optimal clocking of digital circuits. Proc. ICCAD, 552-555, 1990.
• 17: Narendra Shenoy , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Graph algorithms for clock schedule optimization, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.132-136, November 1992, Santa Clara, California, United States
• 18: T. G. Szymanski, Computing optimal clock schedules, Proceedings of the 29th ACM/IEEE conference on Design automation, p.399-404, June 08-12, 1992, Anaheim, California, United States
• 19: Chung-Wen Albert Tsao , Cheng-Kok Koh, UST/DME: a clock tree router for general skew constraints, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 20: [20] R.-S. Tsay. An exact zero-skew clock routing algorithm. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 12, 242-249, 1993.
• 21: [21] J. Vygen. Theory of VLSI Layout. Habilitation thesis. University of Bonn, 2001.
• 22: Joe Gufeng Xi , Wayne Wei-Ming Dai, Useful-Skew Clock Routing with Gate Sizing for Low Power Design, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.163-179, June/July 1997 [doi>10.1023/A:1007939023899]
• 23: [23] N. E. Young, R. E. Tarjan, and J. B. Orlin. Faster parametric shortest path and minimum-balance algorithms. Networks, 21, 205-221, 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles

          Nouns: ASIC

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Asynchronous/synchronous operation
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

General Terms:
Algorithms, Design, Performance