BIMSA : accelerating long sequence alignment using processing-in-memory
Alonso-Marín, Alejandro (Barcelona Supercomputing Center)
Fernandez, Ivan (Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors)
Aguado-Puig, Quim (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Gómez-Luna, Juan (NVIDIA)
Marco-Sola, Santiago (Barcelona Supercomputing Center)
Mutlu, Onur (ETH Zurich. Department of Information Technology and Electrical Engineering)
Moreto, Miquel (Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors)

Date:	2024
Abstract:	Recent advances in sequencing technologies have stressed the critical role of sequence analysis algorithms and tools in genomics and healthcare research. In particular, sequence alignment is a fundamental building block in many sequence analysis pipelines and is frequently a performance bottleneck both in terms of execution time and memory usage. Classical sequence alignment algorithms are based on dynamic programming and often require quadratic time and memory with respect to the sequence length. As a result, classical sequence alignment algorithms fail to scale with increasing sequence lengths and quickly become memory-bound due to data-movement penalties. Processing-In-Memory (PIM) is an emerging architectural paradigm that seeks to accelerate memory-bound algorithms by bringing computation closer to the data to mitigate data-movement penalties. This work presents BIMSA (idirectional n-emory equence lignment), a PIM design and implementation for the state-of-the-art sequence alignment algorithm BiWFA (Bidirectional Wavefront Alignment), incorporating new hardware-aware optimizations for a production-ready PIM architecture (UPMEM). BIMSA supports aligning sequences up to 100K bases, exceeding the limitations of state-of-the-art PIM implementations. First, BIMSA achieves speedups up to 22. 24× (11. 95× on average) compared to state-of-the-art PIM-enabled implementations of sequence alignment algorithms. Second, achieves speedups up to 5. 84× (2. 83× on average) compared to the highest-performance multicore CPU implementation of BiWFA. Third, BIMSA exhibits linear scalability with the number of compute units in memory, enabling further performance improvements with upcoming PIM architectures equipped with more compute units and achieving speedups up to 9. 56× (4. 7× on average).
Grants:	European Commission 101137416 Agencia Estatal de Investigación PID2023-146193OB-I00 Agencia Estatal de Investigación PID2023-146511NB-I00 Agencia Estatal de Investigación TED2021-132634A-I00 Agencia Estatal de Investigación PRE2021-101059 Agencia Estatal de Investigación PID2020-113614RB-C21 Agencia Estatal de Investigación PID2019-107255GB-C21 Agencia Estatal de Investigación PID2019-107255GB-C22 Agència de Gestió d'Ajuts Universitaris i de Recerca 2021/SGR-00763 Agència de Gestió d'Ajuts Universitaris i de Recerca 2021/SGR-00574
Rights:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Language:	Anglès
Document:	Article ; recerca ; Versió publicada
Subject:	Bioinformatics ; Computational Biology ; Biological Sciences
Published in:	Bioinformatics, Vol. 40, issue 11 (November 2024) , art. btae631, ISSN 1367-4811

DOI: 10.1093/bioinformatics/btae631
PMID: 39432682

10 p, 1.5 MB

The record appears in these collections:
Articles > Research articles
Articles > Published articles