high performance computing on graphics processing units: hgpu.org

The longest common subsequence (LCS) for two given strings has various applications, such as for the comparison of deoxyribonucleic acid (DNA). In this thesis, we propose a graphics processing unit (GPU) algorithm to accelerate Hirschberg’s LCS algorithm improved with the bit-parallel algorithm by Crochemore et al. The algorithm by Crochemore et al. includes bitwise logical operators, which can be computed easily in parallel because they have bitwise parallelism. However, the algorithm by Crochemore et al. also includes an operator with less parallelism, i.e., an arithmetic sum. In this thesis, we focus on how to implement these operators efficiently in parallel and experimentally show the following results. First, the proposed GPU algorithm with a 2.67 GHz Intel Core i7 920 CPU and a GeForce GTX 580 GPU executes a maximum of 12.81 times faster than the bit-parallel CPU algorithm with a single-core of a 2.67 GHz Intel Xeon X5550 CPU. Next, the proposed GPU algorithm executes a maximum of 4.56 times faster than the bit-parallel CPU algorithm with all the four-cores of a 2.67 GHz Intel Xeon X5550 CPU. Finally, the proposed algorithm with a GeForce 8800 GTX executes a maximum of 18.1 times faster than the GPU algorithm proposed by Kloetzli et al. with the same GPU.