skip to main content
research-article

Energy and switch area optimizations for FPGA global routing architectures

Published: 23 January 2009 Publication History

Abstract

Low energy and small switch area usage are two important design objectives in FPGA global routing architecture design. This article presents an improved MCF model based CAD flow that performs aggressive optimizations, such as topology and wire style optimization, to reduce the energy and switch area of FPGA global routing architectures. The experiments show that when compared to traditional mesh architecture, the optimized FPGA routing architectures achieve up to 10% to 15% energy savings and up to 20% switch area savings in average for a set of seven benchmark circuits.

References

[1]
Albrecht, C. 2000. Provably good global routing by a new approximation algorithm for multicommodity flow. In Proceedings of the International Symposium on Physical Design. 19--25.
[2]
Albrecht, C., Kahng, A., Mandoiu, I., and Zelikovsky, A. 2007. Multicommodity flow algorithms for buffered global routing. In Approximation Algorithms and Metaheuristics, Chapter 80.
[3]
Betz, V. and Rose, J. 1997. Vpr: A new packing, placement and routing tool for FPGA research. In Proceedings of International Workshop on Field-Programmable Logic and Applications. 213--222.
[4]
Betz, V., Rose, J., and Marquardt, A. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers.
[5]
Brown, S., Khellah, M., and Lemieux, G. 1996. Segmented routing for speed-performance and routability in field-programmable gate arrays. J. VLSI Des. 4, 4, 275--291.
[6]
Brown, S., Khellah, M., and Vranesic, Z. 1996. Minimizing fpga interconnect delays. IEEE Des. Test Mag. 16--23.
[7]
Carden, R. and Cheng, C. 1991. A global router using an efficient approximate multicommodity multiterminal flow algorithm. In Proceedings of the Design Automation Conference. 316--321.
[8]
Carden, R., Li, J., and Cheng, C. 1996. A global routing with a theoretical bound on the optimum solution. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 15, 208--216.
[9]
Chen, H., Shi, R., Cheng, C., and Harris, D. 2005. Surfliner: A distortionless electrical signaling scheme for speed of light on-chip communications. In Proceedings of the IEEE International Conference on Computer Design. 497--502.
[10]
Chow, P., Seo, S., Rose, J., Chung, K., Paez, G., and Rahardja, I. 1999. The design of an sram-based field-programmable gate array, part i: Architecture. IEEE Trans. VLSI Syst. 7, 191--197.
[11]
Choy, N., Chin, S., Lee, C., Poon, K., Lamoureux, J., Yan, A., Wilton, S., Ang, S.-S., and Luk, W. Power modeling for FPGA's. http://www.ece.ubc.ca/stevew/powermodel.html.
[12]
Christie, P. and Stroobandt, D. 2000. The interpretation and application of Rent's rule. IEEE Trans. VLSI Syst. 8, 6, 639--648.
[13]
Cong, J. and Ding, Y. 1994. Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 1--12.
[14]
Dambre, J., Stroobandt, D., and Campenhout, J. V. 2004. Toward the accurate prediction of placement wire length distributions in vlsi circuits. IEEE Trans. VLSI Syst. 12, 4, 339--348.
[15]
DeHon, A. and Rubin, R. 2004. Design of fpga interconnect for multilevel metallization. IEEE Transactions on VLSI Syst. 12, 10, 1038--1050.
[16]
Donath, W. E. 1981. Wire length distribution for placements of computer logic. IBM J. Resear. Devel. 25, 152--155.
[17]
Garg, N. and Konemann, J. 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. Proceedings of the 39th Annual IEEE Symp. on Foundations of Computer Science, 300--309.
[18]
Hu, Y., Chen, H., Zhu, Y., Chien, A. A., and Cheng, C. 2005. Physical synthesis of energy-efficient nocs through topology exploration and wire style optimization. In Proceedings of the International Conference on Computer Design. 111--118.
[19]
Hu, Y., Zhu, Y., Chen, H., Graham, R., and Cheng, C. 2006. Communication latency aware low power NOC synthesis. In Proceedings of the Design Automation Conference. 574--579.
[20]
Hutton, M., Rose, J., Grossman, J., and Cornei, D. 1998. Characterization and parameterized generation of synthetic combinational benchmark circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 17, 10, 985--996.
[21]
Khellah, M., Brown, S., and Vranesic, Z. 1994. Minimizing interconnection delays in array-bassed fpgas. In Proceedings of the Custom Integrated Circuits Conference. 181--184.
[22]
Lee, S., Xiang, H., Wong, D., and Sun, R.Y. 2003. Wire type assignment for fpga routing. In Proceedings of the International Symposium on Field Programmable Gate Arrays. 61--67.
[23]
Lemieux, G., Lee, E., Tom, M., and Yu, A. 2004. Directional and single-driver wires in FPGA interconnect. In Proceedings of the IEEE International Conference on Field-Programmable Technology. 41--48.
[24]
Mehlhorn, K. 1988. A faster approximation algorithm for the steiner problem in graphs. Inform. Process. Lett. 27, 3, 125--128.
[25]
Poon, K., Wilton, S., and Yan, A. 2002. A detailed power model for field programmable gate arrays. ACM Trans. Des. Automat. Electr. Syst. 10, 2, 279--302.
[26]
Sentovich, E. and Al, E. 1992. Sis: A system for sequential circuit analysis. Tech. rep. No. UCB/ERL M92/41, University of California, Berkeley.
[27]
Shahrokhi, F. and Matula, D. 1990. The maximum concurrent flow problem. J. Assoc. Comput. Math. 37, 2, 318--334.
[28]
Shyu, M., Wu, G., Chang, Y., and Chang, Y. 2000. Generic universal switch blocks. IEEE Trans. Comput. 49, 4, 348--359.
[29]
Yang, S. 1991. Logic synthesis and optimization benchmarks, version 3.0. Tech. rep. Microelectronics Center of North Carolina.
[30]
Ye, A. and Rose, J. 2005. Using bus-based connections to improve field-programmable gate array density for implementing datapath circuits. In Proceedings of the International Symposium on Field Programmable Gate Arrays. 3--13.
[31]
Ye, A., Rose, J., and Lewis, D. 2003. Architecture of datapath-oriented coarse-grain logic and routing for FPGAs. In Proceedings of the Custom Integrated Circuits Conference. 61--64.

Cited By

View all
  • (2015)Improving network routing energy-efficiency for real-time workloads by stochastic service modelInternational Journal of Information and Communication Technology10.1504/IJICT.2015.0684067:2/3(302-315)Online publication date: 1-Apr-2015
  • (2013)Towards development of an analytical model relating FPGA architecture parameters to routabilityACM Transactions on Reconfigurable Technology and Systems10.1145/2499625.24996276:2(1-24)Online publication date: 2-Aug-2013
  • (2010)Optimal Design for FPGA Interconnect Based on Combinations of Single-driver and Multi-driver WiresJournal of Electronics & Information Technology10.3724/SP.J.1146.2009.0100732:8(2023-2027)Online publication date: 26-Aug-2010

Index Terms

  1. Energy and switch area optimizations for FPGA global routing architectures

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Design Automation of Electronic Systems
      ACM Transactions on Design Automation of Electronic Systems  Volume 14, Issue 1
      January 2009
      444 pages
      ISSN:1084-4309
      EISSN:1557-7309
      DOI:10.1145/1455229
      Issue’s Table of Contents
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Journal Family

      Publication History

      Published: 23 January 2009
      Accepted: 01 July 2008
      Revised: 01 May 2008
      Received: 01 October 2007
      Published in TODAES Volume 14, Issue 1

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. FPGA
      2. global routing
      3. low power

      Qualifiers

      • Research-article
      • Research
      • Refereed

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)2
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2015)Improving network routing energy-efficiency for real-time workloads by stochastic service modelInternational Journal of Information and Communication Technology10.1504/IJICT.2015.0684067:2/3(302-315)Online publication date: 1-Apr-2015
      • (2013)Towards development of an analytical model relating FPGA architecture parameters to routabilityACM Transactions on Reconfigurable Technology and Systems10.1145/2499625.24996276:2(1-24)Online publication date: 2-Aug-2013
      • (2010)Optimal Design for FPGA Interconnect Based on Combinations of Single-driver and Multi-driver WiresJournal of Electronics & Information Technology10.3724/SP.J.1146.2009.0100732:8(2023-2027)Online publication date: 26-Aug-2010

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media