Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This work presents the routing cost valleys (RCV) algorithm - the first published algorithm that simultaneously optimizes all short- and long-path timing constraints in a field-programmable gate array (FPGA). RCV is comprised of a new slack allocation algorithm that produces both minimum and maximum delay budgets for each circuit connection, and a new router that strives to meet and, if possible, surpass these connection delay constraints. RCV achieves excellent results. On a set of 100 large circuits, RCV improves both long-path and short-path timing slack significantly vs. an earlier computer-aided design (CAD) system that focuses solely on long-path timing. Even with no short-path timing constraints, RCV improves the clock speed of circuits by 3.9% on average. Finally, RCV is able to meet timing on all 72 peripheral component interconnect (PCI) cores tested, while an earlier algorithm fails to achieve timing on all 72 cores.

REFERENCES

• 1: [1] "Quartus II Software", www.altera.com.
• 2: [2] "ISE Logic Design Tools", www.xilinx.com.
• 3: Narendra V. Shenoy , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Minimum padding to satisfy short path constraints, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.156-161, November 07-11, 1993, Santa Clara, California, United States
• 4: [4] P. S. Hauge, R. Nair, and E. J. Yoffa, "Circuit Placement for Predictable Performance", ICCAD, 1987, pp. 88-91.
• 5: [5] H. Youssef and E. Shragowitz, "Timing Constraints for Correct Performance", ICCAD, 1990, pp. 24-27.
• 6: J. Frankle, Iterative and adaptive slack allocation for performance-driven layout and FPGA routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.536-542, June 08-12, 1992, Anaheim, California, United States
• 7: Yuh-sheng Lee , Allen C.-H. Wu, A performance and routablity driven router for FPGAs considering path delays, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.557-561, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217588]
• 8: 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]
• 9: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 10: [10] S. Lee and M. Wong, "Timing-Driven Routing for FPGAs Based on Lagrangian Relaxation," IEEE TCAD, April 2003, pp. 506-511.
• 11: [11] "The FPGA Place and Route Challenge", http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html.
• 12: [12] "Stratix Device Family Data Sheet", www.altera.com.