Coarse-Grained Reconfigurable Architectures (CGRAs) are an at- tractive 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 limita- tion problem. This extends the solutions space, and enables better mappings, ii) General Problem Formulation: A precise and gen- eral formulation of the application mapping problem on a CGRA is presented, and its computational complexity is established. iii) Ex- tracting 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. Experi- mental results on 14 important kernels extracted from well known benchmark programs show that using EPIMap can improve the per- formance 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 theoreti- cal best performance for any of the benchmarks. EPIMap achieves better mappings at acceptable increase in the compilation time.
