Fast longest common subsequence with general integer scoring support on GPUs. Ozsoy, A., Chauhan, A., & Swany, M. In Proceedings of the 2014 International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2014, 2014.
abstract   bibtex   
Graphic Processing Units (GPUs) have been gaining popularity among high-performance users. Certain classes of algorithms benefit greatly from the massive parallelism of GPUs. One such class of algorithms is longest common subsequence (LCS). Combined with bit parallelism, recent studies have been able to achieve terascale performance for LCS on GPUs. However, the reported results for the one-to-many matching problem lack correlation with weighted scoring algorithms. In this paper, we describe a novel technique to improve the score significance of the length of LCS algorithm for multiple matching. We extend the bit-vector algorithms for LCS to include integer scoring and parallelize them for hybrid CPU-GPU platforms. We benchmark our algorithm against the well-known sequence alignment algorithm on GPUs, CUDASW++, for accuracy and report performance on three different systems.
@inproceedings{
 title = {Fast longest common subsequence with general integer scoring support on GPUs},
 type = {inproceedings},
 year = {2014},
 identifiers = {[object Object]},
 id = {418c6096-2af8-32f2-a6b1-0e67f103168c},
 created = {2019-10-01T17:21:00.210Z},
 file_attached = {false},
 profile_id = {42d295c0-0737-38d6-8b43-508cab6ea85d},
 last_modified = {2019-10-01T17:23:44.548Z},
 read = {false},
 starred = {false},
 authored = {true},
 confirmed = {true},
 hidden = {false},
 citation_key = {Ozsoy2014a},
 folder_uuids = {73f994b4-a3be-4035-a6dd-3802077ce863},
 private_publication = {false},
 abstract = {Graphic Processing Units (GPUs) have been gaining popularity among high-performance users. Certain classes of algorithms benefit greatly from the massive parallelism of GPUs. One such class of algorithms is longest common subsequence (LCS). Combined with bit parallelism, recent studies have been able to achieve terascale performance for LCS on GPUs. However, the reported results for the one-to-many matching problem lack correlation with weighted scoring algorithms. In this paper, we describe a novel technique to improve the score significance of the length of LCS algorithm for multiple matching. We extend the bit-vector algorithms for LCS to include integer scoring and parallelize them for hybrid CPU-GPU platforms. We benchmark our algorithm against the well-known sequence alignment algorithm on GPUs, CUDASW++, for accuracy and report performance on three different systems.},
 bibtype = {inproceedings},
 author = {Ozsoy, A. and Chauhan, A. and Swany, M.},
 booktitle = {Proceedings of the 2014 International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2014}
}

Downloads: 0