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

ABSTRACT

Interconnection planning is becoming an important design issue for ASICs and large FPGAs. As the technology shrinks and the design density increases, proper planning of routing resources becomes all the more important to ensure rapid and feasible design convergence. One of the most important issues for planning interconnection is the ability to predict the routability of a given placed design. This paper provides insight into the workings of recently proposed method by Lou et. al.[Lou_Shankar] and compares it with our proposed methodology, fGREP[fGREP]. We have implemented the two methods for a generic FPGA architecture and compare the performance, accuracy and usability of their estimates. We use the well known FPGA physical design suite VPR[VPR], as a common comparison tool. Our experiments show that fGREP produces far better routing estimates but at larger execution times than Lou's method. Insight into what makes the methods work and where they falter are also discussed in detail.

REFERENCES

• 1: [1] H. B. Bakoglu. Circuit, Interconnections, and Packaging for VLSI. Addison Wesley, Reading, MA, 1990.
• 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] A. A. E. Gamal. Two-Dimensional Stochastic Model for Interconnections in Master Slice Integrated Circuits. IEEE Trans. CAS., Feb 1981.
• 4: [4] M. Garey and D. Johnson. The Rectilinear Steiner Problem is NP-complete. SIAM Journal on Applied Mathematics , 32:826-834, 1977.
• 5: [5] J. Griffith, G. Robins, J. Salowe, and T. Zhang. Closing the Gap: Near Optimal Steiner Trees in Polynomial Time. IEEE Transactions on Computer-Aided Design, 13(11):1351-1365, November 1994.
• 6: PariVallal Kannan , Shankar Balachandran , Dinesh Bhatia, fGREP - Fast Generic Routing Demand Estimation for Placed FPGA Circuits, Proceedings of the 11th International Conference on Field-Programmable Logic and Applications, p.37-47, August 27-29, 2001
• 7: Wei Li , D. K. Banerji, Routability Prediction for Hierarchical FPGAs, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.256, March 04-06, 1999
• 8: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 9: [9] H. V. Marck, D. Stroobandt, and J. V. Campenhout. Toward an Extension of Rent's Rule for Describing Local Variations in Interconnection Complexity. In Proceedings of the 4th International Conference for Young Computer Scientists, pages 136-141, 1995.
• 10: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 11: [11] S. K. Nag and R. Rutenbar. Performance-driven Simultaneous Placement and Routing for FPGAs. IEEE Transactions on CAD, June 1998.
• 12: G. Parthasarathy , M. Marek-Sadowska , Arindam Mukherjee , Amit Singh, Interconnect complexity-aware FPGA placement using Rent's rule, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.115-121, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368806]
• 13: [13] S. Sastry and A. Parker. Stochastic Models for Wireability Analysis of Gate Arrays. IEEE Trans. on CAD, Jan 1986.
• 14: [14] S. Brown, J. Rose, and Z. G. Vranesic. A Stochastic Model to Predict the Routability of Field Programmable Gate Arrays. IEEE Transactions on CAD, pages 1827-1838, Dec 1993.
• 15: Maogang Wang , Majid Sarrafzadeh, On the behavior of congestion minimization during placement, Proceedings of the 1999 international symposium on Physical design, p.145-150, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300044]
• 16: R. Glenn Wood , Rob A. Rutenbar, FPGA routing and routability estimation via Boolean satisfiability, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.119-125, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258322]