Coarse-grained reconfigurable architectures (CGRAs) can provide extremely energy-efficient acceleration for applications that are rich in arithmetic operations such as digital signal processing and multimedia applications. Since those applications are often naturally represented by stream graphs, it is very compelling to develop optimization strategies for stream graphs on CGRAs. One unique property of stream graphs is that they contain many kernels or loops, which creates both advantages and challenges when it comes to mapping them to CGRAs. This paper addresses two main problems with it, namely, many-buffer problem and control overhead problem, and presents our results of optimizing the execution of stream graphs for CGRAs including our low-cost architecture extensions. Our evaluation results demonstrate that our software and hardware optimizations can help generate highly efficient mapping of stream applications to CGRAs, with 3.4× speedup on average at the application level over CPU-only execution, which is significant.

Nested loops represent a significant portion of application runtime in multimedia and DSP applications, an important domain of applications for coarse-grained reconfigurable architectures (CGRAs). While conventional approaches to mapping nested loops utilize only a single-dimensional pipelining, which is either along the innermost loop or along an outer loop, in this paper, we explore an orthogonal approach of pipelining along multiple loop dimensions by first flattening the loop nest. To remedy the inevitable problem of repetitive outer-loop computation in flattened loops, we present a small set of special operations that can effectively reduce the number and frequency of micro-operations in the pipelined loop. We also present a loop transformation technique that can make our special operations applicable to a broader range of loops, including those with triangular iteration spaces. Our experimental results using imperfect loops from StreamIt benchmarks demonstrate that our special operations can cover a large portion of operations in flattened loops, improve performance of nested loops by nearly 30% over using loop flattening only, and achieve near-ideal executions on CGRAs for imperfect loops.

Coarse-Grained Reconfigurable Architectures (CGRAs), often used as coprocessors for DSP and multimedia kernels, can deliver highly energy-efficient execution for compute-intensive kernels. Simultaneously, stream applications, which consist of many actors and channels connecting them, can provide natural representations for DSP applications, and therefore be a good match for CGRAs. We present our results of mapping DSP applications written in StreamIt language to CGRAs, along with our mapping flow. One important challenge in mapping is how to manage the multitude of kernels in the application for the limited local memory of a CGRA, for which we present a novel integer linear programming-based solution. Our evaluation results demonstrate that our software and hardware optimizations can help generate highly efficient mapping of stream applications to CGRAs, enabling far more energy-efficient executions (7× worse to 50× better) compared to using state-of-the-art GP-GPUs.