EPIMap: Using epimorphism to map applications on CGRAs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

113 Scopus citations


Coarse-Grained Reconfigurable Architectures (CGRAs) are an attractive platform that promise simultaneous high-performance and high power-efficiency. One of the primary challenges in using CGRAs is to develop efficient compilers that can automatically and efficiently map applications to the CGRA. To this end, this paper makes several contributions: i) Using Re-computation for Resource Limitations: For the first time in CGRA compilers, we propose the use of re-computation as a solution for resource limitation problem. This extends the solutions space, and enables better mappings, ii) General Problem Formulation: A precise and general formulation of the application mapping problem on a CGRA is presented, and its computational complexity is established. iii) Extracting an Efficient Heuristic: Using the insights from the problem formulation, we design an effective global heuristic called EPIMap. EPIMap transforms the input specification (a directed graph) to an Epimorphic equivalent graph that satisfies the necessary conditions for mapping on to a CGRA, reducing the search space. Experimental results on 14 important kernels extracted from well known benchmark programs show that using EPIMap can improve the performance of the kernels on CGRA by more than 2.8X on average, as compared to one of the best existing mapping algorithm, EMS. EPIMap was able to achieve the theoretical best performance for 9 out of 14 benchmarks, while EMS could not achieve the theoretical best performance for any of the benchmarks. EPIMap achieves better mappings at acceptable increase in the compilation time.

Original languageEnglish (US)
Title of host publicationProceedings of the 49th Annual Design Automation Conference, DAC '12
Number of pages8
StatePublished - Jul 11 2012
Event49th Annual Design Automation Conference, DAC '12 - San Francisco, CA, United States
Duration: Jun 3 2012Jun 7 2012

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Other49th Annual Design Automation Conference, DAC '12
Country/TerritoryUnited States
CitySan Francisco, CA


  • coarse-grained reconfigurable architectures
  • compilation
  • modulo scheduling

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation


Dive into the research topics of 'EPIMap: Using epimorphism to map applications on CGRAs'. Together they form a unique fingerprint.

Cite this