Simultaneous escape routing and layer assignment for dense PCBs

ABSTRACT

As die sizes are shrinking, and circuit complexities are increasing, the PCB routing problem becomes more and more challenging. Traditional routing algorithms can not handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. In this paper, we propose a problem decomposition that distinguishes routing within dense components from routing in the intermediate area. In particular, we propose an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, we model the problem as a longest path with forbidden pairs (LPFP) problem, and propose two algorithms for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then we use these algorithms to assign the maximal subset of planar nets to each layer, and then distribute the remaining nets at the end. We demonstrate the effectiveness of these algorithms through experiments on industrial circuits.

REFERENCES

• 1: Piotr Berman , Georg Schnitger, On the complexity of approximating the independent set problem, Information and Computation, v.96 n.1, p.77-94, Jan. 1992 [doi>10.1016/0890-5401(92)90056-L]
• 2: [2] H. N. Brady. An approach to topological pin assignment. IEEE Trans. on Computer Aided Design, 3: 250-255, 1984.
• 3: [3] J. Cong and C. L. Liu. On the k-layer planar subset and topological via minimization problems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 10, 1991.
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: [5] P. Crescenzi and V. Kann. A compendium of np optimization problems, http://www.nada.kth.se/viggo/problemlist.
• 6: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 7: Norman L. Koren, Pin assignment in automated printed circuit board design, Proceedings of the 9th workshop on Design automation, p.72-79, June 26-28, 1972 [doi>10.1145/800153.804932]
• 8: [8] J. Ludwig. IBM Systems Group, Private communication, 2004.
• 9: Muhammet Mustafa Ozdal , Martin D. F. Wong, Length-Matching Routing for High-Speed Printed Circuit Boards, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.394, November 09-13, 2003 [doi>10.1109/ICCAD.2003.92]
• 10: [10] B. Voss. The package routing challenge. StilwellBaker, Inc., June, 2003.
• 11: [11] D. Wiens. Printed circuit board routing at the threshold. White Paper, Mentor Graphics, 2000.
• 12: Hua Xiang , Xiaoping Tang , D. F. Wong, An algorithm for simultaneous pin assignment and routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California