Performance driven multi-layer general area routing for PCB/MCM designs

ABSTRACT

In this paper we present a new global router appropriate for Multichip Module (MCM) and dense Printed Circuit Board (PCB) design, which utilizes a hybrid of the classical rip-up and reroute approach, and the more recent iterative deletion [9] method. The global router addresses performance issues by utilizing recent results in high performance interconnect design, while still effectively minimizing global congestion. With experimen ts on the maze-routing component of our global router, we show that the choice of routing cost functions can have a significant impact on final solution quality. The results of a number of previously proposed routers may be improved dramatically by adopting the cost functions we suggest here. W e also find little evidence of the “net ordering problem” when our cost functions and routing model are applied. The iterative deletion method is shown to improve global solution quality, particularly when high performance interconnect is required. We evaluate the performance of our global router by comparing the congestion of routes produced by our global router to those of a well known MCM router, V4R [14]. Our global router, MINOTAUR, supports arbitrary numbers of routing layers, differing capacities for each layer, pre-existing congestion and obstacles, and high performance interconnect structures (including those which require variable width interconnect).

REFERENCES

• 1: H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley, 1990.
• 2: J. D. Carothers , Donghui Li , T. Hameenanttila, MCG: a correct-by-design multichip module router with crosstalk avoidance, Proceedings of the 7th IEEE International Workshop on Rapid System Prototyping (RSP '96), p.183, June 19-21, 1996
• 3: Young-Jun Cha , Chong S. Rim , Kazuo Nakajima, A simple and effective greedy multilayer router for MCMs, Proceedings of the 1997 international symposium on Physical design, p.67-72, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267686]
• 4: J. D. Cho, K.-F. Liao, S. Raje, and M. Sarrafzadeh. M2R~ Multilayer routing algorithm for high-performance MCMs. IEEE Trans. on Circuits and Systems, 41(4):253-265, April 1994.
• 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 , Cheng-Kok Koh, Interconnect layout optimization under higher-order RLC model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.713-720, November 09-13, 1997, San Jose, California, United States
• 7: 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]
• 8: J. Cong and P. H. Madden. Performance driven multi-layer general area routing for pcb/mcm designs,. Technical Report 980013, UCLA C$ Dept, March 1998.
• 9: J. Cong and B. Preas. A new algorithm for standard cell global routing. In Proc. Int. Conf. on Computer Aided Design, pages 176-179, November 1988.
• 10: A. Hanafusa, Y. Yamashita, and M. Yasuda. Three-dimensional routing for multilayer ceramic printed circuit boards. In Proc. Int. Conf. on Computer Aided Design, pages 386-389, 1990.
• 11: A. B. Kahng and G. Robins. On Optimal Interconnections for VLSL Kluwer Academic Publishers, 1994.
• 12: K. Kawamura, T. Shindo, T. Shibuya, H. Miwatari, and Y. Ohki. Touch and cross router. In Proc. Int. Conf. on Computer Aided Design, pages 56-59, 1990.
• 13: K.-Y. Khoo and J. Cong. A fast multilayer general area router for MCM designs. IEEE Trans. on Circuits and Systems, pages 841-851, 1992.
• 14: K.-Y. Khoo and J. Cong. An efficient multilayer MCM router based on four-via routing. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pages 1277-1290, 1994.
• 15: C. Y. Lee. An algorithm for path connection and its applications. IRE Trans. on Electronic Computers, EC-10(3):346-365, 1961.
• 16: Ralph Linsker, An iterative-improvement penalty-function-driven wire routing system, IBM Journal of Research and Development, v.28 n.5, p.613-624, September 1984
• 17: Sharad Mehrotra , Paul Franzon , Michael Steer, Performance driven global routing and wiring rule generation for high speed PCBs and MCMs, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.381-387, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217559]
• 18: H. Shin and A. Sangiovanni-Vincentelli. A detailed router based on incremental routing modifications: Mighty. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, CAD-6(6):942-955, November 1987.
• 19: E. Shragowitz , S. Keel, A global router based on a multicommodity flow model, Integration, the VLSI Journal, v.5 n.1, p.3-16, March 1987 [doi>10.1016/S0167-9260(87)80003-2]
• 20: 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
• 21: Qiong Yu , Sandeep Badida , Naveed Sherwani, Algorithmic aspects of three dimensional MCM routing, Proceedings of the 31st annual conference on Design automation, p.397-401, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196434]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

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

  C. Computer Systems Organization

  J. Computer Applications

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

Keywords:
fanout optimization, gate-sizing, logic synthesis