More Web Proxy on the site http://driver.im/

research-article

Recurrence cycle aware modulo scheduling for coarse-grained reconfigurable architectures

Authors:

Bernhard Egger,

Scott MahlkeAuthors Info & Claims

LCTES '09: Proceedings of the 2009 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

Pages 21 - 30

https://doi.org/10.1145/1542452.1542456

Published: 19 June 2009 Publication History

Abstract

In high-end embedded systems, coarse-grained reconfigurable architectures (CGRA) continue to replace traditional ASIC designs. CGRAs offer high performance at a low power consumption, yet provide flexibility through programmability. In this paper we introduce a recurrence cycle-aware scheduling technique for CGRAs. Our modulo scheduler groups operations belonging to a recurrence cycle into a clustered node and then computes a scheduling order for those clustered nodes. Deadlocks that arise when two or more recurrence cycles depend on each other are resolved by using heuristics that favor recurrence cycles with long recurrence delays. While with previous work one had to sacrifice either a fast compilation speed in order to get good quality results, or vice versa, this is not necessary anymore with the proposed recurrence cycle-aware scheduling technique. We have implemented the proposed method into our in-house CGRA chip and compiler solution and show that the technique achieves better quality schedules than schedulers based on simulated annealing at a 170-fold speed increase.

References

[1]

M. Ahn, J. W. Yoon, Y. Paek, Y. Kim, M. Kiemb, and K. Choi. A spatial mapping algorithm for heterogeneous coarse-grained reconfigurable architectures. In DATE '06: Proceedings of the conference on Design, automation and test in Europe, pages 363--368, 3001 Leuven, Belgium, Belgium, 2006. European Design and Automation Association.

Digital Library

[2]

N. Bansal, S. Gupta, N. Dutt, A. Nicolau, and R. Gupta. Interconnectaware mapping of applications to coarse-grain reconfigurable architectures. Lecture Notes in Computer Science, 3203:891--899, 2004.

[3]

J. C. Dehnert and R. A. Towle. Compiling for the cydra 5. The Journal of Supercomputing, 7(1--2):181--227, 1993.

Digital Library

[4]

C. Ebeling, D. C. Cronquist, P. Franklin, J. Secosky, and S. G. Berg. Mapping applications to the rapid configurable architecture. In FCCM'97: Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, page 106, Washington, DC, USA, 1997. IEEE Computer Society.

Digital Library

[5]

S. Goldstein, H. Schmit, M. Moe, M. Bidu, S. Cadambi, R. Taylor, and R. Laufer. Piperench: a coprocessor for streaming multimedia acceleration. In Proceedings of the 26th International Symposium on Computer Architecture, pages 28--39, Washington, DC, USA, 1999. IEEE Computer Society.

Digital Library

[6]

R. Hartenstein. A decade of reconfigurable computing: a visionary retrospective. In DATE '01: Proceedings of the conference on Design, Automation and Test in Europe, pages 642--649, Washington, DC, USA, 2001. IEEE Computer Society.

Digital Library

[7]

A. Hatanaka and N. Bagherzadeh. A modulo scheduling algorithm for a coarse-grain reconfigurable array template. In Parallel and Distributed Processing Symposium, pages 1--8, Washington, DC, USA, 2007. IEEE Computer Society.

[8]

J.-e. Lee, K. Choi, and N. D. Dutt. Compilation approach for coarsegrained reconfigurable architectures. IEEE Design & Test of Computers, 20(1):26--33, 2003.

Digital Library

[9]

J. Llosa. Swing modulo scheduling: A lifetime-sensitive approach. In PACT '96: Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, page 80, Washington, DC, USA, 1996. IEEE Computer Society.

Digital Library

[10]

G. Lu, H. Singh, M.-H. Lee, N. Bagherzadeh, F. J. Kurdahi, and E. M. C. Filho. The morphosys parallel reconfigurable system. In Euro-Par '99: Proceedings of the 5th International Euro-Par Conference on Parallel Processing, pages 727--734, London, UK, 1999. Springer-Verlag.

Digital Library

[11]

B. Mei, S. Vernalde, D. Verkest, H. De Man, and R. Lauwereins. Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling. In DATE '03: Proceedings of the conference on Design, Automation and Test in Europe, page 10296, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[12]

B. Mei, S. Vernalde, D. Verkest, and R. Lauwereins. Design methodology for a tightly coupled vliw/reconfigurable matrix architecture: A case study. In DATE '04: Proceedings of the conference on Design, automation and test in Europe, page 21224, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[13]

H. Park, K. Fan, M. Kudlur, and S. Mahlke. Modulo graph embedding: mapping applications onto coarse-grained reconfigurable architectures. In CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, pages 136--146, New York, NY, USA, 2006. ACM.

Digital Library

[14]

H. Park, K. Fan, S. A. Mahlke, T. Oh, H. Kim, and H.-s. Kim. Edgecentric modulo scheduling for coarse-grained reconfigurable architectures. In PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques, pages 166--176, New York, NY, USA, 2008. ACM.

Digital Library

[15]

B. R. Rau. Iterative modulo scheduling: an algorithm for software pipelining loops. In MICRO 27: Proceedings of the 27th annual international symposium on Microarchitecture, pages 63--74, New York, NY, USA, 1994. ACM.

Digital Library

[16]

J.W. Yoon, A. Shrivastava, S. Park, M. Ahn, R. Jeyapaul, and Y. Paek. Spkm: a novel graph drawing based algorithm for application mapping onto coarse-grained reconfigurable architectures. In ASP-DAC '08: Proceedings of the 2008 conference on Asia and South Pacific design automation, pages 776--782, Los Alamitos, CA, USA, 2008. IEEE Computer Society Press.

Digital Library

Cited By

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
Tirelli CFerretti LPozzi L(2023)SAT-MapIt: A SAT-based Modulo Scheduling Mapper for Coarse Grain Reconfigurable Architectures2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137123(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137123
Balasubramanian MShrivastava ABolchini CO'Connor IVerbauwhede IWille R(2022)PathSeekerProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3539913(268-273)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3539913
Show More Cited By

Index Terms

Recurrence cycle aware modulo scheduling for coarse-grained reconfigurable architectures
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers
      2. Source code generation

Recommendations

Edge-centric modulo scheduling for coarse-grained reconfigurable architectures
PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques

Coarse-grained reconfigurable architectures (CGRAs) present an appealing hardware platform by providing the potential for high computation throughput, scalability, low cost, and energy efficiency. CGRAs consist of an array of function units and register ...
Recurrence cycle aware modulo scheduling for coarse-grained reconfigurable architectures
LCTES '09

In high-end embedded systems, coarse-grained reconfigurable architectures (CGRA) continue to replace traditional ASIC designs. CGRAs offer high performance at a low power consumption, yet provide flexibility through programmability. In this paper we ...
Compiling custom instructions onto expression-grained reconfigurable architectures
CASES '08: Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems

While customizable processors aim at combining the flexibility of general purpose processors with the speed and power advantages of custom circuits, commercially available processors are often limited by the inability to reconfigure the application-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '09: Proceedings of the 2009 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

June 2009

188 pages

ISBN:9781605583563

DOI:10.1145/1542452

General Chair:
Christoph Kirsch
University of Salzburg, Austria
,
Program Chair:
Mahmut Kandemir
Pennsylvania State University, USA

ACM SIGPLAN Notices Volume 44, Issue 7
LCTES '09
July 2009
176 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1543136
Issue’s Table of Contents

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: 19 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '09

Sponsor:

LCTES '09: ACM SIGPLAN/SIGBED 2009 Conference on Languages, Compilers, and Tools for Embedded Systems

June 19 - 20, 2009

Dublin, Ireland

Acceptance Rates

LCTES '09 Paper Acceptance Rate 18 of 81 submissions, 22%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
631
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Tirelli CFerretti LPozzi L(2023)SAT-MapIt: A SAT-based Modulo Scheduling Mapper for Coarse Grain Reconfigurable Architectures2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137123(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137123
Balasubramanian MShrivastava ABolchini CO'Connor IVerbauwhede IWille R(2022)PathSeekerProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3539913(268-273)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3539913
Zhao ZSheng WLi JYe PWang QMao Z(2021)Similarity-Aware Architecture/Compiler Co-Designed Context-Reduction Framework for Modulo-Scheduled CGRAElectronics10.3390/electronics1018221010:18(2210)Online publication date: 9-Sep-2021
https://doi.org/10.3390/electronics10182210
Torng CPan POu YTan CBatten C(2021)Ultra-Elastic CGRAs for Irregular Loop Specialization2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA51647.2021.00042(412-425)Online publication date: Feb-2021
https://doi.org/10.1109/HPCA51647.2021.00042
Kim CJeong SCho SLee YSong WKim YKim H(2021)Thread-Aware Area-Efficient High-Level Synthesis Compiler for Embedded Devices2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO51591.2021.9370341(327-339)Online publication date: 27-Feb-2021
https://doi.org/10.1109/CGO51591.2021.9370341
Egger BSong ELee HShin D(2019)Random test program generation for verification and validation of the Samsung Reconfigurable ProcessorJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2019.05.00797:C(219-238)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1016/j.sysarc.2019.05.007
Egger BSong ELee HShin D(2018)Verification of coarse-grained reconfigurable arrays through random test programsACM SIGPLAN Notices10.1145/3299710.321134253:6(76-88)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3299710.3211342
Egger BSong ELee HShin DZhang ZDubach C(2018)Verification of coarse-grained reconfigurable arrays through random test programsProceedings of the 19th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3211332.3211342(76-88)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3211332.3211342
Dave SBalasubramanian MShrivastava A(2018)RAMPProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196101(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196101
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.

Media

Figures

Other

Tables

View Table of Contents