On metrics for comparing routability estimation methods for FPGAs

ABSTRACT

Interconnect management is a critical design issue for large FPGA based designs. One of the most important issues for planning interconnection is the ability to accurately and efficiently predict the routability of a given design on a given FPGA architecture. The recently proposed routability estimation procedure, fGREP [6], produced estimates within 3 to 4% of an actual detailed router. Other known routability estimation methods include RISA [5], Lois's [7] method and Rent's rule based methods [1] [11] [9]. Comparing these methods has been difficult because of the different reporting methods used by the authors. We propose a uniform reporting metric based on comparing the estimates produced with the results of an actual detailed router on both local and global levels. We compare all the above methods using our reporting metric on a large number of benchmark circuits and show that the enhanced fGREP method produces tight estimates that outperform most other techniques.

REFERENCES

• 1: H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison Wesley, Reading, MA, 1990.
• 2: Shankar Balachandran , Parivallal Kannan , Dinesh Bhatia, On Routing Demand and Congestion Estimation for FPGAs, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.639, January 07-11, 2002
• 3: 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
• 4: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, On routability prediction for field-programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.326-330, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164915]
• 5: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 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: 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]
• 8: 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]
• 9: 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]
• 10: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 11: 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.
• 12: X. Yang, R. Kastner, and M. Sarrafzadeh. Congestion Estimation During Top down Placement. IEEE Transactions on CAD, 21, Jan 2002.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
FPGA, RISA, congestion, fGREP, rent's rule, routability estimation