Interconnection lengths and delays estimation for communication links in FPGAs

ABSTRACT

This paper presents a new stochastic model to predictinterconnection lengths of communication links in FPGAs. Based on a stochastic inter-module routing model, expected length and variance of interconnections have been rigorously derived and, thus, delay can be computed based on the length estimate. The theoretical results are compared with experimental results of lengths and delays, which are obtained from implementations of links circuits in an FPGA. The stochastic model provides an accurate prediction of length with an average error of 6.3%. Results also show that theproposed model produces reliable predictions of delay and therefore the methodology can be applied to early stage planning and design optimization for communication links. Moreover, as a byproduct of this work, we also present in this paper an interesting phenomenon which we term "interconnection fringing". The fringing effect is attributed to the competition for routing resources in a communication link and will lengthen interconnections and, therefore, increase the delay.

REFERENCES

• 1: Altera. Stratix II Device Family Data Sheet. 2005.
• 2: Shankar Balachandran , Dinesh Bhatia, A-priori wirelength and interconnect estimation based on circuit characteristics, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639945]
• 3: L. Benini and D. Bertozzi. Network-on-chip Architectures and Design Methods. IEE Proc.-Comput. Digit. Tech., 152:261--272, 2005.
• 4: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 5: S. Brown, J. Rose, and Z. Vranesic. A Stochastic Model to Predict the Routability of Field-Programmable Gate Arrays. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 12:1827--1838, 1993.
• 6: A. El Gamal and Z. Syed. A Stochastic Model for Interconnections in Custom Integrated Circuits. IEEE Trans. on Circuits and Systems, 28:888--894, 1981.
• 7: IBM. CoreConnect(TM) Bus Architectre. White paper, 1999.
• 8: Nachiket Kapre , Nikil Mehta , Michael deLorimier , Raphael Rubin , Henry Barnor , Michael J. Wilson , Michael Wrighton , Andre DeHon, Packet Switched vs. Time Multiplexed FPGA Overlay Networks, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.205-216, April 24-26, 2006 [doi>10.1109/FCCM.2006.55]
• 9: Valavan Manohararajah , Gordon R. Chiu , Deshanand P. Singh , Stephen D. Brown, Difficulty of predicting interconnect delay in a timing driven FPGA CAD flow, Proceedings of the 2006 international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany [doi>10.1145/1117278.1117280]
• 10: Sheldon M. Ross, Introduction to Probability Models, Ninth Edition, Academic Press, Inc., Orlando, FL, 2006
• 11: A. M. Smith. Heterogeneous Reconfigurable Architecture Design: An Optimisation Approach. Ph.D Thesis in Electrical Engineering, Imperial College London, 2006.
• 12: N. J. Steiner. A Standalone Wire Database for Routing and Tracing in Xilinx Virtex, Virtex-E, and Virtex-II FPGAs. Master Thesis in Electrical Engineering, Virginia Polytechnic Institute and State University, 2002.
• 13: D. Stroobandt. A Priori Wire Length Estimates for Digital Design. Springer, 2001.
• 14: Xilinx. Virtex-4 Data Sheets. 2005.
• 15: Xilinx. Xilinx ISE 8.2i Software Manuals. 2006.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.0 General

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

General Terms:
Design, Performance, Theory

Keywords:
FPGA, communciation link, interconnection length prediction