Pasar al contenido principal

Resultados relacionados

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

Dipòsit Digital de Documents de la UAB
Publicación 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
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 Capítulo o parte de un libro (BookPart)

Building representative and balanced datasets of OpenMP parallel regions

  • Alcaraz, Jordi|||0000-0002-9640-6763
  • Sleder, Steven
  • Tehranijamsaz, Ali
  • Sikora, Anna|||0000-0003-0090-4109
  • Jannesari, Ali|||0000-0001-8672-5317
  • Sorribes Gomis, Joan|||0000-0002-8868-7382
  • César Galobardes, Eduardo|||0000-0002-9729-8557
Incorporating machine learning into automatic performance analysis and tuning tools is a promising path to tackle the increasing heterogeneity of current HPC applications. However, this introduces the need for generating balanced and representative datasets of parallel applications' executions. This work proposes a methodology for building datasets of OpenMP parallel code regions patterns. It allows for determining whether a given code region covers a unique part of the pattern input space not covered by the patterns already included in the dataset. The proposed methodology uses hardware performance counters to represent the execution of the region, which is referred to as the region signature for a given number of cores. Then, a complete representation of the region is built by joining the signatures for every different thread configuration in the system. Next, correlation analysis is performed between this representation and the representation of all the patterns already in the training set. Finally, if this correlation is below a given threshold, the region is considered to cover a unique part of the pattern input space and is subsequently added to the dataset. For validating this methodology, an example dataset, obtained from well known benchmarks, has been used to train a carefully designed neural network model to demonstrate that it is able to classify different patterns of OpenMP parallel regions.
Dipòsit Digital de Documents de la UAB
Publicación Capítulo o parte de un libro (BookPart)

Wind field parallelization based on Python multiprocessing to reduce forest fire propagation prediction uncertainty

  • Sanjuan Gómez, Gemma|||0000-0003-1406-3320
  • Margalef, Tomàs|||0000-0001-6384-7389
  • Cortés Fité, Ana|||0000-0003-1697-1293
Forest fires provoke significant loses from the ecological, social and economical point of view. Furthermore, the climate emergency will also increase the occurrence of such disasters. In this context, forest fire propagation prediction is a key tool to fight against these natural hazards efficiently and mitigate the damages. However, forest fire spread simulators require a set of input parameters that, in many cases, cannot be measured and must be estimated indirectly introducing uncertainty in forest fire propagation predictions. One of such parameters is the wind. It is possible to measure wind using meteorological stations and it is also possible to predict wind using meteorological models such as WRF. However, wind components are highly affected by the terrain topography introducing a large degree of uncertainty in forest fire spread predictions. Therefore, it is necessary to introduce wind field models that estimate wind speed and direction at very high resolution to reduce such uncertainty. Such models are time consuming models that are usually executed under strict time constrains. So, it is critical to minimize the execution time, taking into account the fact that in many cases it is not possible to execute the model on a supercomputer, but must be executed on commodity hardware available on the field or at control centers. This work introduces a new parallelization approach for wind field calculation based on Python multiprocessing to accelerate wind field evaluation. The results show that the new approach reduces execution time using a single personal computer.
Dipòsit Digital de Documents de la UAB
Publicación Capítulo o parte de un libro (BookPart)

Early adaptive evaluation scheme for data-driven calibration in forest fire spread prediction

  • Fraga, Edigley|||0000-0002-5525-6164
  • Cortés Fité, Ana|||0000-0003-1697-1293
  • Cencerrado Barraqué, Andrés|||0000-0002-9143-3279
  • Hernández Budé, Porfidio|||0000-0002-8592-934X
  • Margalef, Tomàs|||0000-0001-6384-7389
Forest fires severally affect many ecosystems every year, leading to large environmental damages, casualties and economic losses. Established and emerging technologies are used to help wildfire analysts determine fire behavior and spread aiming at a more accurate prediction results and efficient use of resources in fire fighting. Natural hazards simulations need to deal with data input uncertainty and their impact on prediction results, usually resorting to compute-intensive calibration techniques. In this paper, we propose a new evaluation technique capable of reducing the overall calibration time by 60% when compared to the current data-driven approaches. This is achieved by means of the proposed adaptive evaluation technique based on a periodic monitoring of the fire spread prediction error.
Dipòsit Digital de Documents de la UAB
Publicación Capítulo o parte de un libro (BookPart)

Cloud-Based Urgent Computing for Forest Fire Spread Prediction under Data Uncertainties

  • Fraga, Edigley|||0000-0002-5525-6164
  • Cortés Fité, Ana|||0000-0003-1697-1293
  • Margalef, Tomàs|||0000-0001-6384-7389
  • Hernández Budé, Porfidio|||0000-0002-8592-934X
Forest fires severely affect many ecosystems every year, leading to large environmental damages, casualties, and economic losses. Emerging and established technologies are used to help wildfire analysts determine fire behavior and spread, aiming at more accurate prediction results and efficient use of resources in fire fighting. We propose a novel forest fire spread prediction platform based on a proven two-stage prediction model devised to deal with input data uncertainties. The model is able to calibrate the unknown parameters based on the real observed data using an iterative process. Since this calibration is compute-intensive and due to the unpredictability of urgent computing needs, we exploit an elastic and scalable cloud-based solution platform implemented through coarse-grain parallel processing using a work queue.
Dipòsit Digital de Documents de la UAB
Publicación Capítulo o parte de un libro (BookPart)

Efficient Cloud-Based Calibration of Input Data for Forest Fire Spread Prediction

  • Fraga, Edigley|||0000-0002-5525-6164
  • Cortés Fité, Ana|||0000-0003-1697-1293
  • Margalef, Tomàs|||0000-0001-6384-7389
  • Hernández Budé, Porfidio|||0000-0002-8592-934X
Every year, forest fires cause damages to biodiversity, atmosphere, and economy. To face such permanent threat, wildfire analysts rely on emerging and well established technologies to determine fire behavior and propagation patterns. Nevertheless, input data describing fire scenarios are subject to high levels of uncertainty that represent a serious challenge for the correctness of the prediction. The unknown parameters need to be adjusted, and an input data calibration phase is carried over following a genetic algorithm strategy. The calibrated input is then pipelined into the actual prediction phase. In addition, this two-stage prediction scheme is leveraged by the cloud computing, which enables high level of parallelism on demand, almost real-time elasticity and unlimited scalability. All of them at a low-cost strategy. In this paper, to obtain more accurate prediction results and efficient use of cloud resources in the compute-intensive calibration phase, we propose a new fitness function in tandem with a strict deadline policy that decreases overall processing time. In consonance with the hard-deadline-driven nature of fire extinction activities, the proposed strategies improve the genetic algorithm convergence and decrease the response time for the calibration stage, setting up an important upper bound limit to the critical compute-intensive adjustment phase. For the case study evaluated, only 3.87% of of accuracy loss is given out in exchange of a guarantee that the calibration phase will never last more than 50 minutes in the worst case.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Slanted Stixels, A Way to Represent Steep Streets

  • Hernández Juárez, Daniel|||0000-0001-5878-1549
  • Schneider, Lukas
  • Cebrian, Pau|||0000-0002-0650-4117
  • Espinosa, Antonio|||0000-0002-6460-3789
  • Vázquez Bermúdez, David|||0000-0002-2845-8158
  • López, Antonio
  • Franke, Uwe
  • Pollefeys, Marc
  • Moure, Juan C.|||0000-0001-6697-0331
This work presents and evaluates a novel compact scene representation based on Stixels that infers geometric and semantic information. Our approach overcomes the previous rather restrictive geometric assumptions for Stixels by introducing a novel depth model to account for non-flat roads and slanted objects. Both semantic and depth cues are used jointly to infer the scene representation in a sound global energy minimization formulation. Furthermore, a novel approximation scheme is introduced in order to significantly reduce the computational complexity of the Stixel algorithm, and then achieve real-time computation capabilities. The idea is to first perform an over-segmentation of the image, discarding the unlikely Stixel cuts, and apply the algorithm only on the remaining Stixel cuts. This work presents a novel over-segmentation strategy based on a fully convolutional network, which outperforms an approach based on using local extrema of the disparity map. We evaluate the proposed methods in terms of semantic and geometric accuracy as well as run-time on four publicly available benchmark datasets. Our approach maintains accuracy on flat road scene datasets while improving substantially on a novel non-flat road dataset.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Designing a benchmark for the performance evaluation of agent-based simulation applications on HPC

  • Moreno, Andreu
  • Rodríguez, Juan J.
  • Beltrán Mora, Daniel
  • Sikora, Anna|||0000-0003-0090-4109
  • Jorba i Esteve, Josep|||0000-0002-5810-4748
  • César Galobardes, Eduardo|||0000-0002-9729-8557
Agent-based modeling and simulation (ABMS) is a class of computational models for simulating the actions and interactions of autonomous agents with the goal of assessing their effects on a system as a whole. Several frameworks for generating parallel ABMS applications have been developed taking advantage of their common characteristics, but there is a lack of a general benchmark for comparing the performance of the generated applications. We propose and design a benchmark that takes into consideration the most common characteristics of this type of applications and includes parameters for influencing their relevant performance aspects. We provide an initial implementation of the benchmark for FLAME, FLAME GPU, Repast HPC and EcoLab, some of the most popular parallel ABMS platforms, and use it for comparing the applications generated by these platforms. The obtained results are mostly in agreement with previous studies, but the designed and implemented specification has allowed for testing a wider set of aspects, such as the number of interacting agents, the amount of interchanged data or the evolution of the workload and obtaining more reliable results.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

GPU-oriented architecture for an end-to-end image/video codec based on JPEG2000

  • de Cea Dominguez, Carlos|||0000-0002-0868-6479
  • Moure, Juan C.|||0000-0001-6697-0331
  • Bartrina-Rapesta, Joan|||0000-0002-1551-3680
  • Aulí-Llinàs, Francesc|||0000-0002-3208-9957
Modern image and video compression standards employ computationally intensive algorithms that provide advanced features to the coding system. Current standards often need to be implemented in hardware or using expensive solutions to meet the real-time requirements of some environments. Contrarily to this trend, this paper proposes an end-to-end codec architecture running on inexpensive Graphics Processing Units (GPUs) that is based on, though not compatible with, the JPEG2000 international standard for image and video compression. When executed in a commodity Nvidia GPU, it achieves real time processing of 12K video. The proposed S/W architecture utilizes four CUDA kernels that minimize memory transfers, use registers instead of shared memory, and employ a double-buffer strategy to optimize the streaming of data. The analysis of throughput indicates that the proposed codec yields results at least 10× superior on average to those achieved with JPEG2000 implementations devised for CPUs, and approximately 4× superior to those achieved with hardwired solutions of the HEVC/H.265 video compression standard.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Complexity scalable bitplane image coding with parallel coefficient processing

  • de Cea Dominguez, Carlos|||0000-0002-0868-6479
  • Moure, Juan C.|||0000-0001-6697-0331
  • Bartrina-Rapesta, Joan|||0000-0002-1551-3680
  • Aulí-Llinàs, Francesc|||0000-0002-3208-9957
Very fast image and video codecs are a pursued goal both in the academia and the industry. This paper presents a complexity scalable and parallel bitplane coding engine for wavelet-based image codecs. The proposed method processes the coefficients in parallel, suiting hardware architectures based on vector instructions. Our previous work is extended with a mechanism that provides complexity scalability to the system. Such a feature allows the coder to regulate the throughput achieved at the expense of slightly penalizing compression effi- ciency. Experimental results suggests that, when using the fastest speed, the method almost doubles the throughput of our previous engine while penalizing compression efficiency by about 10%.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Real-time 16K video coding on a GPU with complexity scalable BPC-PaCo

  • de Cea Dominguez, Carlos|||0000-0002-0868-6479
  • Moure, Juan C.|||0000-0001-6697-0331
  • Bartrina-Rapesta, Joan|||0000-0002-1551-3680
  • Aulí-Llinàs, Francesc|||0000-0002-3208-9957
The advent of new technologies such as high dynamic range or 8K screens has enhanced the quality of digital images but it has also increased the codecs' computational demands to process such data. This paper presents a video codec that, while providing the same coding features and performance as those of JPEG2000, can process 16K video in real time using a consumer-grade GPU. This high throughput is achieved with a technique that introduces complexity scalability to a bitplane coding engine, which is the most computationally complex stage of the coding pipeline. The resulting codec can trade throughput for coding performance depending on the user's needs. Experimental results suggest that our method can double the throughput achieved by CPU implementations of the recently approved High-Throughput JPEG2000 and by hardwired implementations of HEVC in a GPU.
Dipòsit Digital de Documents de la UAB
Publicación 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
Publicación Artículo científico (JournalArticle)

Predicting number of threads using balanced datasets for openMP regions

  • Alcaraz, Jordi|||0000-0002-9640-6763
  • TehraniJamsaz, Ali
  • Dutta, Akash|||0009-0007-0947-1182
  • Sikora, Anna|||0000-0003-0090-4109
  • Jannesari, Ali|||0000-0001-8672-5317
  • Sorribes Gomis, Joan|||0000-0002-8868-7382
  • César Galobardes, Eduardo|||0000-0002-9729-8557
Incorporating machine learning into automatic performance analysis and tuning tools is a promising path to tackle the increasing heterogeneity of current HPC applications. However, this introduces the need for generating balanced datasets of parallel applications' executions and for dealing with natural imbalances for optimizing performance parameters. This work proposes a holistic approach that integrates a methodology for building balanced datasets of OpenMP code-region patterns and a way to use such datasets for tuning performance parameters. The methodology uses hardware performance counters to characterize the execution of a given region and correlation analysis to determine whether it covers an unique part of the pattern input space. Nevertheless, a balanced dataset of region patterns may become naturally imbalanced when used for training a model for tuning any specific performance parameter. For this reason, we have explored several methods for dealing with naturally imbalanced datasets for finding the appropriated way of using them for tuning purposes. Experimentation shows that the proposed methodology can be used to build balanced datasets and that such datasets, plus a combination of Random Forest and binary classification, can be used to train a model able to accurately tune the number of threads of OpenMP parallel regions.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Drastic reduction of false positive species in samples of insects by intersecting the default output of two popular metagenomic classifiers

  • Garrido-Sanz, Lidia|||0000-0003-2622-9674
  • Senar Rosell, Miquel|||0000-0002-0316-5420
  • Piñol, Josep|||0000-0002-4067-3301
The use of high-throughput sequencing to recover short DNA reads of many species has been widely applied on biodiversity studies, either as amplicon metabarcoding or shotgun metagenomics. These reads are assigned to taxa using classifiers. However, for different reasons, the results often contain many false positives. Here we focus on the reduction of false positive species attributable to the classifiers. We benchmarked two popular classifiers, BLASTn followed by MEGAN6 (BM) and Kraken2 (K2), to analyse shotgun sequenced artificial single-species samples of insects. To reduce the number of misclassified reads, we combined the output of the two classifiers in two different ways: (1) by keeping only the reads that were attributed to the same species by both classifiers (intersection approach); and (2) by keeping the reads assigned to some species by any classifier (union approach). In addition, we applied an analytical detection limit to further reduce the number of false positives species. As expected, both metagenomic classifiers used with default parameters generated an unacceptably high number of misidentified species (tens with BM, hundreds with K2). The false positive species were not necessarily phylogenetically close, as some of them belonged to different orders of insects. The union approach failed to reduce the number of false positives, but the intersection approach got rid of most of them. The addition of an analytic detection limit of 0.001 further reduced the number to ca. 0.5 false positive species per sample. The misidentification of species by most classifiers hampers the confidence of the DNA-based methods for assessing the biodiversity of biological samples. Our approach to alleviate the problem is straightforward and significantly reduced the number of reported false positive species.
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.