Font Size: a A A

Fast Parallel Suffix Array on the GPU

Posted on:2016-02-05Degree:M.SType:Thesis
University:University of California, DavisCandidate:Wang, LeyuanFull Text:PDF
GTID:2478390017481142Subject:Computer Science
Abstract/Summary:
In this thesis, we implement two classes of suffix array construction algorithms on the GPU. The first, 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 also demonstrate the effectiveness of our implementations in a Burrows-Wheeler transform and a parallel FM index for pattern searching.
Keywords/Search Tags:Parallel
Related items