K-loops: Loop Transformations for Reconfigurable Architectures

K-loops: Loop Transformations for Reconfigurable Architectures

Dragomir, O.S.

Sips, H.J. (promotor)
Bertels, K.L.M. (promotor)

Electrical Engineering, Mathematics and Computer Science

Microelectronics & Computer Engineering

2011-06-16

The focus of this dissertation is on kernel loops (K-loops), which are loop nests that contain hardware mapped kernels in the loop body. In this thesis, we propose methods for improving the performance of such K-loops, by using standard loop transformations for exposing and exploiting the coarse grain loop level parallelism. We target a reconfigurable architecture that is a heterogeneous system consisting of a general purpose processor and a field programmable gate array (FPGA). Research projects targeting reconfigurable architectures are trying to give answers to several problems: how to partition the application -- decide which parts to be accelerated on the FPGA, how to optimize these parts (the kernels), what is the performance gain. However, only few try to exploit the coarse grain loop level parallelism. This work goes towards automatically deciding the number of kernel instances to place into the reconfigurable hardware, in a flexible way that can balance between area and performance. In this dissertation, we propose a general framework that helps determine the optimal degree of parallelism for each hardware mapped kernel within a K-loop, taking into account area, memory size and bandwidth, and performance considerations. In the future it can also take into account power. Furthermore, we present algorithms and mathematical models for several loop transformations in the context of K-loops. The algorithms are used to determine the best degree of parallelism for a given K-loop, while the mathematical models are used to determine the corresponding performance improvement. The algorithms are validated with experimental results. The loop transformations that we analyze in this thesis are loop unrolling, loop shifting, K-pipelining, loop distribution, and loop skewing. An algorithm that decides which transformations to use for a given K-loop is also provided. Finally, we also present an analysis of possible situations and justifications of when and why the loop transformations have or have not a significant impact on the K-loop performance.

compiler optimizations
loop transformations
reconfigurable computing
K-loops

http://resolver.tudelft.nl/uuid:da1e4bbb-ce28-42d3-ae2b-f076ccc7ee91

Wohrmann Print Service

9789072298003

Institutional Repository

doctoral thesis

(c) 2011 Dragomir, O.S.