research-article

Wotan: Evaluating FPGA Architecture Routability without Benchmarks

Authors:

Vaughn BetzAuthors Info & Claims

ACM Transactions on Reconfigurable Technology and Systems (TRETS), Volume 11, Issue 2

Article No.: 11, Pages 1 - 23

https://doi.org/10.1145/3195800

Published: 26 July 2018 Publication History

Abstract

FPGA routing architectures consist of routing wires and programmable switches that together account for the majority of the fabric delay and area, making evaluation and optimization of an FPGA’s routing architecture very important. Routing architectures have traditionally been evaluated using a full synthesize, pack, place and route CAD flow over a suite of benchmark circuits. While the results are accurate, a full CAD flow has a long runtime and is often tuned to a specific FPGA architecture type, which limits exploration of different architecture options early in the design process. In this article, we present Wotan, a tool to quickly estimate routability for a wide range of architectures without the use of benchmark circuits. At its core, our routability predictor efficiently counts paths through the FPGA routing graph to (1) estimate the probability of node congestion and (2) estimate the probabilities to successfully route a randomized subset of (source, sink) pairs, which are then combined into an overall routability metric. We describe our predictor and present routability estimates for a range of 6-LUT and 4-LUT architectures using mixes of wire types connected in complex ways, showing a rank correlation of 0.91 with routability results from the full VPR CAD flow while requiring 18× less CPU effort.

References

[1]

Vaughn Betz and Jonathan Rose. 1999. FPGA routing architecture: Segmentation and buffering to optimize speed and density. In FPGA. 59--68.

Digital Library

[2]

Vaughn Betz, Jonathan Rose, and Alexander Marquardt. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers.

Digital Library

[3]

Stephen Brown, Jonathan Rose, and Zvonko G. Vranesic. 1993. A stochastic model to predict the routability of field-programmable gate arrays. IEEE Trans. Comput.-Aid. Des. 12, 12 (1993), 1827--1838.

Digital Library

[4]

Yao-Wen Chang and D. F. Wong. 1996. Universal switch modules for FPGA design. ACM Trans. Des. Autom. Electon. Syst. 1, 1 (1996), 80--101.

Digital Library

[5]

Charles Colbourn. 1987. The Combinatorics of Network Reliability. Oxford University Press.

Digital Library

[6]

Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.

Digital Library

[7]

Intel Corporation. 2014. Advancing Moore’s Law in 2014. Retrieved from https://www.intel.com/content/dam/www/public/us/en/documents/presentation/advancing-moores-law-in-2014-presentation.pdf.

[8]

Joydip Das and Steven Wilton. 2011. An analytical model relating FPGA architecture parameters to routability. In FPGA. 181--184.

Digital Library

[9]

Abbas El Gamal. 1981. Two-dimensional stochastic model for interconnections in master slice integrated circuits. IEEE Trans. Circ. Syst. 28, 2 (1981), 127--138.

[10]

Wei Fang and Jonathan Rose. 2008. Modeling routing demand for early-stage FPGA architecture development. In FPGA. 139--148.

Digital Library

[11]

International Technology Roadmap for Semiconductors. 2013. Interconnect. Retrieved from http://www.itrs2.net/2013-itrs.html.

[12]

Parivallal Kannan and Dinesh Bhatia. 2006. Interconnect estimation for FPGAs. IEEE Trans. Comput.-Aid. Des. 25 (2006), 1523--1534.

Digital Library

[13]

T. Kong. 2002. A novel net weighting algorithm for timing-driven placement. In ICCAD. IEEE, 172--176.

Digital Library

[14]

Ian Kuon and Jonathan Rose. 2006. Measuring the gap between FPGAs and ASICs. In FPGA. 21--30.

Digital Library

[15]

Lattice Semiconductor. 2017. iCE40 LP/HX family data sheet.

[16]

G. Lemieux, E. Lee, M. Tom, and A. Yu. 2004. Directional and single-driver wires in FPGA interconnect. In FPT. 41--48.

[17]

David Lewis and others. 2013. Architectural enhancements in stratix V. In FPGA. 147--156.

Digital Library

[18]

Mingjie Lin, John Wawrzynek, and Abbas El Gamal. 2010. Exploring FPGA routing architecture stochastically. IEEE Trans. Comput.-Aid. Des. 29, 10 (2010), 1509--1522.

Digital Library

[19]

Jinan Lou, Thakur Shashidhar, Shankar Krishnamoorthy, and Henry Sheng. 2002. Estimating routing congestion using probabilistic analysis. IEEE Trans. Comput.-Aid. Des. 21, 1 (2002), 32--41.

Digital Library

[20]

Jason Luu and others. 2014. VTR 7.0: Next generation architecture and CAD system for FPGAs. Trans. Recofig. Technol. Syst. 7, 2 (2014), 1--30

Digital Library

[21]

E. F. Moore and C. E. Shannon. 1956. Reliable circuits using less reliable relays. J. Franklin Inst. 262, 3 (Oct. 1956), 191--208.

[22]

Kevin Murray, Scott Whitty, Suya Liu, Jason Luu, and Vaughn Betz. 2013. Titan: Enabling large and complex benchmarks in academic CAD. In FPL.

[23]

Oleg Petelin and Vaughn Betz. 2015. Wotan: A tool for rapid evaluation of FPGA architecture routability without benchmarks. In FPL.

[24]

Oleg Petelin and Vaughn Betz. 2016. The speed of diversity: Exploring complex FPGA routing topologies for the global metal layer. In FPL.

[25]

Justin Richardson, Steven Fingulin, Diwakar Raghunathan, Chris Massie, Alan George, and Herman Lam. 2010. Comparative analysis of HPC and accelerator devices: Computation, memory, I/O, and power. In HPRCTA. 1--10.

[26]

Jonathan Rose and Stephen Brown. 1991. Flexibility of interconnection structures for field-programmable gate arrays. J. Solid State Circ. 26, 3 (1991), 277--282.

[27]

Akshay Sharma, Carl Ebeling, and Scott Hauck. 2005. Architecture adaptive routability-driven placement for FPGAs. In FPL. 427--432.

[28]

Akshay Sharma and Scott Hauck. 2005. Accelerating FPGA routing using architecture-adaptive A* techniques. In FPT. 225--232.

[29]

Alastair Smith, George Constantinides, Steven Wilton, and Peter Cheung. 2009. Concurrently optimizing FPGA architecture parameters and transistor sizing: Implications for FPGA design. In FPT. 54--61.

[30]

Alastair Smith, Joydip Das, and Steven Wilton. 2009. Wirelength modeling for homogeneous and heterogeneous FPGA architectural development. In FPGA. 181--190.

Digital Library

[31]

Leslie Valiant. 1979. The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 3 (1979).

[32]

Steven J. E. Wilton. 1997. Architectures and Algorithms for Field-Programmable Gate Arrays with Embedded Memory. Ph.D. Dissertation. University of Toronto.

Digital Library

Cited By

Greene JIenne PZhang Z(2023)FPGA Mux Usage and Routability Estimates without Explicit RoutingProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573045(141-147)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573045
Gunter AWilton S(2023)A Machine Learning Approach for Predicting the Difficulty of FPGA Routing Problems2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM57271.2023.00016(63-74)Online publication date: May-2023
https://doi.org/10.1109/FCCM57271.2023.00016
Chochaev RZheleznikov DIvanova GGavrilov SEnns V(2021)FPGA Routing Architecture Estimation Models and MethodsRussian Microelectronics10.1134/S106373972107004050:7(509-515)Online publication date: 29-Dec-2021
https://doi.org/10.1134/S1063739721070040
Show More Cited By

Index Terms

Wotan: Evaluating FPGA Architecture Routability without Benchmarks
1. Hardware
  1. Electronic design automation
    1. Methodologies for EDA
      1. Software tools for EDA
  2. Integrated circuits
    1. Reconfigurable logic and FPGAs
      1. Programmable interconnect
2. Networks
  1. Network properties
    1. Network reliability

Recommendations

Exploring FPGA routing architecture stochastically
Special section on the ACM IEEE international conference on formal methods and models for codesign (MEMOCODE) 2009

This paper proposes a systematic strategy to efficiently explore the design space of field-programmable gate array (FPGA) routing architectures. The key idea is to use stochastic methods to quickly locate near-optimal solutions in designing FPGA routing ...
t-QuadPlace: Timing Driven Quadratic Placement using Quadrisection Partitioning for FPGAs (Abstact Only)
FPGA '16: Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Conventional Simulated Annealing (SA) based placement methods for FPGAs generate high quality results in terms of wirelength and critical path delay, but at a high runtime cost. In case of modern multi-million gate FPGAs, SA-based methods for placement ...
Hardware accelerated FPGA placement

A key advantage of field-programmable gate arrays (FPGAs) over full-custom and semi-custom devices is that they provide relatively quick implementation from concept to physical realization. However, as modern FPGAs reach close to one million logic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Reconfigurable Technology and Systems

ACM Transactions on Reconfigurable Technology and Systems Volume 11, Issue 2

June 2018

109 pages

ISSN:1936-7406

EISSN:1936-7414

DOI:10.1145/3242893

Editor:
Steve Wilton
Department of Electrical and Computer Engineering / University of British Columbia / Kaiser 4112, 5500-2332 Main Mall / Vancouver, BC V6T 1Z4 Canada

Issue’s Table of Contents

Copyright © 2018 ACM.

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 the author(s) 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

Publication History

Published: 26 July 2018

Accepted: 01 March 2018

Revised: 01 February 2018

Received: 01 November 2017

Published in TRETS Volume 11, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Lattice Semiconductor and the NSERC/Altera Industrial Research Chair in Programmable Silicon

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
269
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Greene JIenne PZhang Z(2023)FPGA Mux Usage and Routability Estimates without Explicit RoutingProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573045(141-147)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573045
Gunter AWilton S(2023)A Machine Learning Approach for Predicting the Difficulty of FPGA Routing Problems2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM57271.2023.00016(63-74)Online publication date: May-2023
https://doi.org/10.1109/FCCM57271.2023.00016
Chochaev RZheleznikov DIvanova GGavrilov SEnns V(2021)FPGA Routing Architecture Estimation Models and MethodsRussian Microelectronics10.1134/S106373972107004050:7(509-515)Online publication date: 29-Dec-2021
https://doi.org/10.1134/S1063739721070040
Chochaev RGavrilov S(2021)Evaluating FPGA Routing Architectures with Complex Grid Layouts2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus)10.1109/ElConRus51938.2021.9396240(2604-2635)Online publication date: 26-Jan-2021
https://doi.org/10.1109/ElConRus51938.2021.9396240

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents