Length-Matching Routing for High-Speed Printed Circuit Boards

ABSTRACT

As the clock frequencies used in industrial applications increase,the timing requirements imposed on routing problems becometighter. So, it becomes important to route the nets within tight minimumand maximum length bounds. Although the problem of routingnets to satisfy maximum length constraints is a well-studiedproblem, there exists no sophisticated algorithm in the literaturethat ensures that minimum length constraints are also satisfied. Inthis paper, we propose a novel algorithm that effectively incorporatesthe min-max length constraints into the routing problem. Ourapproach is to use a Lagrangian relaxation framework to allocateextra routing resources around nets simultaneously during routingthem. We also propose a graph model that ensures that all theallocated routing resources can be used effectively for extendinglengths. Our routing algorithm automatically prioritizes resourceallocation for shorter nets, and length minimization for longer netsso that all nets can satisfy their min-max length constraints. Ourexperiments demonstrate that this algorithm is effective even in thecases where length constraints are tight, and the layout is dense.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, Directional bias and non-uniformity in FPGA global routing architectures, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.652-659, November 10-14, 1996, San Jose, California, United States
• 2: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 3: [3] K. D. Boese, J. Cong, A. B. Kahng, K. S. Leung, and D. Zhou. On highspeed VLSI interconnects: Analysis and design. In Proc. Asia-Pacific Conf. Circuits Syst., pages 35- 40, 1992.
• 4: [4] J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong. Provably good performance-driven global routing. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 11(6):739-752, 1992.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• 7: 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]
• 8: [8] M. L. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1-18, 1981.
• 9: [9] M. L. Fisher. An applications oriented guide to Lagrangian relaxation. Interfaces, 15(2):10-21, 1985.
• 10: [10] A. M. Geoffrion. Lagrangian relaxation and its uses in integer programming. Mathematical Programming, 2:82-114, 1974.
• 11: [11] X. Guan, P. B. Luh, and L. Zhang. Nonlinear approximation method in Lagrangian relaxation-based algorithms for hydrothermal scheduling. IEEE Transactions on Power Systems , 10(2):772-778, 1995.
• 12: X. H. Guan , Q. Z. Zhai , F. Lai, New Lagrangian relaxation based algorithm for resource scheduling with homogeneous subproblems, Journal of Optimization Theory and Applications, v.113 n.1, p.65-82, April 2002 [doi>10.1023/A:1014805213554]
• 13: [13] M. H. Held, P. Wolfe, and H. D. Crowder. Validation of subgradient optimization. Mathematical Programming, 6(1):62-88, 1974.
• 14: [14] E. Kuh, M. A. B. Jackson, and M. Marek-Sadowska. Timing-driven routing for building block layout. In Proc. IEEE Intl. Symposium on Circuits and Systems, pages 518-519, 1987.
• 15: [15] S. Prastjutrakul and W. J. Kubitz. A timing-driven global router for custom chip design. In Proc. of IEEE Intl. Conf. on Computer-Aided Design, pages 48-51, 1990.
• 16: [16] A. Renaud. Daily generation management at electricite de france: Form planning toward real time. IEEE Transactions on Automatic Control, 38(7):1080-1093, 1993.
• 17: [17] L.W. Ritchey. Busses: What are they and how do they work? Printed Circuit Design Magazine, 2000.
• 18: [18] S. J. Wang, S. M. Shahidehpour, D. S. Kirschen, S. Mokhtari, and G. D. Irisari. Short-term generation scheduling with transmission constraints using augmented Lagrangian relaxation. IEEE Trans. on Power Systems, 10(3):1294-1301, 1995.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Path and circuit problems

General Terms:
Algorithms, Design, Performance