Automatic generation of FPGA routing architectures from high-level descriptions

ABSTRACT

In this paper we present a “high-level” FPGA architecture description language which lets FPGA architects succinctly and quickly describe an FPGA routing architecture. We then present an “architecture generator” built into the VPR CAD tool [1, 2] that converts this high-level architecture description into a detailed and completely specified flat FPGA architecture. This flat architecture is the representation with which CAD optimization and visualization modules typically work. By allowing FPGA researchers to specify an architecture at a high-level, an architecture generator enables quick and easy “what-if” experimentation with a wide range of FPGA architectures. The net effect is a more fully optimized final FPGA architecture. In contrast, when FPGA architects are forced to use more traditional methods of describing an FPGA (such as the manual specification of every switch in the basic file of the FPGA), far less experimentation can be performed in the same time, and the architectures experimented upon are likely to be highly similar, leaving important parts of the design space completely unexplored.This paper describes the automated routing architecture generation problem, and highlights the two key difficulties — creating an FPGA architecture that matches all of an FPGA architect's specifications, while simultaneously determining good values for the many unspecified portions of an FPGA so that a high quality FPGA results. We describe the method by which we generate FPGA routing architectures automatically, and present several examples.

REFERENCES

• 1: V. Betz, "Architecture and CAD for Speed and Area Optimization of FPGAs," Ph.D. Thesis, University of Toronto, 1998.
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 4: S. Brown, J. Rose, and Z. Vranesic, "A Detailed Router for Field-Programmable Gate Arrays," IEEE Trans. on CAD, May 1992, pp. 620 - 628.
• 5: G Lemieux, and S. Brown, "A Detailed Router for Allocating Wire Segments in FPGAs," ACM/SIGDA Physical Design Workshop, 1993, pp. 215 - 226.
• 6: Darren C. Cronquist , Larry McMurchie, Emerald: an architecture-driven tool compiler for FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.144-150, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228391]
• 7: J. Rose and S. Brown, "Flexibility of Interconnection Structures for Field-Programmable Gate Arrays," JSSC, March 1991, pp. 277 - 282.
• 8: Paul Chow , Jonathan Rose , Soon Ong Seo , Kevin Chung , Gerard Páez-Monzón , Immanuel Rahardja, The design of an SRAM-based field-programmable gate array—part I: architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.2, p.191-197, June 1999 [doi>10.1109/92.766746]
• 9: 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]
• 10: Guy G. F. Lemieux , Stephen D. Brown , Daniel Vranesic, On two-step routing for FPGAS, Proceedings of the 1997 international symposium on Physical design, p.60-66, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267682]
• 11: H. Hseih, et al, "Third-Generation Architecture Boosts Speed and Density of Field-Programmable Gate Arrays," CICC, 1990, pp. 31.2.1 - 31.27.
• 12: M. Khellah, S. Brown and Z. Vranesic, "Minimizing Interconnection Delays in Array-Based FPGAs," CICC, 1994, pp. 181 - 184.
• 13: V. Betz, "VPR User's Manual, Version 4.22," Available from http://www.eecg.toronto.edu/vaughn/vpr/vpr.html, Nov. 1998.
• 14: V. Betz and J. Rose, "Cluster-Based Logic Blocks for FPGAs: Area-Efficiency vs. Input Sharing and Size," CICC, 1997, pp. 551 - 554.
• 15: Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
• 16: E Leventis, "Placement Algorithms and Routing Architecture for Long-Line Based FPGAs," Undergraduate Thesis, University of Toronto, 1999.
• 17: B.K. Britton et al., "Second Generation ORCA Architecture Utilizing 0.5 ktm Process Enhances the Speed and Usable Gate Capacity of FPGAs," IEEEInt. ASIC Conf., Sept. 1994, pp. 474 - 478.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages

General Terms:
Design, Performance, Theory