UST/DME: a clock tree router for general skew constraints

ABSTRACT

In this article, we propose new approaches for solving the useful-skew tree (UST) routing problem [Xi and Dai 1997]: clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for the zero-skew tree (ZST) [Edahiro 1992; Chao et al. 1992] and bounded-skew tree (BST) [Cong and Koh 1995; Huang et al. 1995; Kahng and Tsao 1997; Cong et al. 1998] routings; hence, the names UST/DME and Greedy-UST/DME for our UST algorithms. Our novel contribution is that we simultaneously perform skew scheduling and tree routing so that each local skew range is incrementally refined to a skew value that minimizes the wirelength increase during the bottom-up merging phase of DME. As a result, not only is the skew schedule feasible, but also the wirelength increase is minimized at each merging step of clock tree construction. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total routing wirelength.

REFERENCES

• 1: Chao, T.-H., Hsu, Y.-C. H., Ho, J.-M., Boese, K. D., and Kahng, A. B. 1992. Zero skew clock routing with minimum wirelength. IEEE Trans. Circ. Syst. 39, 11 (Nov.), 799--814.
• 2: Cong, J. and Koh, C.-K. 1995. Minimum-cost bounded-skew clock routing. In Proceedings of the IEEE International Symposium on Circuits and Systems (April), 1.215--1.218.
• 3: 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]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Deokar, R. B. and Sapatnekar, S. S. 1994. A graph-theoretic approach to clock skew optimization. In Proceedings of the IEEE International Symposium on Circuits and Systems, 407--410.
• 6: Edahiro, M. 1992. Minimum path-length equi-distant routing. In Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems (December), 41--46.
• 7: 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]
• 8: Masato Edahiro, An efficient zero-skew routing algorithm, Proceedings of the 31st annual conference on Design automation, p.375-380, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196426]
• 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: 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]
• 11: Kahng, A. B. and Tsao, C.-W. A. 1996. Planar-DME: A single-layer zero-skew clock tree router. IEEE Trans. Comput. Aid. Des. Integ. Circ. Syst. 15, 1 (Jan.), 8--19.
• 12: Andrew B. Kahng , C.-W. Albert Tsao, Practical Bounded-Skew Clock Routing, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.199-215, June/July 1997 [doi>10.1023/A:1007995125716]
• 13: Liao, Y.-Z. and Wong, C. K. 1983. An algorithm to compact a VLSI symbolic layout with mixed constraints. IEEE Trans. Comput. Aid. Des. Integ. Circ. Syst. 2, 2 (Feb.), 62--69.
• 14: José Luis Neves , Eby G. Friedman, Optimal clock skew scheduling tolerant to process variations, Proceedings of the 33rd annual conference on Design automation, p.623-628, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240636]
• 15: Sakallah, K. A., Mudge, T. N., and Olukotun, O. A. 1990. checkTc and minTc: Timing verification and optimal clocking of synchronous digital circuits. In Proceedings of the International Conference on Computer Aided Design, 552--555.
• 16: Sapatnekar, S. S. and Deokar, R. B. 1996. Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE Trans. Comput. Aid. Des. Integ. Circ. Syst. 15, 10 (Oct.), 1237--1248.
• 17: Sapatnekar, S. S. and Lehther, D. 1998. Moment-based techniques for rlc clock tree construction. IEEE Trans. Circ. Syst. II: Analog Digital Sig. Process. 45, 1 (Jan.), 69--79.
• 18: Sapatnekar, S. S. and Maheshwari, M. 1998. Efficient retiming of large circuits. IEEE Trans. VLSI Syst. 6, 1, 74--83.
• 19: 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
• 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: 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
• 22: Tsay, R.-S. 1993. An exact zero-skew clock routing algorithm. IEEE Trans. Comput. Aid. Des. Integ. Circ. Syst. CAD-12, 2 (Feb.), 242--249.
• 23: Ashok Vittal , Hein Ha , Forrest Brewer , Malgorzata Marek-Sadowska, Clock skew optimization for ground bounce control, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.395-399, November 10-14, 1996, San Jose, California, United States
• 24: P. Vuillod , L. Benini , A. Bogliolo , G. De Micheli, Clock skew optimization for peak current reduction, Proceedings of the 1996 international symposium on Low power electronics and design, p.265-270, August 12-14, 1996, Monterey, California, United States
• 25: 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
• 26: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Useful Skew, clock tree, feasible skew range, incremental skew scheduling, merging and embedding, merging region