BSG-Route: a length-matching router for general topology

ABSTRACT

Length-matching routing is a very important issue for PCB routing. Previous length-matching routers [1]--[3] all have assumptions on the routing topology whereas practical designs may be free of any topological constraint. In this paper, we propose a router that deals with general topology. Unlike previous routers, our router does not impose any restriction on the routing topology. Moreover, our router is gridless. Its performance does not depend on the routing grid size of the input while routers in [1]--[3] do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-matching routing problem as an area assignment problem and use a placement structure, Bounded-Sliceline Grid (BSG) [4], to help solving the problem. Experimental results show that our router can handle practical designs that previous routers can't handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 seconds while the router in [3] takes more than one day.

REFERENCES

• 1: M. M. Ozdal and M. D. F. Wong, "Algorithmic study of single-layer bus routing for high-speed boards," IEEE Trans. Computer-Aided Design, vol. 25, no. 3, pp. 490--503, Mar. 2006.
• 2: Yukiko Kubo , Hiroshi Miyashita , Yoji Kajitani , Kazuyuki Tateishi, Equidistance routing in high-speed VLSI layout design, Integration, the VLSI Journal, v.38 n.3, p.439-449, January 2005 [doi>10.1016/j.vlsi.2004.07.008]
• 3: M. M. Ozdal and M. D. F. Wong, "A length-matching routing algorithm for high-performance printed circuit boards," IEEE Trans. Computer-Aided Design, vol. 25, no. 12, Dec. 2006.
• 4: S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, "Module packing based on the BSG-structure and IC layout applications," IEEE Trans. Computer-Aided Design, vol. 17, no. 6, June 1998.
• 5: D. Wiens, "Printed circuit board routing at the threshold," in White Paper. Mentor Graphics, 2000. {Online}. Available: http://www.mentor.com/products/pcb/expedition/techpubs/mentorpaper_626
• 6: L. W. Ritchey and J. Zasio, Right the First Time, A Practical Handbook on High Speed PCB and System Design, K. J. Knack, Ed. Speeding Edge, 2003.
• 7: L. W. Ritchey, "Busses: What are they and how do they work?" in Printed Circuit Design Magazine, Dec. 2000. {Online}. Available: http://www.speedingedge.com/PDF-Files/busses.pdf
• 8: Tan Yan , Martin D. F. Wong, Untangling twisted nets for bus routing, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 9: lp_solve: an open source linear programming solver. {Online}. Available: http://sourceforge.net/projects/lpsolve