Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 7
Encontrada(s) 1 página(s)

Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

WFA-GPU: Gap-affine pairwise read-alignment using GPUs

  • Aguado-Puig, Quim|||0000-0003-4871-3192
  • Doblas, Max
  • Matzoros, Christos
  • Espinosa, Antonio|||0000-0002-6460-3789
  • Moure, Juan C.|||0000-0001-6697-0331
  • Marco-Sola, Santiago|||0000-0001-7951-3914
  • Moreto, Miquel|||0000-0002-9848-8758
Advances in genomics and sequencing technologies demand faster and more scalable analysis methods that can process longer sequences with higher accuracy. However, classical pairwise alignment methods, based on dynamic programming (DP), impose impractical computational requirements to align long and noisy sequences like those produced by PacBio and Nanopore technologies. The recently proposed wavefront alignment (WFA) algorithm paves the way for more efficient alignment tools, improving time and memory complexity over previous methods. However, high-performance computing (HPC) platforms require efficient parallel algorithms and tools to exploit the computing resources available on modern accelerator-based architectures. This paper presents WFA-GPU, a GPU (graphics processing unit)-accelerated tool to compute exact gap-affine alignments based on the WFA algorithm. We present the algorithmic adaptations and performance optimizations that allow exploiting the massively parallel capabilities of modern GPU devices to accelerate the alignment computations. In particular, we propose a CPU-GPU co-design capable of performing inter-sequence and intra-sequence parallel sequence alignment, combining a succinct WFA-data representation with an efficient GPU implementation. As a result, we demonstrate that our implementation outperforms the original multi-threaded WFA implementation by up to 4.3× and up to 18.2× when using heuristic methods on long and noisy sequences. Compared to other state-of-the-art tools and libraries, the WFA-GPU is up to 29× faster than other GPU implementations and up to four orders of magnitude faster than other CPU implementations. Furthermore, WFA-GPU is the only GPU solution capable of correctly aligning long reads using a commodity GPU. WFA-GPU code and documentation are publicly available at https://github.com/quim0/WFA-GPU.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

BIMSA, accelerating long sequence alignment using processing-in-memory

  • Alonso-Marín, Alejandro
  • Fernandez, Ivan
  • Aguado-Puig, Quim|||0000-0003-4871-3192
  • Gómez-Luna, Juan|||0000-0002-6514-1571
  • Marco-Sola, Santiago|||0000-0001-7951-3914
  • Mutlu, Onur
  • Moreto, Miquel|||0000-0002-9848-8758
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).
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

GenArchBench: A genomics benchmark suite for arm HPC processors

  • López-Villellas, Lorién
  • Langarita-Benítez, Rubén
  • Badouh, Asaf
  • Soria-Pardos, Víctor
  • Aguado-Puig, Quim
  • López-Paradís, Guillem
  • Doblas, Max
  • Setoain, Javier
  • Kim, Chulho
  • Ono, Makoto
  • Armejach, Adrià
  • Marco-Sola, Santiago
  • Alastruey-Benedé, Jesús
  • Ibáñez, Pablo
  • Moretó, Miquel
Arm usage has substantially grown in the High-Performance Computing (HPC) community. Japanese supercomputer Fugaku, powered by Arm-based A64FX processors, held the top position on the Top500 list between June 2020 and June 2022, currently sitting in the fourth position. The recently released 7th generation of Amazon EC2 instances for compute-intensive workloads (C7 g) is also powered by Arm Graviton3 processors. Projects like European Mont-Blanc and U.S. DOE/NNSA Astra are further examples of Arm irruption in HPC. In parallel, over the last decade, the rapid improvement of genomic sequencing technologies and the exponential growth of sequencing data has placed a significant bottleneck on the computational side. While most genomics applications have been thoroughly tested and optimized for x86 systems, just a few are prepared to perform efficiently on Arm machines. Moreover, these applications do not exploit the newly introduced Scalable Vector Extensions (SVE). This paper presents GenArchBench, the first genome analysis benchmark suite targeting Arm architectures. We have selected computationally demanding kernels from the most widely used tools in genome data analysis and ported them to Arm-based A64FX and Graviton3 processors. Overall, the GenArch benchmark suite comprises 13 multi-core kernels from critical stages of widely-used genome analysis pipelines, including base-calling, read mapping, variant calling, and genome assembly. Our benchmark suite includes different input data sets per kernel (small and large), each with a corresponding regression test to verify the correctness of each execution automatically. Moreover, the porting features the usage of the novel Arm SVE instructions, algorithmic and code optimizations, and the exploitation of Arm-optimized libraries. We present the optimizations implemented in each kernel and a detailed performance evaluation and comparison of their performance on four different HPC machines (i.e., A64FX, Graviton3, Intel Xeon Skylake Platinum, and AMD EPYC Rome). Overall, the experimental evaluation shows that Graviton3 outperforms other machines on average. Moreover, we observed that the performance of the A64FX is significantly constrained by its small memory hierarchy and latencies. Additionally, as proof of concept, we study the performance of a production-ready tool that exploits two of the ported and optimized genomic kernels.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

QuickEd: high-performance exact sequence alignment based on bound-and-align

  • Doblas Font, Max
  • Lostes Cazorla, Óscar
  • Aguado Puig, Quim
  • Iñiguez Rodríguez, Cristian
  • Moretó Planas, Miquel
  • Marco Sola, Santiago
Motivation: Pairwise sequence alignment is a core component of multiple sequencing-data analysis tools. Recent advancements in sequencing technologies have enabled the generation of longer sequences at a much lower price. Thus, long-read sequencing technologies have become increasingly popular in sequencing-based studies. However, classical sequence analysis algorithms face significant scalability challenges when aligning long sequences. As a result, several heuristic methods have been developed to improve performance at the expense of accuracy, as they often fail to produce the optimal alignment. Results: This paper introduces QuickEd, a sequence alignment algorithm based on a bound-and-align strategy. First, QuickEd effectively bounds the maximum alignment-score using efficient heuristic strategies. Then, QuickEd utilizes this bound to reduce the computations required to produce the optimal alignment. Compared to Oðn2Þ complexity of traditional dynamic programming algorithms, QuickEd’s bound-and-align strategy achieves OðnbsÞ complexity, where n is the sequence length and bs is an estimated upper bound of the alignment-score between the sequences. As a result, QuickEd is consistently faster than other state-of-the-art implementations, such as Edlib and BiWFA, achieving performance speedups of 4:2-5:9× and 3:8-4:4×, respectively, aligning long and noisy datasets. In addition, QuickEd maintains a stable memory footprint below 35 MB while aligning sequences up to 1 Mbp. Availability and implementation: QuickEd code and documentation are publicly available at https://github.com/maxdoblas/QuickEd., This work was partially funded by the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033 and FSEþ [PID2019-107255GB-C21, PID2020-113614RBC21, TED2021-132634A-I00, and PRE2021-101059 to Q. A.-P.], the Spanish Ministry of Economy, Industry, and Competitiveness through an FPU fellowship [FPU20-04076 to M.D.], the Spanish Ministry, Ministerio para la Transformación Digital y de la Función Pública, and the European Union – NextGenerationEU through the Cátedra Chip UPC project [TSI-069100-2023-0015], Lenovo-BSC Contract-Framework Contract (2020), and the Generalitat de Catalunya GenCat-DIUiE (GRR) [2017-SGR-313, 2017- SGR-1328, 2017-SGR-1414, 2021-SGR-00763, and 2021- SGR-00574]., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

GenArchBench: A genomics benchmark suite for arm HPC processors

  • López Villellas, Lorien
  • Langarita Benítez, Rubén
  • Badouh, Asaf
  • Soria Pardos, Víctor
  • Aguado Puig, Quim
  • López Paradís, Guillem
  • Doblas Font, Max
  • Setoain, Javier
  • Kim, Chulho
  • Ono, Makoto
  • Armejach Sanosa, Adrià
  • Marco Sola, Santiago
  • Alastruey Benedé, Jesús
  • Ibáñez Marín, Pablo
  • Moretó Planas, Miquel
Arm usage has substantially grown in the High-Performance Computing (HPC) community. Japanese supercomputer Fugaku, powered by Arm-based A64FX processors, held the top position on the Top500 list between June 2020 and June 2022, currently sitting in the fourth position. The recently released 7th generation of Amazon EC2 instances for compute-intensive workloads (C7 g) is also powered by Arm Graviton3 processors. Projects like European Mont-Blanc and U.S. DOE/NNSA Astra are further examples of Arm irruption in HPC. In parallel, over the last decade, the rapid improvement of genomic sequencing technologies and the exponential growth of sequencing data has placed a significant bottleneck on the computational side. While most genomics applications have been thoroughly tested and optimized for x86 systems, just a few are prepared to perform efficiently on Arm machines. Moreover, these applications do not exploit the newly introduced Scalable Vector Extensions (SVE). This paper presents GenArchBench, the first genome analysis benchmark suite targeting Arm architectures. We have selected computationally demanding kernels from the most widely used tools in genome data analysis and ported them to Arm-based A64FX and Graviton3 processors. Overall, the GenArch benchmark suite comprises 13 multi-core kernels from critical stages of widely-used genome analysis pipelines, including base-calling, read mapping, variant calling, and genome assembly. Our benchmark suite includes different input data sets per kernel (small and large), each with a corresponding regression test to verify the correctness of each execution automatically. Moreover, the porting features the usage of the novel Arm SVE instructions, algorithmic and code optimizations, and the exploitation of Arm-optimized libraries. We present the optimizations implemented in each kernel and a detailed performance evaluation and comparison of their performance on four different HPC machines (i.e., A64FX, Graviton3, Intel Xeon Skylake Platinum, and AMD EPYC Rome). Overall, the experimental evaluation shows that Graviton3 outperforms other machines on average. Moreover, we observed that the performance of the A64FX is significantly constrained by its small memory hierarchy and latencies. Additionally, as proof of concept, we study the performance of a production-ready tool that exploits two of the ported and optimized genomic kernels., This work has been partially supported by the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033 (contracts PID2019-107255GB-C21, PID2019-105660RB-C21, PID2022136454NB-C22, and TED2021-132634A-I00), by the Generalitat de Catalunya, Spain (contract 2021-SGR-763), by the Gobierno de Aragón (T58_23R research group), by the European Union NextGenerationEU/ PRTR, and by Lenovo BSC Contract-Framework Contract (2020)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

SMX: Heterogeneous architecture for universal sequence alignment acceleration

  • Doblas Font, Max
  • Shih, Pojui
  • Lostes Cazorla, Óscar
  • Moretó Planas, Miquel
  • Batten, Christopher
  • Marco Sola, Santiago
Sequence alignment is a fundamental building block for critical applications across multiple fields, such as computational biology and information retrieval. The rapid advancement of genome sequencing technologies and breakthrough generative AI tools, like AlphaFold, has driven an exponential increase in sequence-data production, creating a pressing need for fast and efficient sequence alignment tools to analyze ever-growing biological sequence databases. Notwithstanding the numerous accelerators proposed, from general-purpose architectures (CPUs and GPUs) to domain-specific designs (FPGAs and ASICs), the most efficient solutions suffer from over-specialization and fail to adapt to the wide variety of irregular use cases demanded by practical sequence alignment applications. Thus, it remains a challenge to design an architecture that can balance efficiency and flexibility to meet the demands of real-world alignment applications. This work introduces SMX, a heterogeneous architecture designed for high-performance sequence alignment that supports various configurations for different sequence types (DNA, protein, and ASCII text) and alignment models (including weighted gaps and substitution matrices). SMX integrates an ISA extension (SMX-1D) for irregular and sequential tasks and a specialized coprocessor (SMX-2D) to accelerate regular and parallel tasks, both orchestrated by the general-purpose core to enable seamless integration with state-of-the-art sequence alignment algorithms. Our results demonstrate that SMX’s heterogeneous architecture accelerates different sequence alignment use cases by 256–744 × compared to state-of-the-art software implementations when aligning real datasets. Compared to specialized hardware accelerators, SMX delivers up to 18.5 × more peak performance per area added while providing greater flexibility to accelerate different use cases. Physical design results targeting a 22nm technology node estimate SMX’s area at 0.34mm2, which is only 30% of a single-issue in-order CPU. SMX offers a high-performance and efficient heterogeneous architecture for accelerating practical sequence alignment algorithms, providing a scalable and flexible solution tailored to meet the needs of modern sequence-analysis tools. Furthermore, an SMX case study explores the frontier between flexibility and efficiency in domain-specific architectures and accelerators., This work has been partially funded by the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033 and FSE+ [grant number PID2019-107255GB-C21, PID2020-113614RB-C21, TED2021-132634A-I00, and PID2023-146511NB-I00], the Spanish Ministry of Economy, Industry, and Competitiveness through an FPU fellowship [grant number FPU20-04076 to M.D.], LenovoBSC Contract-Framework Contract (2020), the NSF CSSI Award #2311890 and NSF PPoSS Award #2118709, the Spanish Ministry for Digital Transformation and Public Service, and the European Union – NextGenerationEU through the Càtedra Chip UPC project [grant number TSI-069100-2023-0015], the Spanish Ministry for Digital Transformation and Public Service, within the framework of the Recovery, Transformation and Resilience Plan - NextGenerationEU [REGAGE22e00058408992], and the Generalitat de Catalunya GenCat-DIUiE (GRR) [grant numbers 2021-SGR00763, and 2021-SGR-00574]., Peer Reviewed, Postprint (author's final draft)
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Optimal gap-affine alignment in O (s) space

  • Marco-Sola, Santiago|||0000-0001-7951-3914
  • Eizenga, Jordan|||0000-0001-8345-8356
  • Guarracino, Andrea|||0000-0001-9744-131X
  • Paten, Benedict|||0000-0001-8863-3539
  • Garrison, Erik|||0000-0003-3821-631X
  • Moreto, Miquel|||0000-0002-9848-8758
Pairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand faster and scalable algorithms that can cope with the ever-increasing sequence lengths. Classical pairwise alignment algorithms based on dynamic programming are strongly limited by quadratic requirements in time and memory. The recently proposed wavefront alignment algorithm (WFA) introduced an efficient algorithm to perform exact gap-affine alignment in time, where s is the optimal score and n is the sequence length. Notwithstanding these bounds, WFA's memory requirements become computationally impractical for genome-scale alignments, leading to a need for further improvement. In this article, we present the bidirectional WFA algorithm, the first gap-affine algorithm capable of computing optimal alignments in memory while retaining WFA's time complexity of . As a result, this work improves the lowest known memory bound to compute gap-affine alignments. In practice, our implementation never requires more than a few hundred MBs aligning noisy Oxford Nanopore Technologies reads up to 1 Mbp long while maintaining competitive execution times. All code is publicly available at . Supplementary data are available at Bioinformatics online.