Article

Using sparse crossbars within LUT

Authors:

Guy Lemieux,

David LewisAuthors Info & Claims

FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays

Pages 59 - 68

https://doi.org/10.1145/360276.360299

Published: 01 February 2001 Publication History

Get Access

Abstract

In FPGAs, the internal connections in a cluster of lookup tables (LUTs) are often fully-connected like a full crossbar. Such a high degree of connectivity makes routing easier, but has significant area overhead. This paper explores the use of sparse crossbars as a switch matrix inside the clusters between the cluster inputs and the LUT inputs. We have reduced the switch densities inside these matrices by 50% or more and saved from 10 to 18% in area with no degradation to critical-path delay. To compensate for the loss of routability, increased compute time and spare cluster inputs are required. Further investigation may yield modest area and delay reductions.

References

[1]

E. Ahmed. The effect of logic block granularity on deepsubmicron FPGA performance and density. Master's thesis, Department of Electrical and Computer Engineering, University of Toronto, 2001.

Google Scholar

[2]

E. Ahmed and J. Rose. The effect of LUT and cluster size on deep-submicron FPGA performance and density. In ACM/SIGDA Int'l. Symp. on FPGAs, pages 3-12, 2000.

Digital Library

Google Scholar

[3]

V. Betz and J. Rose. VPR: A new packing, placement and routing tool for FPGA research. In Field-Programmable Logic, pages 213-222, 1997.

Digital Library

Google Scholar

[4]

V. Betz, J. Rose, and A. Marquardt. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers, Boston, 1999.

Digital Library

Google Scholar

[5]

J. Cong and Y. Ding. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Transactions on Computer-Aided Design, pages 1-12, January 1994.

Google Scholar

[6]

W. Elmore. The transient response of damped linear networks with particular regard to wideband amplifiers. Journal of Applied Physics, pages 55-63, January 1948.

Crossref

Google Scholar

[7]

C. B. Laboratory. LGSynth93 suite. http://www.cbl.ncsu.edu/www/.

Google Scholar

[8]

G. Lemieux, P. Leventis, and D. Lewis. Generating highly-routable sparse crossbars for PLDs. In ACM/SIGDA Int'l. Symp. on FPGAs, pages 155-164, Monterey, CA, February 2000.

Digital Library

Google Scholar

[9]

A. Marquardt, V. Betz, and J. Rose. Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density. In ACM/SIGDA Int'l. Symp. on FPGAs, pages 37-46, 1999.

Digital Library

Google Scholar

[10]

A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for FPGAs. In ACM/SIGDA Int'l. Symp. on FPGAs, pages 203-213, 2000.

Digital Library

Google Scholar

[11]

M. I. Masud. FPGA routing structures: A novel switch block and depopulated interconnect matrix architectures. Master's thesis, Department of Electrical and Computer Engineering, University of British Columbia, December 1999.

Google Scholar

[12]

J. Rose and S. Brown. Flexibility of interconnection structures in field-programmable gate arrays. IEEE Journal of Solid State Circuits, 26(3):277-282, March 1991.

Crossref

Google Scholar

[13]

E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuit analysis. Technical Report UCB/ERL M92/41, University of California, Berkeley, May 1992.

Google Scholar

[14]

M. Sheng and J. Rose. Mixing buffers and pass transistors in FPGA routingarchitectures. In ACM/SIGDA Int'l. Symp. on FPGAs, 2001.

Digital Library

Google Scholar

Cited By

View all

Rostami Sani SYe A(2024)Evaluating the Impact of Using Multiple-Metal Layers on the Layout Area of Switch Blocks for Tile-Based FPGAs in FinFET 7nmACM Transactions on Reconfigurable Technology and Systems10.1145/363905517:1(1-29)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3639055
Shi KWang L(2024)An Open-Source Tool to Model and Explore Complex Routing Architecture for FPGA2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617494(734-739)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617494
Shi KZhou HWang L(2023)Explore the Feedback Interconnects in Intra-Cluster Routing for FPGAs2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00034(250-253)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00034
Show More Cited By

Index Terms

Using sparse crossbars within LUT
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Integrated circuits
    1. Logic circuits
      1. Combinational circuits

Recommendations

Mapping into LUT structures
DATE '12: Proceedings of the Conference on Design, Automation and Test in Europe

Mapping into K-input lookup tables (K-LUTs) is an important step in synthesis for Field-Programmable Gate Arrays (FPGAs). The traditional FPGA architecture assumes all interconnects between individual LUTs are "routable". This paper proposes a modified ...
Placement-driven technology mapping for LUT-based FPGAs
FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays

In this paper, we study the problem of placement-driven technology mapping for table-lookup based FPGA architectures to optimize circuit performance. Early work on technology mapping for FPGAs such as Chortle-d[14] and Flowmap[3] aim to optimize the ...
Simultaneous depth and area minimization in LUT-based FPGA mapping
FPGA '95: Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays

In this paper, we present an improvement of the FlowMap algorithm, named CutMap, which combines depth and area minimization during the mapping process by computing min-cost min-height K-feasible cuts for critical nodes for depth minimization and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays

February 2001

200 pages

ISBN:1581133413

DOI:10.1145/360276

Chairman:
Scott Hauck
Univ. of Washington, Seattle
,
Editors:
Martine Schlag
Univ. of California, Santa Cruz
,
Russell Tessier
Univ. of Massachusetts, Amherst

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

Publication History

Published: 01 February 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPGA01

Sponsor:

SIGDA

FPGA01: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
629
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)2

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rostami Sani SYe A(2024)Evaluating the Impact of Using Multiple-Metal Layers on the Layout Area of Switch Blocks for Tile-Based FPGAs in FinFET 7nmACM Transactions on Reconfigurable Technology and Systems10.1145/363905517:1(1-29)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3639055
Shi KWang L(2024)An Open-Source Tool to Model and Explore Complex Routing Architecture for FPGA2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617494(734-739)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617494
Shi KZhou HWang L(2023)Explore the Feedback Interconnects in Intra-Cluster Routing for FPGAs2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00034(250-253)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00034
Shi KZhou HWang L(2023)VIB: A Versatile Interconnection Block for FPGA Routing Architecture2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00014(79-87)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00014
Mohaghegh ABetz V(2023)Tear Down The Wall: Unified and Efficient Intra-and Inter-Cluster Routing for FPGAs2023 33rd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL60245.2023.00026(130-136)Online publication date: 4-Sep-2023
https://doi.org/10.1109/FPL60245.2023.00026
Wang YShi KWang L(2023)An Enhanced Packing Algorithm for FPGA Architectures without Local Crossbar2023 IEEE 15th International Conference on ASIC (ASICON)10.1109/ASICON58565.2023.10396657(1-4)Online publication date: 24-Oct-2023
https://doi.org/10.1109/ASICON58565.2023.10396657
Shi KZhou XZhou HWang L(2022)An Optimized GIB Routing Architecture with Bent Wires for FPGAACM Transactions on Reconfigurable Technology and Systems10.1145/351959916:1(1-28)Online publication date: 22-Dec-2022
https://dl.acm.org/doi/10.1145/3519599
Zha YLi JAdler MIenne P(2022)Revisiting PathFinder Routing AlgorithmProceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3490422.3502356(24-34)Online publication date: 13-Feb-2022
https://dl.acm.org/doi/10.1145/3490422.3502356
Razzaq ASani SYe A(2022)The effect of gate voltage boosting on the power efficiency of multi-context FPGAsIntegration, the VLSI Journal10.1016/j.vlsi.2022.04.00786:C(30-43)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.vlsi.2022.04.007
Shen YQian JShi KWang LZhou H(2021)Two-level MUX Design and Exploration in FPGA Routing Architecture2021 31st International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL53798.2021.00045(234-241)Online publication date: Aug-2021
https://doi.org/10.1109/FPL53798.2021.00045
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Mapping into LUT structures

Placement-driven technology mapping for LUT-based FPGAs

Simultaneous depth and area minimization in LUT-based FPGA mapping