Affine Transformations for Communication and Reconfiguration Optimization of Mapping Loop Nests on CGRAs

Shouyi YIN  Dajiang LIU  Leibo LIU  Shaojun WEI  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.8   pp.1582-1591
Publication Date: 2013/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1582
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Design Methodology
reconfigurable computing,  loop transformation,  polyhedra model,  compiling,  

Full Text: PDF>>
Buy this Article

A coarse-grained reconfigurable architecture (CGRA) is typically hybrid architecture, which is composed of a reconfigurable processing unit (RPU) and a host microprocessor. Many computation-intensive kernels (e.g., loop nests) are often mapped onto RPUs to speed up the execution of programs. Thus, mapping optimization of loop nests is very important to improve the performance of CGRA. Processing element (PE) utilization rate, communication volume and reconfiguration cost are three crucial factors for the performance of RPUs. Loop transformations can affect these three performance influencing factors greatly, and would be of much significance when mapping loops onto RPUs. In this paper, a joint loop transformation approach for RPUs is proposed, where the PE utilization rate, communication cost and reconfiguration cost are under a joint consideration. Our approach could be integrated into compilers for CGRAs to improve the operating performance. Compared with the communication-minimal approach, experimental results show that our scheme can improve 5.8% and 13.6% of execution time on motion estimation (ME) and partial differential equation (PDE) solvers kernels, respectively. Also, run-time complexity is acceptable for the practical cases.