hLCS. A hybrid GPGPU approach for solving multiple short and unbalanced LCS problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationComputational Science and Its Applications, ICCSA 2014 - 14th International Conference, Proceedings
PublisherSpringer Verlag
Pages102-115
Number of pages14
EditionPART 6
ISBN (Print)9783319091525
DOIs
StatePublished - 2014
Externally publishedYes
Event14th International Conference on Computational Science and Its Applications, ICCSA 2014 - Guimaraes, Portugal
Duration: Jun 30 2014Jul 3 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 6
Volume8584 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Computational Science and Its Applications, ICCSA 2014
Country/TerritoryPortugal
CityGuimaraes
Period06/30/1407/3/14

Keywords

  • Longest Common Subsequence
  • multicore and GPU
  • parallel algorithms

Fingerprint

Dive into the research topics of 'hLCS. A hybrid GPGPU approach for solving multiple short and unbalanced LCS problems'. Together they form a unique fingerprint.

Cite this