Skip to main content

Resultados relacionados

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

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

Accelerating Edit-Distance Sequence Alignment on GPU Using the Wavefront Algorithm

  • Aguado-Puig, Quim|||0000-0003-4871-3192
  • Marco-Sola, Santiago|||0000-0001-7951-3914
  • Moure, Juan C.|||0000-0001-6697-0331
  • Castells-Rufas, David|||0000-0002-7181-9705
  • Alvarez, Lluc
  • Espinosa, Antonio|||0000-0002-6460-3789
  • Moreto, Miquel|||0000-0002-9848-8758
Sequence alignment remains a fundamental problem with practical applications ranging from pattern recognition to computational biology. Traditional algorithms based on dynamic programming are hard to parallelize, require significant amounts of memory, and fail to scale for large inputs. This work presents eWFA-GPU, a GPU (graphics processing unit)-accelerated tool to compute the exact edit-distance sequence alignment based on the wavefront alignment algorithm (WFA). This approach exploits the similarities between the input sequences to accelerate the alignment process while requiring less memory than other algorithms. Our implementation takes full advantage of the massive parallel capabilities of modern GPUs to accelerate the alignment process. In addition, we propose a succinct representation of the alignment data that successfully reduces the overall amount of memory required, allowing the exploitation of the fast shared memory of a GPU. Our results show that our GPU implementation outperforms by 3- 9× the baseline edit-distance WFA implementation running on a 20 core machine. As a result, eWFA-GPU is up to 265 times faster than state-of-the-art CPU implementation, and up to 56 times faster than state-of-the-art GPU implementations.
Dipòsit Digital de Documents de la UAB
Publication 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.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Programming parallel dense matrix factorizations and inversion for new-generation NUMA architectures

  • Catalán, Sandra
  • Igual, Francisco D.
  • Herrero, José R.
  • Rodríguez-Sánchez, Rafael
  • Quintana-Ortí, Enrique S.|||0000-0002-5454-165X
[EN] We propose a methodology to address the programmability issues derived from the emergence of newgeneration shared-memory NUMA architectures. For this purpose, we employ dense matrix factorizations and matrix inversion (DMFI) as a use case, and we target two modern architectures (AMD Rome and Huawei Kunpeng 920) that exhibit configurable NUMA topologies. Our methodology pursues performance portability across different NUMA configurations by proposing multi-domain implementations for DMFI plus a hybrid task- and loop-level parallelization that configures multi-threaded executions to fix core-todata binding, exploiting locality at the expense of minor code modifications. In addition, we introduce a generalization of the multi-domain implementations for DMFI that offers support for virtually any NUMA topology in present and future architectures. Our experimentation on the two target architectures for three representative dense linear algebra operations validates the proposal, reveals insights on the necessity of adapting both the codes and their execution to improve data access locality, and reports performance across architectures and inter- and intra-socket NUMA configurations competitive with state-of-the-art message-passing implementations, maintaining the ease of development usually associated with shared-memory programming., This research was sponsored by project PID2019-107255GB of Ministerio de Ciencia, Innovacion y Universidades; project S2018/TCS-4423 of Comunidad de Madrid; project 2017-SGR-1414 of the Generalitat de Catalunya and the Madrid Government under the Multiannual Agreement with UCM in the line Pro-gram to Stimulate Research for Young Doctors in the context of the V PRICIT, project PR65/19-22445. This project has also re-ceived funding from the European High-Performance Computing Joint Undertaking (JU) under grant agreement No 955558. The JU receives support from the European Union's Horizon 2020 research and innovation programme, and Spain, Germany, France, Italy, Poland, Switzerland, Norway. The work is also supported by grants PID2020-113656RB-C22 and PID2021-126576NB-I00 of MCIN/AEI/10.13039/501100011033 and by ERDF A way of making Europe.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Static scheduling of the LU factorization with look-ahead on asymmetric multicore processors

  • Catalán, Sandra
  • Herrero, José R.
  • Rodríguez-Sánchez, Rafael
  • Quintana-Ortí, Enrique S.|||0000-0002-5454-165X
[EN] We analyze the benefits of look-ahead in the parallel execution of the LU factorization with partial pivoting (LUpp) in two distinct "asymmetric" multicore scenarios. The first one corresponds to an actual hardware-asymmetric architecture such as the Samsung Exynos 5422 system-on-chip (SoC), equipped with an ARM big.LITTLE processor consisting of a quad core Cortex-A15 cluster plus a quad-core Cortex-A7 cluster. For this scenario, we propose a careful mapping of the different types of tasks appearing in LUpp to the computational resources, in order to produce an efficient architecture-aware exploitation of the computational resources integrated in this SoC. The second asymmetric configuration appears in a hardware-symmetric multicore architecture where the cores can individually operate at a different frequency levels. In this scenario, we show how to employ the frequency slack to accelerate the tasks in the critical path of LUpp in order to produce a faster global execution as well as a lower energy consumption. (C) 2018 Elsevier B.V. All rights reserved., The researchers from Universidad Jaume I were supported by projects TIN2014-53495-R and TIN2017-82972-R of MINECO and FEDER, and the FPU program of MECD. The researcher from Universitat Politecnica de Catalunya was supported by projects TIN2015-65316-P of MINECO and FEDER and 2017-SGR-1414 from the Generalitat de Catalunya.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Fine-grain task-parallel algorithms for matrix factorizations and inversion on many-threaded CPUs

  • Catalán, Sandra
  • Herrero, José R.
  • Igual, Francisco D.
  • Rodríguez-Sánchez, Rafael
  • Quintana-Ortí, Enrique S.|||0000-0002-5454-165X
[EN] We extend a two-level task partitioning previously applied to the inversion of dense matrices via Gauss-Jordan elimination to the more challenging QR factorization as well as the initial orthogonal reduction to band form found in the singular value decomposition. Our new task-parallel algorithms leverage the tasking mechanism currently available in OpenMP to exploit "nested" task parallelism, with a first outer level that operates on matrix panels and a second inner level that processes the matrix either by mu$$ \mu $$-panels or by tiles, in order to expose a large number of independent tasks. We present a detailed performance analysis, including execution traces, which shows that the two-level refinement into fine grain tasks allows for an improved load balancing and delivers high performance on current general-purpose many-core processors (CPUs) from Intel and AMD., This research was sponsored by projects RTI2018-093684-B-I00, PID2019-107255GB and TIN2017-82972-R ofMinisterio de Ciencia, Innovación y Universidades; project S2018/TCS-4423 of Comunidad de Madrid; project 2017-SGR-1414 of the Generalitat de Catalunya and the Madrid Government under the Multiannual Agreement with UCM in the line Program to Stimulate Research for Young Doctors in the context of the V PRICIT, project PR65/19-22445.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Efficient update of determinants of rmany-electron wave function overlaps

  • Alonso-Jordá, Pedro|||0000-0002-6882-6592
  • Quintana-Ortí, Enrique S.|||0000-0002-5454-165X
  • Davidovic, Davor
  • Sapunar, Marin
  • Herrero, Jose R.
[EN] The calculation of overlaps between many-electron wave functions at different nuclear geometries during nonadiabatic dynamics simulations requires the evaluation of a large number of determinants of matrices that differ only in a few rows/columns. While this calculation is fast for small systems, its cost grows faster than the alternative electronic structure calculation used to obtain the wave functions. For wave functions that can be written as a CIS expansion, all determinants can be computed using the set of level-2 minors of the reference matrix. However, this is still a costly computation for large systems. In this paper, we provide an algorithm for efficiently calculating all level-2 minors of a matrix by re-utilizing and updating the LU factorization for the determinants of the minors. This approach results in a parallel version of the algorithm that is up to an order of magnitude faster then the current best parallel implementation. The algorithm thus allows the computation of exact wave function overlaps for relatively large systems, with a high density of states, at virtually no cost compared with the electronic structure calculations. Furthermore, the new algorithm opens the path to further investigations in efficient computing of the exact wave function overlaps for complex wave functions such as MR-CIS and MR-CISD. Program summary Program Title: CIS Overlap Licensing provisions: MIT Programming language: FORTRAN 2008, C Nature of problem: Calculation of overlaps between CIS type wave functions at different nuclear geometries during nonadiabatic dynamics simulation requires calculating a large number of connected determinants and scales with the seventh power of the size of the system being studied. Without additional approximations, for large systems this computation becomes more costly than the electronic structure calculation used to obtain the wave functions. Solution method: All of the determinants required for a CIS wave function overlap calculation can be derived from the set of all level-2 minors of the matrix of overlaps between the reference Slater determinants. We developed an algorithm for efficiently computing all level-2 minors of a matrix. This part of the computational process was the bottleneck in previous solutions to the problem and is now an order of magnitude faster resulting in significantly faster overall calculation of the wave function overlaps., Enrique S. Quintana-Orti was supported by project TIN2017-82972-R, Pedro Alonso-Jorda by project TIN2017-89314-P-AR, and Jose R. Herrero by project TIN2015-65316-P, all of the MINECO and FEDER. The latter was also funded by the Generalitat de Catalunya (contract 2017-SGR-1414). Marin Sapunar and Davor Davidovic were supported by Croatian Science Foundation under grant HRZZ IP-2016-06-1142.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A case for malleable thread-level linear algebra libraries: The LU factorization with partial pivoting

  • Catalán, Sandra
  • Herrero, José R.
  • Rodríguez-Sánchez, Rafael
  • van de Geijn, Robert
  • Quintana-Ortí, Enrique S.|||0000-0002-5454-165X
[EN] We propose two novel techniques for overcoming load-imbalance encountered when implementing so-called look-ahead mechanisms in relevant dense matrix factorizations for the solution of linear systems. Both techniques target the scenario where two thread teams are created/activated during the factorization, with each team in charge of performing an independent task/branch of execution. The first technique promotes worker sharing (WS) between the two tasks, allowing the threads of the task that completes first to be reallocated for use by the costlier task. The second technique allows a fast task to alert the slower task of completion, enforcing the early termination (ET) of the second task, and a smooth transition of the factorization procedure into the next iteration. The two mechanisms are instantiated via a new malleable thread-level implementation of the basic linear algebra subprograms, and their benefits are illustrated via an implementation of the LU factorization with partial pivoting enhanced with look-ahead. Concretely, our experimental results on an Intel-Xeon system with 12 cores show the benefits of combining WS+ET, reporting competitive performance in comparison with a task-parallel runtime-based solution., This work was supported in part by the Spanish Ministerio de Economia y Competitividad under Project TIN2014-53495-R, Project TIN2015-65316-P, and Project TIN2017-82972-R, in part by the H2020 EU FETHPC "INTERTWinE" under Project 671602, in part by the Generalitat de Catalunya under Project 2017-SGR-1414, and in part by the NSF under Grant ACI-1550493.
Dipòsit Digital de Documents de la UAB
Publication Artículo científico (JournalArticle)

Fast gap-affine pairwise alignment using the wavefront algorithm

  • Marco-Sola, Santiago|||0000-0001-7951-3914
  • Moure, Juan C|||0000-0001-6697-0331
  • Moreto, Miquel|||0000-0002-9848-8758
  • Espinosa, Antonio|||0000-0002-6460-3789
Pairwise alignment of sequences is a fundamental method in modern molecular biology, implemented within multiple bioinformatics tools and libraries. Current advances in sequencing technologies press for the development of faster pairwise alignment algorithms that can scale with increasing read lengths and production yields. In this article, we present the wavefront alignment algorithm (WFA), an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. As opposed to traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time O (ns), proportional to the read length n and the alignment score s, using memory. Furthermore, our algorithm exhibits simple data dependencies that can be easily vectorized, even by the automatic features of modern compilers, for different architectures, without the need to adapt the code. We evaluate the performance of our algorithm, together with other state-of-the-art implementations. As a result, we demonstrate that the WFA runs 20-300× faster than other methods aligning short Illumina-like sequences, and 10-100× faster using long noisy reads like those produced by Oxford Nanopore Technologies.
Dipòsit Digital de Documents de la UAB
Publication 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.