A GPU Implementation of a Bit-parallel Algorithm for Computing the Longest Common Subsequence
A GPU Implementation of a Bit-parallel Algorithm for Computing the Longest Common Subsequence
复制标题
DOI：
10.2197/ipsjtrans.7.139
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Katsuya Kawanami;N. Fujimoto
中科院分区：
文献类型：
--
作者：
Katsuya Kawanami;N. Fujimoto
：两个给定字符串的最长公共子序列 (LCS) 有多种应用，例如用于比较脱氧核糖核酸 (DNA)。在本文中，我们提出了一种图形处理单元（GPU）算法来加速 Hirschberg 的 LCS 算法，并使用 Crochemore 等人的位并行算法进行了改进。 Crochemore 等人的算法包括按位逻辑运算符，由于它们具有按位并行性，因此可以轻松并行计算。然而，Crochemore 等人的算法还包括一个并行性较低的运算符，即算术和。在本文中，我们重点关注如何并行高效地实现这些算子，并通过实验展示了以下结果。首先，所提出的使用 2.67GHz Intel Core i7 920 CPU 和 GeForce GTX 580 GPU 的 GPU 算法的执行速度比使用单核 2.67GHz Intel Xeon X5550 CPU 的位并行 CPU 算法最多快 12.81 倍。随后，所提出的 GPU 算法的执行速度比使用四核 2.67GHz Intel Xeon X5550 CPU 的位并行 CPU 算法最多快 4.56 倍。此外，所提出的使用 GeForce 8800 GTX 的算法的执行速度比 Kloetzli 等人使用相同 GPU 的现有 GPU 算法快 10.9 至 18.1 倍。
: The longest common subsequence (LCS) for two given strings has various applications, such as for the comparison of deoxyribonucleic acid (DNA). In this paper, we propose a graphics processing unit (GPU) algorithm to accelerate Hirschberg’s LCS algorithm improved with Crochemore et al.’s bit-parallel algorithm. Crochemore et al.’s algorithm includes bitwise logical operators, which can be computed easily in parallel because they have bitwise parallelism. However, Crochemore et al.’s algorithm also includes an operator with less parallelism, i.e., an arithmetic sum. In this paper, we focus on how to implement these operators e ffi ciently in parallel and experimentally show the following results. First, the proposed GPU algorithm with a 2.67GHz Intel Core i7 920 CPU and GeForce GTX 580 GPU performs a maximum of 12.81 times faster than the bit-parallel CPU algorithm using a single-core 2.67GHz Intel Xeon X5550 CPU. Subsequently, the proposed GPU algorithm executes a maximum of 4.56 times faster than the bit-parallel CPU algorithm using a four-core 2.67GHz Intel Xeon X5550 CPU. Furthermore, the proposed algorithm with GeForce 8800 GTX performs 10.9 to 18.1 times faster than Kloetzli et al.’s existing GPU algorithm with the same GPU.