Theories and algorithms on single-detour routing for untangling twisted bus

ABSTRACT

Previous works on PCB bus routing assume matched pin ordering on both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this article, we propose a preprocessing step to untangle such twisted nets. We also introduce a practical routing style, which we call single-detour routing, to simplify the untangling problem. We then present a necessary and sufficient condition for the existence of single-detour routing solutions. Furthermore, we present a dynamic-programming-based algorithm to solve the single-detour untangling problem with consideration of wire capacity between adjacent pins. Our algorithm produces an optimal single-detour routing solution that rematches the pin ordering. By integrating our algorithm into the bus router in a previous length-matching router, we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

REFERENCES

• 1: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 2: Hui Kong , Tan Yan , Martin D. F. Wong , Muhammet Mustafa Ozdal, Optimal bus sequencing for escape routing in dense PCBs, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 3: 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]
• 4: Ozdal, M. M. and Wong, M. D. F. 2006a. Algorithmic study of single-layer bus routing for high-speed boards. IEEE Trans. Comput.-Aided Des. 25, 3, 490--503.
• 5: Ozdal, M. M. and Wong, M. D. F. 2006b. Algorithms for simultaneous escape routing and layer assignment of dense PCBs. IEEE Trans. Comput.-Aided Des. 25, 8, 1510--1522.
• 6: Ozdal, M. M. and Wong, M. D. F. 2006c. A length-matching routing algorithm for high-performance printed circuit boards. IEEE Trans. Comput.-Aided Des. 25, 12, 2784--2794.
• 7: Ritchey, L. W. 2000. Busses: What are they and how do they work? Printed Circ. Des. Mag.
• 8: Ritchey, L. W. and Zasio, J. 2003. Right the First Time, A Practical Handbook on High Speed PCB and System Design. Speeding Edge.
• 9: Steven S. Skiena, The algorithm design manual, Springer-Verlag New York, Inc., New York, NY, 1997
• 10: Tummala, R. R., Rymaszewski, E. J., and Klopfenstein, A. G. 1997. Microelectronics Packaging Handbook, Part II: Semiconductor Packaging. Kluwer Academic.
• 11: Wiens, D. 2000. Printed circuit board routing at the threshold. White paper. Mentor Graphics.
• 12: 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

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
Bus routing, dynamic programming, printed circuit board (PCB), single-detour routing, twisted bus