An enhanced multilevel routing system

ABSTRACT

In this paper, we present several novel techniques that make the recently published multilevel routing scheme [19] more effective and complete. Our contributions include: (1) resource reservation for local nets during the coarsening process, (2) congestion-driven, graph-based Steiner tree construction during the initial routing and the refinement process and (3) multi-iteration refinement considering the congestion history. The experiments show that each of these techniques helps to improve the completion rate considerately. Compared to [19], the new routing system reduces the number of failed nets by 2× to 18×, with less than 50% increase in runtime in most cases.

REFERENCES

• 1: S. Akers, "A modification of Lee's path connection algorithm," IEEE Trans. on Computers, vol. EC-16, pp. 97--98, Feb. 1967.
• 2: 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
• 3: K. Mikami and K. Tabuchi, "A computer program for optimal routing of printed circuit connectors," IFIPs Proc, vol. H-47, pp. 1475--1478, 1968.
• 4: 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]
• 5: R. Nair., "A simple yet effective technique for global wiring," IEEE Trans. on Computer-Aided Design, CAD-6(2), 1987.
• 6: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 7: R. Carden, J. Li, and C.-K.Cheng, "A global router with a theoretical bound on the optimal solution," IEEE Trans. Computer-Aided Design, vol. 15, pp. 208--216, Feb. 1996
• 8: Christoph Albrecht, Provably good global routing by a new approximation algorithm for multicommodity flow, Proceedings of the 2000 international symposium on Physical design, p.19-25, May 2000, San Diego, California, United States [doi>10.1145/332357.332368]
• 9: Jason Cong , Patrick H. Madden, Performance driven multi-layer general area routing for PCB/MCM designs, Proceedings of the 35th annual conference on Design automation, p.356-361, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277144]
• 10: 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]
• 11: C. Chang and J. Cong, "Pseudo pin assignment with crosstalk noise control," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, pp. 598--611, Mar. 2001.
• 12: 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]
• 13: Michael Burstein , Richard Pelavin, Hierarchical channel router, Proceedings of the 20th conference on Design automation, p.591-597, June 27-29, 1983, Miami Beach, Florida, United States
• 14: J. Heisterman and T. Lengauer, "The efficient solution of integer programs for hierarchical global routing," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, pp. 748--753, Jun. 1991.
• 15: 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
• 16: 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]
• 17: 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]
• 18: 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
• 19: 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
• 20: C. Chiang, M. Sarrafzadeh, and C.K, Wong, "A powerful global router: Based on Steiner min-max trees," Proc. IEEE International Conference on Computer-Aided Design, pp. 2--5, Nov. 1989.
• 21: C. Chiang, M. Sarrafzadeh, and C.K., Wong, "A weighted-Steiner-tree-based global router," Manuscript, 1992.
• 22: J. Cong, A. B. Kahng and K.-S. Leung, "Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 1, pp. 24--39, Jan. 1999
• 23: Jason Cong , Jie Fang , Kei-Yong Khoo, An implicit connection graph maze routing algorithm for ECO routing, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.163-167, November 07-11, 1999, San Jose, California, United States
• 24: M. Borah, R. M. Owens, M. J., Irwin, "An edge-based heuristic for Steiner routing," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, (no. 12), Dec. 1994. p. 1563--8
• 25: J. Griffith, G. Robins, J. S. Salowe, Tongtong Zhang, "Closing the gap: near-optimal Steiner trees in polynomial time," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, (no. 11), Nov. 1994. p. 1351--65

INDEX TERMS

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

Additional Classification:
  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.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Experimentation, Performance, Theory