doi: 10.7873/DATE.2015.0713

Joint Affine Transformation and Loop Pipelining for Mapping Nested Loop on CGRAs

Shouyi Yin1, Dajiang Liu1, Leibo Liu1, Shaojun Wei1 and Yike Guo2

1Institute of Microelectronics, Tsinghua University, China

2Department of Computing, Imperial College, London, UK


Coarse-Grained Reconfigurable Architectures (CGRAs) are the promising architectures with high performance, high power- efficiency and attractions of flexibility. The computation-intensive portions of application, i.e. loops, are often implemented on CGRAs for acceleration. The loop pipelining techniques are usually used to exploit the parallelism of loops. However, for nested loops, the existing loop pipelining methods often result in poor hardware utilization and low execution performance. To tackle this problem, this paper makes two contributions: 1) a pipelining-beneficial affine transformation method which can optimize the initiation interval (II) of nested loop and enable multiple loop pipelines merging; 2) a multi-pipeline merging method which can improve hardware utilization further. The experimental results show that our approach can improve the performance of nested loop by up to 56% on average, as compared to the state-of-the-art techniques.

Keywords: Reconfigurable computing, CGRA, Loop pipelining, Affine transformation, Polyhedral model.

Full Text (PDF)