research-article

SPR: an architecture-adaptive CGRA mapping tool

Authors:

Stephen Friedman,

Brian Van Essen,

Benjamin Ylvisaker,

Scott HauckAuthors Info & Claims

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

Pages 191 - 200

https://doi.org/10.1145/1508128.1508158

Published: 22 February 2009 Publication History

Abstract

In this paper we present SPR, a new architecture-adaptive mapping tool for use with Coarse-Grained Reconfigurable Architectures (CGRAs). It combines a VLIW style scheduler and FPGA style placement and pipelined routing algorithms with novel mechanisms for integrating and adapting the algorithms to CGRAs. We introduce a latency padding technique that provides feedback from the placer to the scheduler to meet the constraints of a fixed frequency device with configurable interconnect. Using a new dynamic clustering method during placement, we achieved a 1.3x improvement in throughput of mapped designs. Finally, we introduce an enhancement to the PathFinder algorithm for targeting architectures with a mix of dynamically multiplexed and statically configurable interconnects. The enhanced algorithm is able to successfully share statically configured interconnect in a time-multiplexed way, achieving an average channel width reduction of .5x compared to non-shared static interconnect.

References

[1]

Electric VLSI Design System. Sun Microsystems and Static Free Software. http://www.staticfreesoft.com/.

[2]

Mosaic Research Group. http://www.cs.washington.edu/research/lis/mosaic/.

[3]

V. Betz and J. Rose. VPR: A New Packing, Placement and Routing Tool for FPGA Research. In International Workshop on Field-Programmable Logic and Applications, 1997.

Digital Library

[4]

A. Carroll and C. Ebeling. Reducing the Space Complexity of Pipelined Routing Using Modified Range Encoding. In International Conference on Field-Programmable Logic and Applications, 2006.

[5]

A. Carroll, S. Friedman, B. Van Essen, A. Wood, B. Ylvisaker, C. Ebeling, and S. Hauck. Designing a Coarse-grained Reconfigurable Architecture for Power Efficiency. Technical report, Department of Energy NA-22 University Information Technical Interchange Review Meeting, 2007.

[6]

C. Ebeling, D. C. Cronquist, and P. Franklin. RaPiD -- Reconfigurable Pipelined Datapath. In International Workshop on Field-Programmable Logic and Applications, pages 126--135, 1996.

Digital Library

[7]

K. Eguro and S. Hauck. Armada: Timing-driven Pipeline-aware Routing for FPGAs. In ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pages 169--178, 2006.

Digital Library

[8]

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220:671--680, 1983.

[9]

J.-e. Lee, K. Choi, and N. Dutt. Compilation Approach for Coarse-grained Reconfigurable Architectures. IEEE Design & Test of Computers, 20(1):26--33, 2003.

Digital Library

[10]

S. Li and C. Ebeling. QuickRoute: A Fast Routing Algorithm for Pipelined Architectures. In IEEE International Conference on Field-Programmable Technology, pages 73--80, 2004.

[11]

L. McMurchie and C. Ebeling. PathFinder: A Negotiation-based Performance-driven Router for FPGAs. In ACM International Symposium on Field-Programmable Gate Arrays, pages 111--117, 1995.

Digital Library

[12]

B. Mei, S. Vernalde, D. Verkest, H. De Man, and R. Lauwereins. DRESC: A Retargetable Compiler for Coarse-grained Reconfigurable Architectures. In IEEE International Conference on Field-Programmable Technology, pages 166--173, 2002.

[13]

B. Mei, S. Vernalde, D. Verkest, H. De Man, and R. Lauwereins. ADRES: An Architecture with Tightly Coupled VLIW Processor and Coarse-Grained Reconfigurable Matrix. In International Conference on Field-Programmable Logic and Applications, volume 2778, pages 61--70, 2003.

[14]

E. Mirsky and A. DeHon. MATRIX: a reconfigurable computing architecture with configurable instruction distribution and deployable resources. In IEEE Symposium on Field-Programmable Custom Computing Machines, pages 157--166, 1996.

[15]

M. Mishra and S. C. Goldstein. Virtualization on the Tartan Reconfigurable Architecture. In International Conference on Field-Programmable Logic and Applications, pages 323--330, 2007.

[16]

B. R. Rau. Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops. In International Symposium on Microarchitecture, pages 63--74, 1994

Digital Library

[17]

A. Sharma, S. Hauck, and C. Ebeling. Architecture-adaptive Routability-driven Placement for FPGAs. In International Conference on Field-Programmable Logic and Applications, pages 427--432, 2005.

[18]

H. Singh, M.-H. Lee, G. Lu, F. Kurdahi, N. Bagherzadeh, and E. Chaves Filho. MorphoSys: An Integrated Reconfigurable System for Data-parallel and Computation-Intensive Applications. IEEE Transactions on Computers, 49(5):465--481, 2000.

Digital Library

[19]

W. Tsu, K. Macy, A. Joshi, R. Huang, N. Walker, T. Tung, O. Rowhani, V. George, J. Wawrzynek, and A. DeHon. HSRA: High-speed, Hierarchical Synchronous Reconfigurable Array. In ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pages 125--134, 1999.

Digital Library

[20]

S. J. Wilton. Architecture and Algorithms for Field-Programmable Gate Arrays with Embedded Memory. PhD thesis, University of Toronto, 1997.

Digital Library

Cited By

Wei HBhilare OWaqar HAnderson J(2024)CAD Techniques for NoC-Connected Multi-CGRA Systems14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies (HEART'24))10.1145/3665283.3665297(109-118)Online publication date: 19-Jun-2024
https://doi.org/10.1145/3665283.3665297
Tirelli CSapriza JRodríguez Álvarez RFerretti LDenkinger BAnsaloni GMiranda Calero JAtienza DPozzi L(2024)SAT-Based Exact Modulo Scheduling Mapping for Resource-Constrained CGRAsACM Journal on Emerging Technologies in Computing Systems10.1145/366367520:3(1-26)Online publication date: 22-May-2024
https://dl.acm.org/doi/10.1145/3663675
de Bruin BVadivel KWijtvliet MJääskeläinen PCorporaal H(2024)R-Blocks: an Energy-Efficient, Flexible, and Programmable CGRAACM Transactions on Reconfigurable Technology and Systems10.1145/365664217:2(1-34)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3656642
Show More Cited By

Index Terms

SPR: an architecture-adaptive CGRA mapping tool
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers

Recommendations

Seeing the forest and the trees: Steiner wirelength optimization in placemen
ISPD '06: Proceedings of the 2006 international symposium on Physical design

We show how to optimize Steiner-tree Wirelength (StWL) in global and detail placement without a significant runtime penalty, making the use of Half-Perimeter Wirelength unnecessary. Given that StWL correlates with Routed Wirelength (rWL) much better ...
IPR: an integrated placement and routing algorithm
DAC '07: Proceedings of the 44th annual Design Automation Conference

In nanometer-scale VLSI technologies, several interconnect issues like routing congestion and interconnect delay have become the main concerns in placement. However, all previous placement approaches optimize some very primitive interconnect models ...
An FPGA-based heterogeneous coarse-grained dynamically reconfigurable architecture
CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

Coarse-grained reconfigurable architecture has emerged as a promising model for embedded systems as a solution to reduce the complexity of FPGA synthesis and mapping steps, consequently reducing reconfiguration time. Despite these advantages, CGRA usage ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

February 2009

302 pages

ISBN:9781605584102

DOI:10.1145/1508128

General Chair:
Paul Chow
University of Toronto, Canada
,
Program Chair:
Peter Cheung
Imperial College London, UK

Copyright © 2009 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: 22 February 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FPGA '09

Sponsor:

FPGA '09: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

February 22 - 24, 2009

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

123
Total Citations
View Citations
914
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)11

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wei HBhilare OWaqar HAnderson J(2024)CAD Techniques for NoC-Connected Multi-CGRA Systems14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies (HEART'24))10.1145/3665283.3665297(109-118)Online publication date: 19-Jun-2024
https://doi.org/10.1145/3665283.3665297
Tirelli CSapriza JRodríguez Álvarez RFerretti LDenkinger BAnsaloni GMiranda Calero JAtienza DPozzi L(2024)SAT-Based Exact Modulo Scheduling Mapping for Resource-Constrained CGRAsACM Journal on Emerging Technologies in Computing Systems10.1145/366367520:3(1-26)Online publication date: 22-May-2024
https://dl.acm.org/doi/10.1145/3663675
de Bruin BVadivel KWijtvliet MJääskeläinen PCorporaal H(2024)R-Blocks: an Energy-Efficient, Flexible, and Programmable CGRAACM Transactions on Reconfigurable Technology and Systems10.1145/365664217:2(1-34)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3656642
Dai YLi JZhu QQiu YHu YYin WWang L(2024)HETA: A Heterogeneous Temporal CGRA Modeling and Design Space Exploration via Bayesian OptimizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.334453632:3(505-518)Online publication date: Mar-2024
https://doi.org/10.1109/TVLSI.2023.3344536
Li JYan YLi JSun SJin BYin WWang L(2024)An Architecture-Agnostic Dataflow Mapping Framework on CGRA2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00121(618-625)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00121
Del Sozzo EWang XAdhi BCortes CAnderson JSano K(2024)Exploration of Trade-offs Between General-Purpose and Specialized Processing Elements in HPC-Oriented CGRA2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00065(668-680)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00065
Liu DXia YShang JZhong JOuyang PYin S(2024)E2EMap: End-to-End Reinforcement Learning for CGRA Compilation via Reverse Mapping2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00015(46-60)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00015
Beidas RAnderson J(2024)Mapping Enumeration for Multi-Context CGRAs Using Zero-Suppressed Binary Decision Diagrams2024 IEEE 32nd Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM60383.2024.00026(151-161)Online publication date: 5-May-2024
https://doi.org/10.1109/FCCM60383.2024.00026
Pudi DMalviya SBoppu SYang YHemani ACenkeramaddi L(2024)Integer Linear Programming-Based Simultaneous Scheduling and Binding for SiLago FrameworkIEEE Access10.1109/ACCESS.2024.345350312(124081-124094)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3453503
Pudi DTiwari UBoppu SYang YHemani A(2024)Automating functional unit and register binding for synchoros CGRA platformDesign Automation for Embedded Systems10.1007/s10617-024-09286-y28:2(155-186)Online publication date: 12-Jun-2024
https://doi.org/10.1007/s10617-024-09286-y
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten