Parallel suffix array and least common prefix for the GPU
Parallel suffix array and least common prefix for the GPU
复制标题
GPU 的并行后缀数组和最不常见前缀
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Keely
中科院分区：
文献类型：
--
作者：
Mrinal Deo;S. Keely
后缀数组（SA）是将字符串的后缀按字典顺序排序形成的数据结构。 SA 已用于各种应用中，尤其是在模式匹配和基于 Burrows-Wheeler 变换 (BWT) 的无损数据压缩中。 SA 也已成为许多（如果不是全部）字符串处理问题的首选数据结构，后缀树方法适用于这些问题。在过去的二十年里，研究人员提出了许多后缀数组构造算法（SACA）。我们对 SACA 的主要类别进行了系统研究，旨在将它们映射到 GPU 等数据并行架构上。我们得出的结论是，倾斜算法 [12]（一种线性时间递归算法）是 GPU 的最佳候选算法，因为它的所有阶段都可以有效地映射到数据并行硬件。与使用独立 GPU 和 APU 的单线程 CPU 实现相比，我们的 OpenCL 倾斜算法实现的吞吐量高达 25 MStrings/秒，加速分别高达 34 倍和 5.8 倍。我们还将我们的 OpenCL 实现与基于诱导复制的已知最快 CPU 实现进行了比较，并实现了高达 3.7 倍的加速。使用 SA，我们在 GPU 上构建 BWT，并且比 GPU 上已知最快的 BWT 实现了 11 倍的加速。
后缀数组通常会使用最长公共前缀 (LCP) 信息进行扩充。我们设计了一种新颖的高性能并行算法，用于在 GPU 上计算 LCP。我们的 LCP 的 GPU 实现在独立 GPU 和 APU 上分别实现了高达 25 倍和 4.3 倍的加速。
Suffix Array (SA) is a data structure formed by sorting the suffixes of a string into lexicographic order. SAs have been used in a variety of applications, most notably in pattern matching and Burrows-Wheeler Transform (BWT) based lossless data compression. SAs have also become the data structure of choice for many, if not all, string processing problems to which suffix tree methodology is applicable. Over the last two decades researchers have proposed many suffix array construction algorithm (SACAs). We do a systematic study of the main classes of SACAs with the intent of mapping them onto a data parallel architecture like the GPU. We conclude that skew algorithm [12], a linear time recursive algorithm, is the best candidate for GPUs as all its phases can be efficiently mapped to a data parallel hardware. Our OpenCL implementation of skew algorithm achieves a throughput of up to 25 MStrings/sec and a speedup of up to 34x and 5.8x over a single threaded CPU implementation using a discrete GPU and APU respectively. We also compare our OpenCL implementation against the fastest known CPU implementation based on induced copying and achieve a speedup of up to 3.7x. Using SA we construct BWT on GPU and achieve a speedup of 11x over the fastest known BWT on GPU.
Suffix arrays are often augmented with the longest common prefix (LCP) information. We design a novel high-performance parallel algorithm for computing LCP on the GPU. Our GPU implementation of LCP achieves a speedup of up to 25x and 4.3x on discrete GPU and APU respectively.