Cited By
View all- Liu YXiong WWang JLai J(2024)A new model for parametrically evaluating the routability of GRM FPGAIEICE Electronics Express10.1587/elex.20.2023055621:3(20230556-20230556)Online publication date: 10-Feb-2024
FPGA Mux Usage and Routability Estimates without Explicit Routing
Pages 141 - 147
Abstract
A new algorithm is proposed to rapidly evaluate an FPGA routing architecture without need of explicitly routing benchmark applications. The algorithm takes as input a probability distribution of nets to be accommodated and a description of an architecture. It produces an estimate for the usage of each type of mux in the FPGA (including intra-cluster muxes), valuable feedback to the architect. The estimates are shown to correlate with actual routed applications in both academic and commercial architectures. This is due in part to the algorithm's novel ability to account for long and multi-fanout nets. Run time is reduced by applying periodic graphs to model FPGAs' regular structure.
We then show how Percolation Theory (a branch of statistical physics) can be applied to elucidate the relationship between mux usage and routability. We show that any blockages when routing a net are most likely to occur in the neighborhood of its terminals, and demonstrate a quantitative relationship among the post-placement wirelength of an application, the percolation threshold of an architecture, and the channel width required to map the application to the architecture. Supporting experimental data is provided.
References
[1]
Prathima Agrawal. 1976. On the Probability of Success in a Routing Process. Proc. IEEE, Vol. 64, 11 (1976), 1624--1625. https://doi.org/10.1109/PROC.1976.10385
[2]
Prathima Agrawal and Melvin Breuer. 1979. Experiments with a Density Router for PC Cards. IEEE Trans. Comput., Vol. C-28, 3 (1979), 262--267. https://doi.org/10.1109/TC.1979.1675333
[3]
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond W. Yeung. 2000. Network Information Flow. IEEE Transactions on Information Theory, Vol. 46, 4 (2000), 1204--1216. https://doi.org/10.1109/18.850663
[4]
Michael Aizenman, Harry Kesten, and Charles M. Newman. 1987. Uniqueness of the Infinite Cluster and Continuity of Connectivity Functions for Short and Long Range Percolation. Communications in Mathematical Physics, Vol. 111, 4 (1987), 505--531. https://doi.org/10.1007/BF01219071
[5]
Scott Chin and Steven Wilton. 2007. Memory Footprint Reduction for FPGA Routing Algorithms. In 2007 International Conference on Field-Programmable Technology. IEEE, 1--8. https://doi.org/10.1109/FPT.2007.4439225
[6]
Joydip Das and Steven J. E. Wilton. 2013. Towards Development of an Analytical Model Relating FPGA Architecture Parameters to Routability. ACM Trans. Reconfigurable Technol. Syst., Vol. 6, 2, Article 10 (aug 2013), 24 pages. https://doi.org/10.1145/2499625.2499627
[7]
Yuzheng Ding, Peter Suaris, and Nanchi Chou. 2005. The Effect of Post-layout Pin Permutation on Timing. In Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-programmable Gate Arrays. 41--50. https://doi.org/10.1145/1046192.1046199
[8]
W. E. Donath. 1981. Wire Length Distribution for Placements of Computer Logic. IBM Journal of Research and Development, Vol. 25, 3 (1981), 152--155. https://doi.org/10.1147/rd.252.0152
[9]
H. L. Frisch, S. B. Gordon, V. A. Vyssotsky, and J. M. Hammersley. 1962 a. Monte Carlo Solution of Bond Percolation Processes in Various Crystal Lattices. Bell System Technical Journal, Vol. 41, 3 (1962), 909--920. https://doi.org/10.1002/j.1538--7305.1962.tb00482.x
[10]
H. L. Frisch, J. M. Hammersley, and D. J. A. Welsh. 1962 b. Monte Carlo Estimates of Percolation Probabilities for Various Lattices. Phys. Rev., Vol. 126 (May 1962), 949--951. Issue 3. https://doi.org/10.1103/PhysRev.126.949
[11]
Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-hardness.
[12]
Jonathan W. Greene and Abbas El Gamal. 1984. Configuration of VLSI Arrays in the Presence of Defects. Journal of the ACM (JACM), Vol. 31, 4 (1984), 694--717. https://doi.org/10.1145/1634.2377
[13]
Franz Höfting and Egon Wanke. 1993. Polynomial Algorithms for Minimum Cost Paths in Periodic Graphs. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Austin, Texas, USA) (SODA '93). Society for Industrial and Applied Mathematics, USA, 493--499.
[14]
Kazuo Iwano and Kenneth Steiglitz. 1987. Testing for cycles in infinite graphs with periodic structure. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 46--55.
[15]
George Karakostas. 2008. Faster Approximation Schemes for Fractional Multicommodity Flow Problems. ACM Trans. Algorithms, Vol. 4, 1, Article 13 (mar 2008), 17 pages. https://doi.org/10.1145/1328911.1328924
[16]
Harry Kesten. 1987. Percolation Theory and First-passage Percolation. The Annals of Probability, Vol. 15, 4 (1987), 1231--1271. https://doi.org/10.1214/aop/1176991975
[17]
Muralidharan Kodialam and James B. Orlin. 1991. Recognizing Strong Connectivity in (Dynamic) Periodic Graphs and Its Relation to Integer Programming. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, USA) (SODA '91). Society for Industrial and Applied Mathematics, USA, 131--135.
[18]
Mingjie Lin, John Wawrzynek, and Abbas El Gamal. 2010. Exploring FPGA Routing Architecture Stochastically. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 29, 10 (2010), 1509--1522. https://doi.org/10.1109/TCAD.2010.2061530
[19]
Microchip. 2022. PolarFire FPGAs. https://www.microchip.com/en-us/products/fpgas-and-plds/fpgas/polarfire-fpgas Retrieved December 20, 2022 from
[20]
Rajeev Motwani, Joseph Naor, and Prabhakar Raghavan. 1997. Randomized Approximation Algorithms in Combinatorial Optimization. In Approximation Algorithms for NP-Hard Problems, Dorit Hochbaum (Ed.). PWS Publishing Co., Boston.
[21]
Kevin E. Murray, Oleg Petelin, Sheng Zhong, Jia Min Wang, Mohamed Eldafrawy, Jean-Philippe Legault, Eugene Sha, Aaron G. Graham, Jean Wu, Matthew J. P. Walker, Hanqing Zeng, Panagiotis Patros, Jason Luu, Kenneth B. Kent, and Vaughn Betz. 2020. VTR 8: High-Performance CAD and Customizable FPGA Architecture Modelling. ACM Transactions on Reconfigurable Technology and Systems, Vol. 13, 2, Article 9 (jun 2020), 55 pages. https://doi.org/10.1145/3388617
[22]
Oleg Petelin and Vaughn Betz. 2018. Wotan: Evaluating FPGA Architecture Routability without Benchmarks. ACM Transactions on Reconfigurable Technology and Systems, Vol. 11, 2, Article 11 (jul 2018), 23 pages. https://doi.org/10.1145/3195800
[23]
Arifur Rahman, Satyaki Das, Tim Tuan, and Anirban Rahut. 2005. Heterogeneous Routing Architecture for Low-power FPGA Fabric. In Proceedings of the IEEE 2005 Custom Integrated Circuits Conference. IEEE, 183--186. https://doi.org/10.1109/CICC.2005.1568637
[24]
Nadia Rezzak, Jih-Jong Wang, Stephen Varela, Gregory Bakker, and Ang Nan Gu. 2018. Neutron and Proton Characterization of Microsemi 28 nm PolarFire SONOS-based FPGA. In 2018 IEEE Radiation Effects Data Workshop (REDW). IEEE, 1--5. https://doi.org/10.1109/NSREC.2018.8584300
[25]
Xifan Tang, Edouard Giacomin, Aurélien Alacchi, and Pierre-Emmanuel Gaillardon. 2019. A Study on Switch Block Patterns for Tileable FPGA Routing Architectures. In 2019 International Conference on Field-Programmable Technology (ICFPT). IEEE, 247--250. https://doi.org/10.1109/ICFPT47387.2019.00039
[26]
Dahai Xu, Mung Chiang, and Jennifer Rexford. 2007. DEFT: Distributed Exponentially-weighted Flow Splitting. In IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications. IEEE, 71--79. https://doi.org/10.1109/INFCOM.2007.17
[27]
S. Zheng, J. Qian, H. Zhou, and L. Wang. 2022. GRAEBO: FPGA General Routing Architecture Exploration via Bayesian Optimization. In Proceedings of the IEEE 2022 International Conference on Field Programmable Logic and Applications. IEEE.
Index Terms
- FPGA Mux Usage and Routability Estimates without Explicit Routing
Recommendations
An effective hop-based detailed router for FPGAs for optimizing track usage and circuit performance
GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSIWe have developed a hop-based complete detailed router ROAD-HOP that uses the Bump & Refit (B&R) approach to route a FPGA circuit in a near-optimal manner. This approach is based on generating a minimum-spanning tree (MST) from the complete pin-to-pin ...
Routability-Driven FPGA Placement Contest
ISPD '16: Proceedings of the 2016 on International Symposium on Physical DesignThe advances of FPGA technology and increasing size of FPGA designs pose great challenges on FPGA design tools. Deep research on FPGA physical design problems is paramount to improve industrial tools. This contest is the first ISPD contest on FPGA CAD ...
UTPlaceF: A routability-driven FPGA placer with physical and congestion aware packing
2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)FPGA packing and placement without routability consideration could lead to unroutable results for high-utilization designs. Conventional FPGA packing and placement approaches are shown to have severe difficulties to yield good routability. In this paper, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2023
283 pages
Copyright © 2023 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 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]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 February 2023
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
FPGA '23
Sponsor:
FPGA '23: The 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays
February 12 - 14, 2023
CA, Monterey, USA
Acceptance Rates
Overall Acceptance Rate 125 of 627 submissions, 20%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 595Total Downloads
- Downloads (Last 12 months)221
- Downloads (Last 6 weeks)24
Reflects downloads up to 15 Jan 2025
Other Metrics
Citations
Cited By
View all- Liu YXiong WWang JLai J(2024)A new model for parametrically evaluating the routability of GRM FPGAIEICE Electronics Express10.1587/elex.20.2023055621:3(20230556-20230556)Online publication date: 10-Feb-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in