A novel framework for multilevel routing considering routability and performance

ABSTRACT

We propose in this paper a novel framework for multilevel routing considering both routability and performance. The two-stage multilevel framework consists of coarsening followed by uncoarsening. Unlike the previous multilevel routing, we integrate global routing, detailed routing, and resource estimation together at each level of the framework, leading to more accurate routing resource estimation during coarsening and thus facilitating the solution refinement during uncoarsening. Further, the exact routing information obtained at each level makes our framework more flexible in dealing with various routing objectives (such as crosstalk, power, etc). Experimental results show that our approach obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100% routing completion for all circuits while the previous multilevel routing, the three-level routing, and the hierarchical routing can complete routing for only 3, 0, 3 circuits, respectively. In particular, the number of routing layers used by our router is even smaller. We also have performed experiments on timing-driven routing. The results are also very promising.

REFERENCES

• 1: C. Albrecht, "Global routing by new approximation algorithms for multicommodity flow," Trans. on Computer-Aided Design, vol. 20, no. 5, pp. 622--632, May 2001.
• 2: C. J. Alpert, J.-H. Huang, and A. B. Kahng, "Multilevel circuit partitioning," IEEE Trans. on Computer-Aided Design, vol. 17, no. 8, pp. 655--667, August 1998.
• 3: Yao-Wen Chang , Kai Zhu , D. F. Wong, Timing-driven routing for symmetrical array-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.433-450, July 2000 [doi>10.1145/348019.348101]
• 4: Tony F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 5: Jason Cong , Jie Fang , Yan Zhang, Multilevel approach to full-chip gridless routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 6: Jason Cong , Jie Fang , Kei-Yong Khoo, DUNE: a multi-layer gridless routing system with wire planning, Proceedings of the 2000 international symposium on Physical design, p.12-18, May 2000, San Diego, California, United States [doi>10.1145/332357.332367]
• 7: J. Cong, A. Kahng, and K. Leung, "Efficient algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design," Trans. on Computer-Aided DEsign, vol 17, pp. 24--39, 1998.
• 8: Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337418]
• 9: Jason Cong , Patrick H. Madden, Performance driven global routing for standard cell design, Proceedings of the 1997 international symposium on Physical design, p.73-80, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267689]
• 10: J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, "Provably good performancedriven global routing," Trans. Computer-Aided Design, vol 11, no 6, pp. 739--752, June 1992.
• 11: Takahiro Deguchi , Tetsushi Koide , Shin'ichi Wakabayashi, Timing-driven hierarchical global routing with wire-sizing and buffer-insertion for VLSI with multi-routing-layer, Proceedings of the 2000 conference on Asia South Pacific design automation, p.99-104, January 2000, Yokohama, Japan [doi>10.1145/368434.368586]
• 12: J. Heisterman and T. lengauer, "The efficient solutions of integer programs for hierarchical global routing," Trans. on Computer-Aided Design, vol. 10, no. 6, pp. 748--753, June 1991.
• 13: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 14: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.69-79, March 1999 [doi>10.1109/92.748202 ]
• 15: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Predictable routing, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 16: Lee, "An algorithm for path connection and its application," IRE Trans. Electronic Computer, EC-10, 1961.
• 17: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
• 18: S.-C. Lee, J.-M. Hsu, and Y.-W. Chang, "Multilevel large-scale module placement/floorplanning using B*-trees," Proc. The 12th VLSI Design/CAD Symposium, Hsinchu, Taiwan, Aug. 2001.
• 19: M. Marek-Sadowska, "Router planner for custom chip design," Proc. ICCAD, Nov. 1986.
• 20: G. Meixner and U. Lauther, "A new global router based on a flow model and linear assignment," Proc. ICCAD, pp. 44--47, Nov. 1990.
• 21: J. Soukup, Fast maze router, Proceedings of the 15th conference on Design automation, p.100-102, June 19-21, 1978, Las Vegas, Nevada, United States
• 22: Dongsheng Wang , Ernest S. Kuh, A New Timing-Driven Multilayer MCM/IC Routing Algorithm, Proceedings of the 1997 Conference on IEEE Multi-Chip Module Conference, p.89, February 04-05, 1997

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

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

General Terms:
Experimentation, Performance, Theory