Recursive variable expansion: A transformation for reconfigurable computing

Recursive variable expansion: A transformation for reconfigurable computing

Nawaz, Z.N.

Sips, H.J. (promotor)

Electrical Engineering, Mathematics and Computer Science

Computer Engineering Laboratory

2011-01-11

Reconfigurable computing, in which general purpose processor (GPP) is augmented with one or more FPGAs, is increasingly used for high-performance computing where massive fine-grain parallelism and pipelining can be exploited. A challenge is to exploit such massive parallelism on FPGAs and more specifically how to map an application on the heterogeneous underlying platform. Similar to software compilers, hardware compilers can use loops to exploit such parallelism. The existence of a dependence between data is one the constraints that limits parallelism in a program. In this dissertation, we propose a transformation called Recursive Variable Expansion (RVE), which can be applied to an important category of loops. It removes all the data dependences by expanding the variable with its dependence expression until the expression becomes only a function of known variables. We classify two types of expressions, one which expands polynomially, and other which expands exponentially on the number of input variables. Irrespective of the type of expression, when we map an expression on an FPGA, the area (LUT) required on an FPGA is proportional to the number of terms in the expression. We present an automated pipeline design algorithm for the problems whose expression expands polynomially. This algorithm determines the largest pipeline size that fits the FPGA. Furthermore, the algorithm also ensures that the time to feed the data is less than the time to process an instruction through the pipeline. We apply this algorithm to DCT, a widely used signal processing kernel, which shows a comparable performance to the hand optimized implementation. The exponentially expanding version is applicable to the category of dynamic programming (DP) problems for which RVE is combined with dataflow. We demonstrated better performance than dataflow only, which is the best technique known so far for such problems. We generalize the approach by proposing a framework such that the technique can be applied to a large range of DP problems. Finally, we validate the proposed DP framework using the Smith-Waterman (SW) algorithm, which is a widely used, computation and data intensive application in bioinformatics. We show that our implementation yields a 2.29 x speedup at the cost of 2.82 x more area as compared to the conventional data?ow systolic array implementation. Moreover, we propose a parallel FPGA design for SW traceback stage, whose bandwidth requirement is also well within limits of the current off-the-shelf FPGA boards.

compiler optimization
high performance computing
reconfigurable computing
Smith-Waterman acceleration

http://resolver.tudelft.nl/uuid:29251f71-81ea-475c-8a3f-5795a6d1b341

9789072298119

Institutional Repository

doctoral thesis

(c) 2011 Nawaz, Z.N.