Parallel DC3 algorithm for suffix array construction on many-core accelerators
Pages 1155 - 1158
Abstract
In bioinformatics applications, suffix arrays are widely used to DNA sequence alignments in the initial exact match phase of heuristic algorithms. With the exponential growth and availability of data, using many-core accelerators, like GPUs, to optimize existing algorithms is very common. We present a new implementation of suffix array on GPU. As a result, suffix array construction on GPU achieves around 10x speedup on standard large data sets, which contain more than 100 million characters. The idea is simple, fast and scalable that can be easily scale to multi-core processors and even heterogeneous architectures.
References
[1]
T. F. Smith and M. S. Waterman, "Identification of common molecular subsequences," Journal of molecular biology, vol. 147, no. 1, pp. 195--197, 1981.
[2]
A. L. Delcher, S. L. Salzberg, and A. M. Phillippy, "Using mummer to identify similar regions in large sequence sets," Current Protocols in Bioinformatics, pp. 10--3, 2003.
[3]
M. Schatz, C. Trapnell, A. Delcher, and A. Varshney, "High-throughput sequence alignment using graphics processing units," BMC bioinformatics, vol. 8, no. 1, p. 474, 2007.
[4]
M. Deo and S. Keely, "Parallel suffix array and least common prefix for the gpu," in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP '13. New York, NY, USA: ACM, 2013, pp. 197--206. {Online}. Available
[5]
E. Ukkonen, "On-line construction of suffix trees," Algorithmica, vol. 14, pp. 249--260, 1995. {Online}. Available
[6]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 2009.
[7]
J. Kärkkäinen, P. Sanders, and S. Burkhardt, "Linear work suffix array construction," Journal of the ACM(JACM), vol. 53, no. 6, pp. 918--936, 2006.
[8]
E. Sintorn and U. Assarsson, "Fast parallel gpu-sorting using a hybrid algorithm," J. Parallel Distrib. Comput., vol. 68, no. 10, pp. 1381--1388, Oct. 2008. {Online}. Available
[9]
G. E. Blelloch, "Prefix sums and their applications," 1990.
[10]
M. Harris, S. Sengupta, and J. D. Owens, "Parallel prefix sum (scan) with cuda," GPU gems, vol. 3, no. 39, pp. 851--876, 2007.
[11]
1000 genomes, a deep catalog of human genetic variation. {Online}. Available: http://www.1000genomes.org/
[12]
J. Shun, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, A. Kyrola, H. V. Simhadri, and K. Tangwongsan, "Brief announcement: the problem based benchmark suite," in Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures. ACM, 2012, pp. 68--70.
- Parallel DC3 algorithm for suffix array construction on many-core accelerators
Recommendations
Parallel suffix array and least common prefix for the GPU
PPoPP '13Suffix 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 ...
Vectorizing Unstructured Mesh Computations for Many-core Architectures
PMAM'14: Proceedings of Programming Models and Applications on Multicores and ManycoresAchieving optimal performance on the latest multi-core and many-core architectures depends more and more on making efficient use of the hardware's vector processing capabilities. While auto-vectorizing compilers do not require the use of vector ...
Vectorizing Unstructured Mesh Computations for Many-core Architectures
PMAM'14: Proceedings of Programming Models and Applications on Multicores and ManycoresAchieving optimal performance on the latest multi-core and many-core architectures depends more and more on making efficient use of the hardware's vector processing capabilities. While auto-vectorizing compilers do not require the use of vector ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IEEE Press
Publication History
Published: 04 May 2015
Check for updates
Qualifiers
- Research-article
Conference
CCGrid '15
CCGrid '15: 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing
May 4 - 7, 2015
Shenzhen, China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 17Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in