SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs

Seongyeon Park, Hajin Kim, Tanveer Ahmad, Nauman Ahmed, Zaid Al-Ars, Peter Hofstee, Youngsok Kim, Jinho Lee*

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
7 Downloads (Pure)

Abstract

Sequence alignment forms an important backbone in many sequencing applications. A commonly used strategy for sequence alignment is an approximate string matching with a two-dimensional dynamic programming approach. Although some prior work has been conducted on GPU acceleration of a sequence alignment, we identify several shortcomings that limit exploiting the full computational capability of modern GPUs. This paper presents SALoBa, a GPU-accelerated sequence alignment library focused on seed extension. Based on the analysis of previous work with real-world sequencing data, we propose techniques to exploit the data locality and improve work-load balancing. The experimental results reveal that SALoBa significantly improves the seed extension kernel compared to state-of-the-art GPU-based methods.
Original languageEnglish
Title of host publicationProceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
EditorsL. O'Conner
Place of PublicationPiscataway
PublisherIEEE
Pages728-738
Number of pages11
ISBN (Electronic)978-1-6654-8106-9
ISBN (Print)978-1-6654-8107-6
DOIs
Publication statusPublished - 2022
Event2022 IEEE 36th International Parallel and Distributed Processing Symposium - Vitual at Lyon, France
Duration: 30 May 20223 Jun 2022
Conference number: 36th

Conference

Conference2022 IEEE 36th International Parallel and Distributed Processing Symposium
Abbreviated titleIPDPS 2022
Country/TerritoryFrance
CityVitual at Lyon
Period30/05/223/06/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • Genome sequencing
  • Sequence alignment
  • Smith-Waterman
  • GPU acceleration

Fingerprint

Dive into the research topics of 'SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs'. Together they form a unique fingerprint.

Cite this