Premium
Fast parallel skew and prefix‐doubling suffix array construction on the GPU
Author(s) -
Wang Leyuan,
Baxter Sean,
Owens John D.
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3867
Subject(s) - computer science , speedup , suffix array , parallel computing , merge sort , merge algorithm , trie , skew , sort , prefix , parallel algorithm , suffix tree , data structure , suffix , lossless compression , massively parallel , algorithm , sorting algorithm , data compression , sorting , telecommunications , linguistics , philosophy , information retrieval , programming language
Summary Suffix arrays are fundamental full‐text index data structures of importance to a broad spectrum of applications in such fields as bioinformatics, Burrows–Wheeler transform‐based lossless data compression, and information retrieval. In this work, we propose and implement two massively parallel approaches on the graphics processing unit (GPU) based on two classes of suffix array construction algorithms. The first, parallel skew , makes algorithmic improvements to the previous work of Deo and Keely to achieve a speedup of 1.45x over their work. The second, a hybrid skew and prefix‐doubling implementation, is the first of its kind on the GPU and achieves a speedup of 2.3–4.4x over Osipov's prefix‐doubling and 2.4–7.9x over our skew implementation on large datasets. Our implementations rely on two efficient parallel primitives, a merge and a segmented sort. We theoretically analyze the two formulations of suffix array construction algorithms and show performance comparisons on a large variety of practical inputs. We conclude that, with the novel use of our efficient segmented sort, prefix‐doubling is more competitive than skew on the GPU. We also demonstrate the effectiveness of our methods in our implementations of the Burrows‐Wheeler transform and in a parallel full‐text, minute‐space‐index for pattern searching. Copyright © 2016 John Wiley & Sons, Ltd.