A provably good algorithm for high performance bus routing

ABSTRACT

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools can not successfully handle these constraints any more. We focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing; and use those resources for length extension afterwards. We first propose a provably optimal algorithm for routing nets with min-area max-length constraints. Then, we extend this algorithm to the case where minimum constraints are given as exact length bounds. We also prove that this algorithm is optimal within a constant factor. Both algorithms proposed are also shown to be scalable for large circuits, since the respective time complexities are O(A) and O(A log A), where A is the area of the intermediate region between chips.

REFERENCES

• 1: 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
• 2: [2] 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., 1992.
• 3: [3] 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.
• 4: 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
• 5: 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]
• 6: Chi-Ping Hsu, General river routing algorithm, Proceedings of the 20th conference on Design automation, p.578-583, June 27-29, 1983, Miami Beach, Florida, United States
• 7: [7] 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.
• 8: [8] S. Lee and M. D. F. Wong. Timing-driven routing for fpgas based on lagrangian relaxation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 506-510, 2003.
• 9: [9] C. E. Leiserson and R. Y. Pinter. Optimal placement for river routing. In Proc. of the CMU Conf. on VLSI Systems and Computations, 1981.
• 10: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 11: [11] J. Ludwig. IBM Systems Group. Private communication, 2004.
• 12: [12] M. M. Ozdal and M. D. F. Wong. An algorithmic study of single-layer bus routing for high-speed boards. Manuscript.
• 13: 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]
• 14: Ron Y. Pinter, On routing two-point nets across a channel, Proceedings of the 19th conference on Design automation, p.894-902, January 1982
• 15: [15] R. Y. Pinter. River routing: Methodology and analysis. In Proc. of the 3rd Caltech Conf. on VLSI, 1983.
• 16: [16] 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.
• 17: [17] L. W. Ritchey. Busses: What are they and how do they work? Printed Circuit Design Magazine, 2000.
• 18: Hai Zhou , D. F. Wong, Optimal river routing with crosstalk constraints, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.496-514, July 1998 [doi>10.1145/293625.293636]