Automatic bus planner for dense PCBs

ABSTRACT

Since no commercial PCB routing tools can solve the routing problem for today's complex PCBs, these circuit boards have to be routed manually, taking about 2 months of time per board. Bus planning is one of the most time-consuming steps of PCB routing. It consists of assigning buses to multiple layers of the PCB and routing them in a planar fashion on each layer. Routing congestion between on-board components and the min-max length bounds of the buses must also be considered during routing. In this paper, we present the first automatic bus planner. We tested our system on a state-of-the-art industrial circuit board with over 7000 nets and 12 signal layers. All the nets on this board were already manually routed. Our bus planner is able to achieve 100% routing completion using the layer assignment extracted from manual design. For simultaneous layer assignment and bus routing, we are able to successfully route 98.5% of the nets. The remaining 1.5% can be routed either manually or by using vias. The runtime of our bus planner is less than 3 hours on a 3 Ghz workstation.

REFERENCES

• 1: V. Betz and J. Rose. VPR: A new packing, placement and routing tool for FPGA research. In FPL '97: Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, pages 213--222, 1997.
• 2: Cadence Allegro PCB Design. (http://www.cadence.com/products/pcb/pcb_design).
• 3: Cadence OrCAD PCB Designer. (http://www.cadence.com/products/pcb/pcb_designer).
• 4: M. Cho, K. Lu, K. Yuan, and D. Z. Pan. BoxRouter 2.0: architecture and implementation of a hybrid and robust global router. In ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, pages 503--508, 2007.
• 5: J. E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: a survey. pages 46--93, 1997.
• 6: C. Ebeling, L. McMurchie, S. A. Hauck, and S. Burns. Placement and routing tools for the Triptych FPGA. IEEE Trans. Very Large Scale Integr. Syst., 3(4):473--482, 1995.
• 7: M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1990.
• 8: L. McMurchie and C. Ebeling. PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs. In Field-Programmable Gate Arrays, 1995. FPGA '95. Proceedings of the Third International ACM Symposium on, pages 111--117, 1995.
• 9: Mentor Graphics Topology Router. http://www.mentor.com/products/pcb-system-design/layout-routing/topology-router.
• 10: M. M. Ozdal. Routing algorithms for high-performance VLSI packaging. PhD thesis, University of Illinois at Urbana-Champaign, 2005.
• 11: M. M. Ozdal and M. D. F. Wong. Archer: a history-driven global routing algorithm. In ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, pages 488--495, 2007.
• 12: M. Pan and C. Chu. FastRoute 2.0: A High-quality and Efficient Global Router. In ASP-DAC '07: Proceedings of the 2007 conference on Asia South Pacific design automation, pages 250--255, 2007.
• 13: L. Ritchey. Busses: What are they and how do they work. In Printed Circuit Design Magazine, 2000.
• 14: J. C. Whitaker. The Electronics Handbook (2nd Edition). CRC Press, 2005.
• 15: D. Wiens. Printed circuit board routing at the threshold. White Paper, Mentor Graphics, 2000.
• 16: D. F. Wong, H. W. Leong, and C. L. Liu. Simulated Annealing for VLSI design. Kluwer Academic Publishers, 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Performance

Keywords:
PCB routing, bus planning, layer assignment, topological routing