TY - GEN
T1 - hLCS. A hybrid GPGPU approach for solving multiple short and unbalanced LCS problems
AU - Valero-Lara, Pedro
PY - 2014
Y1 - 2014
N2 - The "Longest Common Subsequence" is one of the most widely used and well-known methods within the similarity search community, applicable to a wide range of fields. Currently, modern multicore CPU and GPU-based systems offer an impressive cost/performance ratio and are an attractive test platform to accelerate response time and increase the number of problems solved per second. The use of GPUs for carrying out sequences alignment is widely extended for bioinformatics applications. However, we focus on the use of this algorithm applied to other problems which supposes a new and different approach. In particular, the most important difference is found in the pattern of the sequences. While, on one hand, the size of the biological sequences are large and similar, on the other hand, the sequences in other applications are short and unbalanced. Furthermore, this work aims to use one multicore CPU and GPU system for computing multiple problems simultaneously instead of computing only one. The main contribution of this work is a new hybrid approach which combines the two classical parallel techniques for our problem in two different phases. This new implementation is up to 80× and 25× faster, in terms of speedup, over the sequential and multicore counterpart respectively for our particular problem, that is, solving multiple "Longest Common Subsequence" problems on short and unbalanced sequences with a high ratio of problems solved per second.
AB - The "Longest Common Subsequence" is one of the most widely used and well-known methods within the similarity search community, applicable to a wide range of fields. Currently, modern multicore CPU and GPU-based systems offer an impressive cost/performance ratio and are an attractive test platform to accelerate response time and increase the number of problems solved per second. The use of GPUs for carrying out sequences alignment is widely extended for bioinformatics applications. However, we focus on the use of this algorithm applied to other problems which supposes a new and different approach. In particular, the most important difference is found in the pattern of the sequences. While, on one hand, the size of the biological sequences are large and similar, on the other hand, the sequences in other applications are short and unbalanced. Furthermore, this work aims to use one multicore CPU and GPU system for computing multiple problems simultaneously instead of computing only one. The main contribution of this work is a new hybrid approach which combines the two classical parallel techniques for our problem in two different phases. This new implementation is up to 80× and 25× faster, in terms of speedup, over the sequential and multicore counterpart respectively for our particular problem, that is, solving multiple "Longest Common Subsequence" problems on short and unbalanced sequences with a high ratio of problems solved per second.
KW - Longest Common Subsequence
KW - multicore and GPU
KW - parallel algorithms
UR - http://www.scopus.com/inward/record.url?scp=84904902359&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-09153-2_8
DO - 10.1007/978-3-319-09153-2_8
M3 - Conference contribution
AN - SCOPUS:84904902359
SN - 9783319091525
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 102
EP - 115
BT - Computational Science and Its Applications, ICCSA 2014 - 14th International Conference, Proceedings
PB - Springer Verlag
T2 - 14th International Conference on Computational Science and Its Applications, ICCSA 2014
Y2 - 30 June 2014 through 3 July 2014
ER -