Mapping Multi-Level Loop Nests onto CGRAs Using Polyhedral Optimizations

Dajiang LIU  Shouyi YIN  Leibo LIU  Shaojun WEI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.7   pp.1419-1430
Publication Date: 2015/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.1419
Type of Manuscript: Special Section PAPER (Special Section on Design Methodologies for System on a Chip)
Category: 
Keyword: 
coarse-grained reconfigurable architecture,  loops,  polyhedral model,  mapping,  

Full Text: PDF>>
Buy this Article




Summary: 
The coarse-grained reconfigurable architecture (CGRA) is a promising computing platform that provides both high performance and high power-efficiency. The computation-intensive portions of an application (e.g. loop nests) are often mapped onto CGRA for acceleration. However, mapping loop nests onto CGRA efficiently is quite a challenge due to the special characteristics of CGRA. To optimize the mapping of loop nests onto CGRA, this paper makes three contributions: i) Establishing a precise performance model of mapping loop nests onto CGRA, ii) Formulating the loop nests mapping as a nonlinear optimization problem based on polyhedral model, iii) Extracting an efficient heuristic algorithm and building a complete flow of mapping loop nests onto CGRA (PolyMAP). Experiment results on most kernels of the PolyBench and real-life applications show that our proposed approach can improve the performance of the kernels by 27% on average, as compared to the state-of-the-art methods. The runtime complexity of our approach is also acceptable.