Clock-tree routing realizing a clock-schedule for semi-synchronous circuits

ABSTRACT

It is known that the clock-period can be shorter than the maximum of signal-delays between registers if the clock arrival time to each register is properly scheduled. The algorithm to design an optimal clock-schedule was given. In this paper, we propose a clock-tree routing algorithm that realizes a given clock-schedule using the Elmore-delay model. Following the deferred-merge-embedding (DME) framework, the algorithm generates a topology of the clock-tree and determines the locations and sizes of intermediate buffers simultaneously. The experimental results show that this method constructs clock-trees with moderate wire length compared with that of zero-skew clock-trees.

REFERENCES

• 1: K. D. Boese and A. B. Kahng, "Zero-skew clock routing trees with minimum wirelength," in Proc. IEEE 5th ASIC Conj., pp. 1.1.1-1.1.5, 1992.
• 2: 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
• 3: T. H. Chao, Y. C. Hsu, J. M. Ho, K. D. Boese, and A. B. Kahgn, "Zero skew clock routing with minimum wirelength," IEEE Trans. on Circuits and Systems, vol. 39, no. 11, pp. 799-814, 1992.
• 4: Y. P. Chen , D. F. Wong, An Algorithm for Zero-Skew Clock Tree Routing with Buffer Insertion, Proceedings of the 1996 European conference on Design and Test, p.230, March 11-14, 1996
• 5: 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]
• 6: Jason Cong , Andrew B. Kahng , Cheng-Kok Koh , C.-W. Albert Tsao, Bounded-skew clock and Steiner routing under Elmore delay, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.66-71, November 05-09, 1995, San Jose, California, United States
• 7: J. Cong and C. K. Koh, "Minimum-cost bounded-skew clock routing," in Proc. ISCAS 95, vol. 1, pp. 215-218, 1995.
• 8: R. B. Deokar and S. S. Sapatnel~r, "A graph-theoretic approach to clock skew optimization," in Proc. ISCAS '9~, vol. 1, pp. 407-410, 1994.
• 9: M. Edahiro, "Minimum skew and minimum path length routing," NEC Research ~ Development, vol. 32, no. 4, pp. 569-575, 1991.
• 10: Masato Edahiro, A clustering-based optimization algorithm in zero-skew routings, Proceedings of the 30th international conference on Design automation, p.612-616, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165066]
• 11: M. Edahiro and T. Yoshimura, "Minimum path-length equidistant routing," in Proc. APCCAS 92, pp. 41-46, 1992.
• 12: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 13: E. G. Friedman, ed., Clock Distribution Networks in VLSI Circuits and Systems: A Selected Reprint Volume. IEEE Press, 1995.
• 14: Dennis J. H. Huang , Andrew B. Kahng , Chung-Wen Albert Tsao, On the bounded-skew clock and Steiner routing problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.508-513, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217579]
• 15: Donald A. Joy , Maciej J. Ciesielski, Placement for clock period minimization with multiple wave propagation, Proceedings of the 28th conference on ACM/IEEE design automation, p.640-643, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127742]
• 16: J. L. Neves and E. G. Friedman, "Topological design of clock distribution networks based on non-zero clock skew specifications," in Pro~c. 36th Midwest Syrup. on Circuits and Systems, pp. 468-471, 1993.
• 17: J. L. Neves and E. G. Friedman, "Circuit synthesis of clock distribution networks based on non-zero clock skew," in Proc. ISCAS '9~, vol. 4, pp. 175-178, 1994.
• 18: J. L. Neves and E. G. Friedman, "Minimizing power dissipation in non-zero skew-based clock distribution networks," in Proc. ISCAS '95, vol. 3, pp. 1577-1579, 1995.
• 19: Karem A. Sakallah , Trevor N. Mudge , Oyekunle A. Olukotun, Analysis and design of latch-controlled synchronous digital circuits, Proceedings of the 27th ACM/IEEE conference on Design automation, p.111-117, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123237]
• 20: 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
• 21: A. Takahashi and Y. Kajitani, "Performance and reliability driven clock scheduling of sequential logic circuits," in Proc. ASP-DA C '97, pp. 37-42, 1997.
• 22: R. S. Tsay, "Exact zero skew," in Proc. 1991 ICCAD, pp. 336-339, 1991.
• 23: Ashok Vittal , Malgorzata Marek-Sadowska, Power optimal buffered clock tree design, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.497-502, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217577]
• 24: Joe G. Xi , Wayne W.-M. Dai, Jitter-tolerant clock routing in two-phase synchronous systems, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.316-320, November 10-14, 1996, San Jose, California, United States
• 25: Joe G. Xi , Wayne W.-M. Dai, Useful-skew clock routing with gate sizing for low power design, Proceedings of the 33rd annual conference on Design automation, p.383-388, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240592]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware
      B.7.2 Design Aids
          Subjects: Placement and routing

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
clock-tree routing, clock-schedule, synchronous, semi-synchronous, deferred-merge-embedding (DME), buffer insertion, buffer sizing