Skip to main content

High Performance Architectures

RYC-2016-21104

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de Promoción del Talento y su Empleabilidad en I+D+i
Subprogram Subprograma Estatal de Incorporación
Call Ramón y Cajal
Call year 2016
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 7
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.
Dipòsit Digital de Documents de la UAB
Publication Artículo científico (JournalArticle)

AnchorWave, Sensitive alignment of genomes with high sequence diversity, extensive structural polymorphism, and whole-genome duplication

  • Song, Baoxing|||0000-0003-1478-9228
  • Marco-Sola, Santiago|||0000-0001-7951-3914
  • Moreto, Miquel|||0000-0002-9848-8758
  • Johnson, Lynn
  • Buckler, Edward S.|||0000-0002-3100-371X
  • Stitzer, Michelle C.|||0000-0003-4140-3765
One fundamental analysis needed to interpret genome assemblies is genome alignment. Yet, accurately aligning regulatory and transposon regions outside of genes remains challenging. We introduce Anchored Wavefront alignment (AnchorWave), which implements a genome duplication informed longest path algorithm to identify collinear regions and performs base pair-resolved, end-to-end alignment for collinear blocks using an efficient two-piece affine gap cost strategy. AnchorWave improves the alignment under a number of scenarios: genomes with high similarity, large genomes with high transposable element activity, genomes with many inversions, and alignments between species with deeper evolutionary divergence and different whole-genome duplication histories. Potential use cases include genome comparison for evolutionary analysis of nongenic sequences and population genetics of taxa with large, repeat-rich genomes. Millions of species are currently being sequenced, and their genomes are being compared. Many of them have more complex genomes than model systems and raise novel challenges for genome alignment. Widely used local alignment strategies often produce limited or incongruous results when applied to genomes with dispersed repeats, long indels, and highly diverse sequences. Moreover, alignment using many-to-many or reciprocal best hit approaches conflicts with well-studied patterns between species with different rounds of whole-genome duplication. Here, we introduce Anchored Wavefront alignment (AnchorWave), which performs whole-genome duplication-informed collinear anchor identification between genomes and performs base pair-resolved global alignment for collinear blocks using a two-piece affine gap cost strategy. This strategy enables AnchorWave to precisely identify multikilobase indels generated by transposable element (TE) presence/absence variants (PAVs). When aligning two maize genomes, AnchorWave successfully recalled 87% of previously reported TE PAVs. By contrast, other genome alignment tools showed low power for TE PAV recall. AnchorWave precisely aligns up to three times more of the genome as position matches or indels than the closest competitive approach when comparing diverse genomes. Moreover, AnchorWave recalls transcription factor-binding sites at a rate of 1.05- to 74.85-fold higher than other tools with significantly lower false-positive alignments. AnchorWave complements available genome alignment tools by showing obvious improvement when applied to genomes with dispersed repeats, active TEs, high sequence diversity, and whole-genome duplication variation.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Artículo científico (JournalArticle)

On the maturity of parallel applications for asymmetric multi-core processors

  • Chronaki, Kallia
  • Moreto, Miquel
  • Casas, Marc
  • Rico, Alejandro
  • Badia, Rosa M.
  • Ayguade, Eduard
  • Valero, Mateo
Asymmetric multi-cores (AMCs) are a successful architectural solution for both mobile devices and supercomputers. By maintaining two types of cores (fast and slow) AMCs are able to provide high performance under the facility power budget. This paper performs the first extensive evaluation of how portable are the current HPC applications for such supercomputing systems. Specifically we evaluate several execution models on an ARM big.LITTLE AMC using the PARSEC benchmark suite that includes representative highly parallel applications. We compare schedulers at the user, OS and runtime levels, using both static and dynamic options and multiple configurations, and assess the impact of these options on the well-known problem of balancing the load across AMCs. Our results demonstrate that scheduling is more effective when it takes place in the runtime system level as it improves the baseline by 23%, while the heterogeneous-aware OS scheduling solution improves the baseline by 10%., This work has been supported by the RoMoL ERC Advanced Grant (GA 321253), by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation (contracts TIN2015-65316-P), by the Generalitat de Catalunya (contracts 2014-SGR-1051 and 2014-SGR-1272), and by the European Union’s Horizon 2020 research and innovation programme under grant agreement No 671697 and No. 779877. Kallia Chronaki has been partially supported by the Ministry of Economy and Competitiveness under Ramon y Cajal fellowship number RYC-2016-21104., Peer reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Accurate and efficient constrained molecular dynamics of polymers using Newton's method and special purpose code

  • López-Villellas, L.
  • Kjelgaard Mikkelsen C. Ch.
  • Galano-Frutos, J. J.
  • Marco-Sola, S.
  • Alastruey-Benedé, J.
  • Ibáñez, P.
  • Moretó, M.
  • Sancho, J.
  • García-Risueño, P.
In molecular dynamics simulations we can often increase the time step by imposing constraints on bond lengths and bond angles. This allows us to extend the length of the time interval and therefore the range of physical phenomena that we can afford to simulate. We examine the existing algorithms and software for solving nonlinear constraint equations in parallel and we explain why it is necessary to advance the state-of-the-art. We present ILVES-PC, a new algorithm for imposing bond constraints on proteins accurately and efficiently. It solves the same system of differential algebraic equations as the celebrated SHAKE algorithm, but ILVES-PC solves the nonlinear constraint equations using Newton’s method rather than the nonlinear Gauss-Seidel method. Moreover, ILVES-PC solves the necessary linear systems using a specialized linear solver that exploits the structure of the protein. ILVES-PC can rapidly solve constraint equations as accurately as the hardware will allow. The run-time of ILVES-PC is proportional to the number of constraints. We have integrated ILVES-PC into GROMACS and simulated proteins of different sizes. Compared with SHAKE, we have achieved speedups of up to 4.9× in single-threaded executions and up to 76× in shared-memory multi-threaded executions. Moreover, ILVES-PC is more accurate than P-LINCS algorithm. Our work is a proof-of-concept of the utility of software designed specifically for the simulation of polymers.
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.