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

doi:10.1109/IPDPS53621.2022.00076

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 volume › Conference contribution › Scientific › peer-review

1 Citation (Scopus)

15 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 language	English
Title of host publication	Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Editors	L. O'Conner
Place of Publication	Piscataway
Publisher	IEEE
Pages	728-738
Number of pages	11
ISBN (Electronic)	978-1-6654-8106-9
ISBN (Print)	978-1-6654-8107-6
DOIs	https://doi.org/10.1109/IPDPS53621.2022.00076
Publication status	Published - 2022
Event	2022 IEEE 36th International Parallel and Distributed Processing Symposium - Vitual at Lyon, France Duration: 30 May 2022 → 3 Jun 2022 Conference number: 36th

Conference

Conference	2022 IEEE 36th International Parallel and Distributed Processing Symposium
Abbreviated title	IPDPS 2022
Country/Territory	France
City	Vitual at Lyon
Period	30/05/22 → 3/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

Access to Document

10.1109/IPDPS53621.2022.00076

SALoBa_Maximizing_Data_Locality_and_Workload_Balance_for_Fast_Sequence_Alignment_on_GPUsFinal published version, 839 KB

Cite this

Park, S., Kim, H., Ahmad, T., Ahmed, N., Al-Ars, Z., Hofstee, P., Kim, Y., & Lee, J. (2022). SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs. In L. O'Conner (Ed.), Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (pp. 728-738). Article 9820739 IEEE. https://doi.org/10.1109/IPDPS53621.2022.00076

@inproceedings{2e8b2274eef44c79b76e76fbfc21c133,

title = "SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs",

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.",

keywords = "Genome sequencing, Sequence alignment, Smith-Waterman, GPU acceleration",

author = "Seongyeon Park and Hajin Kim and Tanveer Ahmad and Nauman Ahmed and Zaid Al-Ars and Peter Hofstee and Youngsok Kim and Jinho Lee",

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.; 2022 IEEE 36th International Parallel and Distributed Processing Symposium, IPDPS 2022 ; Conference date: 30-05-2022 Through 03-06-2022",

year = "2022",

doi = "10.1109/IPDPS53621.2022.00076",

language = "English",

isbn = "978-1-6654-8107-6",

pages = "728--738",

editor = "L. O'Conner",

booktitle = "Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)",

publisher = "IEEE",

address = "United States",

}

Park, S, Kim, H, Ahmad, T, Ahmed, N , Al-Ars, Z , Hofstee, P, Kim, Y & Lee, J 2022, SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs. in L O'Conner (ed.), Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)., 9820739, IEEE, Piscataway, pp. 728-738, 2022 IEEE 36th International Parallel and Distributed Processing Symposium, Vitual at Lyon, France, 30/05/22. https://doi.org/10.1109/IPDPS53621.2022.00076

SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs. / Park, Seongyeon ; Kim, Hajin ; Ahmad, Tanveer et al.
Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS). ed. / L. O'Conner. Piscataway: IEEE, 2022. p. 728-738 9820739.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - SALoBa

T2 - 2022 IEEE 36th International Parallel and Distributed Processing Symposium

AU - Park, Seongyeon

AU - Kim, Hajin

AU - Ahmad, Tanveer

AU - Ahmed, Nauman

AU - Al-Ars, Zaid

AU - Hofstee, Peter

AU - Kim, Youngsok

AU - Lee, Jinho

N1 - Conference code: 36th

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Genome sequencing

KW - Sequence alignment

KW - Smith-Waterman

KW - GPU acceleration

UR - http://www.scopus.com/inward/record.url?scp=85136332067&partnerID=8YFLogxK

U2 - 10.1109/IPDPS53621.2022.00076

DO - 10.1109/IPDPS53621.2022.00076

M3 - Conference contribution

SN - 978-1-6654-8107-6

SP - 728

EP - 738

BT - Proceedings of the 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)

A2 - O'Conner, L.

PB - IEEE

CY - Piscataway

Y2 - 30 May 2022 through 3 June 2022

ER -

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

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this