Modeling routing demand for early-stage FPGA architecture development

ABSTRACT

Architecture development for FPGAs has typically been a very empirical discipline, requiring the synthesis of benchmark circuits into candidate architectures. This is difficult to do in the early stages of architecture development, however, because there is no complete architecture to synthesize circuits into. The effort required to create prototype tools for nascent architectures is far too great for every new logic block or routing architecture idea, and so it would be extremely helpful to have a simple and intuitive FPGA interconnect model to guide the architect

In this paper we present such an interconnect model for island-style FPGAs, whose single output is the estimated routing demand (often referred to as W, the number of routing tracks per channel) for an FPGA as a function of several logic block, circuit and routing architecture parameters. The goal of this model is to be as simple as possible, while still accurate enough to be useful, to provide understanding and intuition on FPGA routing. Our methodology is empirical -- we propose model forms based on empirical observations, intuition and some derivation, and then fit models to experimentally generated data

We show the development of the model in stages, beginning with a fully flexible FPGA, and gradually proceeding to one which includes the key parameters that control the flexibility of FPGA routing, and one key parameter describing the logic block and another relating to the typical circuit. We then show how to use these models in early-stage architecture development to provide feedback on several aspects of logic block architecture. We also show how the model can be used to explore the routing architecture space itself and to provide an overall intuition for architecture development

REFERENCES

• 1: Xilinx Inc. The Programmable Logic Data Book. 1999.
• 2: James R. Anderson , Siddharth Sheth , Kaushik Roy, A coarse-grained FPGA architecture for high-performance FIR filtering, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.234-244, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275143]
• 3: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 5: 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]
• 6: D. Chen and J. Rabaey. A Reconfigurable Multiprocessor IC for Rapid Prototyping of Algorithmic Specific High Speed DSP Data Paths. IEEE Journal of Solid State Circuits, 27(12):1895--1904, 1992.
• 7: J. Cong and Y. Ding. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on CAD, pages 1--12, Jan. 1994.
• 8: Jason Cong , Hui Huang , Xin Yuan, Technology mapping and architecture evalution for k/m-macrocell-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.3-23, January 2005 [doi>10.1145/1044111.1044113]
• 9: J.A. Davis, V.K. De, and J.D. Meindl. A Stochastic Wire-Length Distribution for Gigascale Integration: Part I: Derivation and Validation. IEEE Trans. on Electron Devices, 45(3):580--589, March 1998.
• 10: W.E. Donath. Placement and Average Interconnection Lengths of Computer Logic. IEEE Trans. on Circuits and Systems, CAS-26(4):272--277, 1979.
• 11: W.M. Fang. M.A.Sc Thesis: Modeling Routing Demand for Early-Stage FPGA Architecture Development. University of Toronto, Dec. 2007.
• 12: M. Feuer, Connectivity of Random Logic, IEEE Transactions on Computers, v.31 n.1, p.29-33, January 1982 [doi>10.1109/TC.1982.1675882]
• 13: A. El Gamal. Two-Dimensional Stochastic Model for Interconnections in Master Slice Integrated Circuits. IEEE Trans. on Circuits and Systems, CAS-28(2):127--138, Feb 1981.
• 14: P. Kannan and D. Bhatia. Interconnect Estimation for FPGAs. IEEE Trans. on CAD, 25(8):1523--1534, Aug 2006.
• 15: G. Lemieux, E. Lee, M. Tom, and A. Yu. Directional and Single-Driver Wires in FPGA Interconnect. In IEEE International Conference on Field Programmable Technology, pages 41--48, Dec. 2004.
• 16: David Lewis , Vaughn Betz , David Jefferson , Andy Lee , Chris Lane , Paul Leventis , Sandy Marquardt , Cameron McClintock , Bruce Pedersen , Giles Powell , Srinivas Reddy , Chris Wysocki , Richard Cliff , Jonathan Rose, The stratixπ routing and logic architecture, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611821]
• 17: Mathstar. reference: http://www.mathstar.com/.
• 18: OpenCores. reference: http://www.opencores.org/. 2007.
• 19: Arifur Rahman , Shamik Das , Anantha P. Chandrakasan , Rafael Reif, Wiring requirement and three-dimensional integration technology for field programmable gate arrays, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.44-54, February 2003 [doi>10.1109/TVLSI.2003.810003]
• 20: J. Rose and S. Brown. Flexibility of Interconnection Structures for Field Programmable Gate Arrays. IEEE Journal of Solid-State Circuits, 26(3):277--282, 1991.
• 21: Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
• 22: Peter Verplaetse , Dirk Stroobandt , Jan Van Campenhout, A stochastic model for the interconnection topology of digital circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.938-942, 12/1/2001 [doi>10.1109/92.974907 ]
• 23: S. Yang. Logic Synthesis and Optimization Benchmarks, Version 3.0. In Tech. Report, Microelectronics Centre of North Carolina, 1991.
• 24: A. Ye. Single Driver Code in VPR. Private Communication, 2005.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design, Experimentation, Theory

Keywords:
FPGA, architecture, model, routing