Accelerating DNA sequence alignment based on smith waterman algorithm using recursive variable expansion / Muhamad Faiz Ismail

Reconfigurable computing, in which general purpose processor (GPP) is increasingly used for high performance computing where massive fine-grain parallelism can be exploited. A challenge is to exploit such massive parallelism on LabVIEW and more specifically how to map an application on the heterogeneous underlying platform. Similar to hardware compilers, software 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 LabVIEW, the area (LUT) required is proportional to the number of terms in the expression. 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 two times speedup at the cost of almost three times more area as compared to the conventional dataflow traditional array implementation.