Pasar al contenido principal

DESAFIOS ACTUALES EN HPC: ARQUITECTURAS, SOFTWARE Y APLICACIONES

PID2019-104184RB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDADE DA CORUÑA

Resultados relacionados

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

Minerva. Repositorio Institucional de la Universidad de Santiago de Compostela
Publicación Artículo científico (JournalArticle)

A Parallel Skeleton for Divide-and-conquer Unbalanced and Deep Problems

  • Martínez, Millán A.
  • Fraguela, Basilio B.
  • Cabaleiro Domínguez, José Carlos
The Divide-and-conquer (D&C) pattern appears in a large number of problems and is highly suitable to exploit parallelism. This has led to much research on its easy and efficient application both in shared and distributed memory parallel systems. One of the most successful approaches explored in this area consists of expressing this pattern by means of parallel skeletons which automate and hide the complexity of the parallelization from the user while trying to provide good performance. In this paper, we tackle the development of a skeleton oriented to the efficient parallel resolution of D&C problems with a high degree of imbalance among the subproblems generated and/or a deep level of recurrence. The skeleton achieves in our experiments average speedups between 11 and 18% higher than those of other solutions, reaching a maximum speedup of 78% in some tests. Nevertheless, the new proposal requires an average of between 13 and 29% less programming effort than the usual alternatives.
Minerva. Repositorio Institucional de la Universidad de Santiago de Compostela
Publicación Artículo científico (JournalArticle)

A new thread-level speculative automatic parallelization model and library based on duplicate code execution

  • Martínez, Millan A.
  • Fraguela, Basilio B.
  • Cabaleiro Domínguez, José Carlos
  • Fernández Rivera, Francisco
Loop-efficient automatic parallelization has become increasingly relevant due to the growing number of cores in current processors and the programming effort needed to parallelize codes in these systems efficiently. However, automatic tools fail to extract all the available parallelism in irregular loops with indirections, race conditions or potential data dependency violations, among many other possible causes. One of the successful ways to automatically parallelize these loops is the use of speculative parallelization techniques. This paper presents a new model and the corresponding C++ library that supports the speculative automatic parallelization of loops in shared memory systems, seeking competitive performance and scalability while keeping user effort to a minimum. The primary speculative strategy consists of redundantly executing chunks of loop iterations in a duplicate fashion. Namely, each chunk is executed speculatively in parallel to obtain results as soon as possible and sequentially in a different thread to validate the speculative results. The implementation uses C++11 threads and it makes intensive use of templates and advanced multithreading techniques. An evaluation based on various benchmarks confirms that our proposal provides a competitive level of performance and scalability.
Minerva. Repositorio Institucional de la Universidad de Santiago de Compostela
Publicación Artículo científico (JournalArticle)

A highly optimized skeleton for unbalanced and deep divide‑and‑conquer algorithms on multi‑core clusters

  • Martínez, Millán A.
  • Fraguela, Basilio B.
  • Cabaleiro Domínguez, José Carlos
Efficiently implementing the divide-and-conquer pattern of parallelism in distributed memory systems is very relevant, given its ubiquity, and difficult, given its recursive nature and the need to exchange tasks and data among the processors. This task is noticeably further complicated in the presence of multi-core systems, where hybrid parallelism must be exploited to attain the best performance, and when unbalanced and deep workloads are considered, as additional measures must be taken to load balance and avoid deep recursion problems. In this manuscript a parallel skeleton that fulfills all these requirements while providing high levels of usability is presented. In fact, the evaluation shows that our proposal is on average 415.32% faster than MPI codes and 229.18% faster than MPI + OpenMP benchmarks, while offering an average improvement in the programmability metrics of 131.04% over MPI alternatives and 155.18% over MPI + OpenMP solutions.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Population based metaheuristics in Spark: Towards a general framework using PSO as a case study

  • Pardo, Xoán C.
  • González, Patricia
  • Banga, Julio R.
  • Doallo, Ramón
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: Over the years metaheuristics have been successfully applied to optimization problems in many real-world applications. The increasing complexity and scale of the problems addressed has posed new challenges to researchers in the field. The application of distributed metaheuristics is a common approach to speed up the time to solution or improve its quality by leveraging traditional parallel programming models on platforms like multicore processors or computer clusters. More recently, the emergence of Cloud Computing and new programming models and frameworks for Big Data has facilitated access to an unprecedented amount of computational resources, which led to a growing interest in optimization frameworks that support the development and execution of distributed metaheuristics taking advantage of this potential. In this paper, we present the current status of development of one such framework that aims to provide support for the application of distributed population-based metaheuristics to the global optimization of large-scale problems in Spark. The framework provides a reduced set of abstractions to represent the general structure of population-based metaheuristics as templates and strategies to particularize them into concrete metaheuristics, as well as other nice features like out of the box implementations of the most common distributed models, full configurability through a human-friendly format, and the possibility of rapid prototyping and testing metaheuristics in the Spark shell. To validate the approach, a template for Particle Swarm Optimization (PSO) was implemented as a proof of concept, which includes strategies for instantiating different variants of the algorithm, configurable topologies, and sequential and distributed execution models., This work was supported by MCIN/AEI/10.13039/501100011033 [grant numbers PID2019-104184RB-I00 , PID2022-136435NB-I00 and PID2020-117271RB-C22 (BIODYNAMICS) ], PID2022 also funded by “ ERDF A way of making Europe ”, EU. Also supported by Xunta de Galicia [grant number ED431C 2021/30 ]. Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

A Software Cache Autotuning Strategy for Dataflow Computing with UPC++ DepSpawn

  • Fraguela, Basilio B.
  • Andrade, Diego
This is the accepted version of the following article: B. B. Fraguela, D. Andrade. A software cache autotuning strategy for dataflow computing with UPC++ DepSpawn. Computational and Mathematical Methods, 3(6), e1148. November 2021, which has been published in final form at http://dx.doi.org/10.1002/cmm4.1148. This article may be used for noncommercial purposes in accordance with the Wiley Self-Archiving Policy [http://www.wileyauthors.com/self-archiving]., [Abstract] Dataflow computing allows to start computations as soon as all their dependencies are satisfied. This is particularly useful in applications with irregular or complex patterns of dependencies which would otherwise involve either coarse grain synchronizations which would degrade performance, or high programming costs. A recent proposal for the easy development of performant dataflow algorithms in hybrid shared/distributed memory systems is UPC++ DepSpawn. Among the many techniques it applies to provide good performance is a software cache that minimizes the communications among the processes involved. In this article we provide the details of the implementation and operation of this cache and we present an autotuning strategy that simplifies its usage by freeing the user from having to estimate an adequate size for this cache. Rather, the runtime is now able to define reasonably sized caches that provide near optimal behavior., This research was funded by the Ministry of Science and Innovation of Spain (TIN2016-75845-P and PID2019-104184RB-I00, AEI/FEDER/EU, 10.13039/501100011033), and by the Xunta de Galicia co-funded by the European Regional Development Fund (ERDF) under the Consolidation Programme of Competitive Reference Groups (ED431C 2017/04). The authors acknowledge also the support from the Centro Singular de Investigación de Galicia “CITIC,” funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014-2020 Program), by grant ED431G 2019/01. They also acknowledge the Centro de Supercomputación de Galicia (CESGA) for the use of its computers, Xunta de Galicia; ED431C 2017/04, Xunta de Galicia; ED431G/01
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

SeQual: Big Data Tool to Perform Quality Control and Data Preprocessing of Large NGS Datasets

  • Expósito, Roberto R.
  • Galego Torreiro, Roi
  • González-Domínguez, Jorge
[Abstract] This paper presents SeQual, a scalable tool to efficiently perform quality control of large genomic datasets. Our tool currently supports more than 30 different operations (e.g., filtering, trimming, formatting) that can be applied to DNA/RNA reads in FASTQ/FASTA formats to improve subsequent downstream analyses, while providing a simple and user-friendly graphical interface for non-expert users. Furthermore, SeQual takes full advantage of Big Data technologies to process massive datasets on distributed-memory systems such as clusters by relying on the open-source Apache Spark cluster computing framework. Our scalable Spark-based implementation allows to reduce the runtime from more than three hours to less than 20 minutes when processing a paired-end dataset with 251 million reads per input file on an 8-node multi-core cluster., 10.13039/501100004837-Ministry of Science and Innovation of Spain (Grant Number: TIN2016-75845-P and PID2019-104184RB-I00) 10.13039/501100004837-AEI/FEDER/EU (Grant Number: 10.13039/501100011033) 10.13039/501100010801-Xunta de Galicia and FEDER funds (Centro de Investigación de Galicia accreditation 2019–2022 and the Consolidation Program of Competitive Reference Groups) (Grant Number: ED431G 2019/01 and ED431C 2017/04), Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2017/04
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Evaluation of Existing Methods for High-Order Epistasis Detection

  • Ponte-Fernández, Christian
  • González-Domínguez, Jorge
  • Carvajal-Rodriguez, Antonio
  • Martín, María J.
[Abstract] Finding epistatic interactions among loci when expressing a phenotype is a widely employed strategy to understand the genetic architecture of complex traits in GWAS. The abundance of methods dedicated to the same purpose, however, makes it increasingly difficult for scientists to decide which method is more suitable for their studies. This work compares the different epistasis detection methods published during the last decade in terms of runtime, detection power and type I error rate, with a special emphasis on high-order interactions. Results show that in terms of detection power, the only methods that perform well across all experiments are the exhaustive methods, although their computational cost may be prohibitive in large-scale studies. Regarding non-exhaustive methods, not one could consistently find epistasis interactions when marginal effects are absent. If marginal effects are present, there are methods that perform well for high-order interactions, such as BADTrees, FDHE-IW, SingleMI or SNPHarvester. As for false-positive control, only SNPHarvester, FDHE-IW and DCHE show good results. The study concludes that there is no single epistasis detection method to recommend in all scenarios. Authors should prioritize exhaustive methods when sufficient computational resources are available considering the data set size, and resort to non-exhaustive methods when the analysis time is prohibitive., This research was funded by the Ministry of Economy and Competitiveness of Spain (CGL2016-75482-P), Ministry of Science and Innovation of Spain (TIN2016-75845-P and PID2019-104184RB-I00, AEI/FEDER/EU, 10.13039/501100011033), the Xunta de Galicia (Grupo de Referencia Competitiva, ED431C2016-037), the Xunta de Galicia and FEDER funds of the EU (Centro de Investigación de Galicia accreditation 2019-2022, ref. ED431G2019/01), Consolidation Program of Competitive Reference Groups (ED431C 2017/04)and the FPU Program of the Ministry of Education of Spain (FPU16/01333). The authors would like to thank the Supercomputing Center of Galicia (CESGA)for providing access to its supercomputing facilities and assisting with the problems encountered, as well as all of the authors contacted for assistance while using their epistasis detection applications., Xunta de Galicia; ED431C2016-037, Xunta de Galicia; ED431G2019/01, Xunta de Galicia; ED431C 2017/04
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

A SIMD Algorithm for the Detection of Epistatic Interactions of Any Order

  • Ponte-Fernández, Christian
  • González-Domínguez, Jorge
  • Martín, María J.
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] Epistasis is a phenomenon in which a phenotype outcome is determined by the interaction of genetic variation at two or more loci and it cannot be attributed to the additive combination of effects corresponding to the individual loci. Although it has been more than 100 years since William Bateson introduced this concept, it still is a topic under active research. Locating epistatic interactions is a computationally expensive challenge that involves analyzing an exponentially growing number of combinations. Authors in this field have resorted to a multitude of hardware architectures in order to speed up the search, but little to no attention has been paid to the vector instructions that current CPUs include in their instruction sets. This work extends an existing third-order exhaustive algorithm to support the search of epistasis interactions of any order and discusses multiple SIMD implementations of the different functions that compose the search using Intel AVX Intrinsics. Results using the GCC and the Intel compiler show that the 512-bit explicit vector implementation proposed here performs the best out of all of the other implementations evaluated. The proposed 512-bit vectorization accelerates the original implementation of the algorithm by an average factor of 7 and 12, for GCC and the Intel Compiler, respectively, in the scenarios tested., This work is supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00/AEI/10.13039/501100011033), the Xunta de Galicia and FEDER funds of the EU (Centro de Investigación de Galicia accreditation 2019-2022, grant no. ED431G2019/01), Consolidation Program of Competitive Research (grant no. ED431C 2021/30), the FPU Program of the Ministry of Education of Spain (grant no. FPU16/01333), and the Universidade da Coruña/CISUG for funding the open access charge, Xunta de Galicia; ED431G2019/01, Xunta de Galicia; ED431C2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

OpenCNN: A Winograd Minimal Filtering Algorithm Implementation in CUDA

  • Castro, Roberto L.
  • Andrade, Diego
  • Fraguela, Basilio B.
[Abstract] Improving the performance of the convolution operation has become a key target for High Performance Computing (HPC) developers due to its prevalence in deep learning applied mainly to video processing. The improvement is being pushed by algorithmic and implementation innovations. Algorithmically, the convolution can be solved as it is mathematically enunciated, but other methods allow to transform it into a Fast Fourier Transform (FFT) or a GEneral Matrix Multiplication (GEMM). In this latter group, the Winograd algorithm is a state-of-the-art variant that is specially suitable for smaller convolutions. In this paper, we present openCNN, an optimized CUDA C++ implementation of the Winograd convolution algorithm. Our approach achieves speedups of up to 1.76× on Turing RTX 2080Ti and up to 1.85× on Ampere RTX 3090 with respect to Winograd convolution in cuDNN 8.2.0. OpenCNN is released as open-source software., This research was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00, AEI/FEDER/EU, 10.13039/501100011033) and the predoctoral grant of Roberto L. Castro (FPU19/03974). and by the Xunta de Galicia co-founded by the European Regional Development Fund (ERDF) under the Consolidation Programme of Competitive Reference Groups (ED431C 2021/30). CITIC, Centro de Investigación de Galicia ref. ED431G 2019/01, receives financial support from Consellería de Educación, Universidade e Formación Profesional, Xunta de Galicia, through the ERDF (80%) and Secretaría Xeral de Universidades (20%), Xunta de Galicia; ED431C 2021/30, Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

PARamrfinder: detecting allele-specific DNA methylation on multicore clusters

  • Fernández-Fraga, Alejandro
  • González-Domínguez, Jorge
  • Martín, María J.
Financiado para publicación en acceso aberto: CRUE-CSIC, [Abstract]: The discovery of Allele-Specific Methylation (ASM) is an important research field in biology as it regulates genomic imprinting, which has been identified as the cause of some genetic diseases. Nevertheless, the high computational cost of the bioinformatic tools developed for this purpose prevents their application to large-scale datasets. Hence, much faster tools are required to further progress in this research field. In this work we present PARamrfinder, a parallel tool that applies a statistical model to identify ASM in data from high-throughput short-read bisulfite sequencing. It is based on the state-of-the-art sequential tool amrfinder, which is able to detect ASM at regional level from Bisulfite Sequencing (BS-Seq) experiments in the absence of Single Nucleotide Polymorphism information. PARamrfinder provides the same Allelically Methylated Regions as amrfinder but at significantly reduced runtime thanks to exploiting the compute capabilities of common multicore CPU clusters and MPI RMA operations to attain an efficient dynamic workload balance. As an example, our tool is up to 567 times faster for real data experiments on a cluster with 8 nodes, each one containing two 16-core processors. The source code of PARamrfinder, as well as a reference manual, is available at https://github.com/UDC-GAC/PARamrfinder., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 and PID2022-136435NB-I00 / AEI / 10.13039/501100011033), PID2022 also funded by “ERDF A way of making Europe”. It was also supported by the Ministry of Universities of Spain under grant FPU21/03408, and by Xunta de Galicia and FEDER funds (Centro de Investigación de Galicia accreditation 2019–2022 and Consolidation Program of Competitive Reference Groups, under Grants ED431G 2019/01 and ED431C 2021/30, respectively)., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Improved cooperative Ant Colony Optimization for the solution of binary combinatorial optimization applications

  • Prado-Rodríguez, Roberto
  • González, Patricia
  • Banga, Julio R.
  • Doallo, Ramón
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: Binary combinatorial optimization plays a crucial role in various scientific and engineering fields. While deterministic approaches have traditionally been used to solve these problems, stochastic methods, particularly metaheuristics, have gained popularity in recent years for efficiently handling large problem instances. Ant Colony Optimization (ACO) is among the most successful metaheuristics and is frequently employed in non-binary combinatorial problems due to its adaptability. Although for binary combinatorial problems ACO can suffer from issues such as rapid convergence to local minima, its eminently parallel structure means that it can be exploited to solve large and complex problems also in this field. In order to provide a versatile ACO implementation that achieves competitive results across a wide range of binary combinatorial optimization problems, we introduce a parallel multicolony strategy with an improved cooperation scheme to maintain search diversity. We evaluate our proposal (Binary Parallel Cooperative ACO, BiPCACO) using a comprehensive benchmark framework, showcasing its performance and, most importantly, its flexibility as a successful all-purpose solver for binary combinatorial problems., RPR, PGG and RDB acknowledges funding from Grants PID2019-104184RB-I00 and PID2022-136435NB-I00, funded by MCIN/AEI/10.13039/501100011033, PID2022 also funded by ‘ERDF A way of making Europe’, EU; Xunta de Galicia and FEDER funds of the EU (Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). JRB acknowledges funding from the Ministry of Science and Innovation of Spain MCIN/AEI/10.13039/501100011033 through grant PID2020-117271RB- C22 (BIODYNAMICS). Authors also acknowledge the Galician Supercom- puting Center (CESGA) for the access to its facilities. Funding for open access charge: Universidade da Coruña/CISUG, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Floating Point Calculation of the Cube Function on FPGAs

  • Osorio, Roberto
© 2023 IEEE. This version of the paper has been accepted for publication. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The final published paper is available online at: https://doi.org/10.1109/TPDS.2022.3220039, [Abstract]: Specialized arithmetic units allow fast and efficient computation of lesser used mathematical functions. The overall impact of those units would be negligible in a general purpose processor, as added circuitry makes chips more complex despite most software would seldom make use of it. On the opposite side, custom computing machines are built for a specific task, and they can always benefit from specialized units if they are available. In this work, floating point architectures are proposed for computing the cube on Intel and Xilinx FPGAs. Those implementations reduce the cost and latency compared to using simple floating point multiplications and squarers., This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033), and by Xunta de Galicia and FEDER funds of the EU (Centro de Investigaci´on de Galicia accreditation 2019–2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30)., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

A Highly Optimized Skeleton for Unbalanced and Deep Divide-And-Conquer Algorithms on Multi-Core Clusters

  • Álvarez Martínez, Millán
  • Fraguela, Basilio B.
  • Cabaleiro, José Carlos
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG , [Abstract] Efficiently implementing the divide-and-conquer pattern of parallelism in distributed memory systems is very relevant, given its ubiquity, and difficult, given its recursive nature and the need to exchange tasks and data among the processors. This task is noticeably further complicated in the presence of multi-core systems, where hybrid parallelism must be exploited to attain the best performance, and when unbalanced and deep workloads are considered, as additional measures must be taken to load balance and avoid deep recursion problems. In this manuscript a parallel skeleton that fulfills all these requirements while providing high levels of usability is presented. In fact, the evaluation shows that our proposal is on average 415.32% faster than MPI codes and 229.18% faster than MPI + OpenMP benchmarks, while offering an average improvement in the programmability metrics of 131.04% over MPI alternatives and 155.18% over MPI + OpenMP solutions., This research was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 and PID2019-104834GB-I00, AEI/FEDER/EU, 10.13039/501100011033) and the predoctoral Grant of Millán Álvarez Ref. BES-2017-081320), and by the Xunta de Galicia co-founded by the European Regional Development Fund (ERDF) under the Consolidation Programme of Competitive Reference Groups (ED431C 2018/19 and ED431C 2021/30). We acknowledge also the support from the Centro Singular de Investigación de Galicia “CITIC” and the Centro Singular de Investigación en Tecnoloxías Intelixentes “CiTIUS”, funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014-2020 Program), by Grants ED431G 2019/01 and ED431G 2019/04. We also acknowledge the Centro de Supercomputación de Galicia (CESGA). Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature, Xunta de Galicia; ED431C 2018/19, Xunta de Galicia; ED431C 2021/30, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431G 2019/04
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

An Efficient Ant Colony Optimization Framework for HPC Environments

  • González, Patricia
  • Osorio, Roberto
  • Pardo, Xoán C.
  • Banga, Julio R.
  • Doallo, Ramón
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] Combinatorial optimization problems arise in many disciplines, both in the basic sciences and in applied fields such as engineering and economics. One of the most popular combinatorial optimization methods is the Ant Colony Optimization (ACO) metaheuristic. Its parallel nature makes it especially attractive for implementation and execution in High Performance Computing (HPC) environments. Here we present a novel parallel ACO strategy making use of efficient asynchronous decentralized cooperative mechanisms. This strategy seeks to fulfill two objectives: (i) acceleration of the computations by performing the ants’ solution construction in parallel; (ii) convergence improvement through the stimulation of the diversification in the search and the cooperation between different colonies. The two main features of the proposal, decentralization and desynchronization, enable a more effective and efficient response in environments where resources are highly coupled. Examples of such infrastructures include both traditional HPC clusters, and also new distributed environments, such as cloud infrastructures, or even local computer networks. The proposal has been evaluated using the popular Traveling Salesman Problem (TSP), as a well-known NP-hard problem widely used in the literature to test combinatorial optimization methods. An exhaustive evaluation has been carried out using three medium and large size instances from the TSPLIB library, and the experiments show encouraging results with superlinear speedups compared to the sequential algorithm (e.g. speedups of 18 with 16 cores), and a very good scalability (experiments were performed with up to 384 cores improving execution time even at that scale)., This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033), and by Xunta de Galicia and FEDER funds of the EU (Centro de Investigación de Galicia accreditation 2019–2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). JRB acknowledges funding from the Ministry of Science and Innovation of Spain MCIN / AEI / 10.13039/501100011033 through grant PID2020-117271RB-C22 (BIODYNAMICS), and from MCIN / AEI / 10.13039/501100011033 and “ERDF A way of making Europe” through grant DPI2017-82896-C2-2-R (SYNBIOCONTROL). Authors also acknowledge the Galician Supercomputing Center (CESGA) for the access to its facilities. Funding for open access charge: Universidade da Coruña/CISUG, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Spark Implementation of the Enhanced Scatter Search Metaheuristic: Methodology and Assessment

  • Pardo, Xoán C.
  • Argüeso-Alejandro, Pablo
  • González, Patricia
  • Banga, Julio R.
  • Doallo, Ramón
This ACCEPTED VERSION of the article: X.C. Pardo, P. Argüeso-Alejandro, P. González, J.R. Banga, R. Doallo (2020). 'Spark Implementation of the Enhanced Scatter Search Metaheuristic: Methodology and Assessment’ has been accepted for publication in: Swarm and Evolutionary Computation (ISSN 2210-6502), 59:100748. The Version of Record is available online at https://doi.org/10.1016/j.swevo.2020.100748., [Abstract] Optimization problems arise nowadays in all disciplines, not only in the scientific area but also in the field of engineering or economics, and in many others. Currently, challenging optimization problems require solution methods that consume a significant amount of computational resources. The application of High-Performance Computing techniques is a common approach to obtain efficient implementations in traditional parallel computing systems. However, more recent approaches are exploring distributed programming frameworks developed in recent years to achieve efficient computations on clusters and cloud systems. In this paper we present a parallel implementation of the enhanced Scatter Search metaheuristic using Spark. The parallel program was obtained as a particularization of a general software framework we developed to support different realisations of the Scatter Search metaheuristic. The aim of this paper is to provide helpful guidance to readers interested in applying, or developing their own, parallel metaheuristics to solve challenging problems in the Cloud. With the twofold objective of demonstrating the potential of the parallelization with Spark and also of studying the factors that influence the performance of the solution, the proposal has been thoroughly evaluated on two different platforms, a cluster and a cloud platform, using a representative set of parameter estimation problems in the field of Computational Systems Biology., This work was supported by the Ministry of Science and Innovation of Spain (DPI2017-82896-C2-2-R, TIN2016-75845-P and PID2019-104184RB-I00, AEI/FEDER/UE, 10.13039/501100011033); and by Xunta de Galicia and FEDER funds (Centro de Investigación de Galicia accreditation 2019-2022, ref. ED431G 2019/01, as well as Consolidation Program of Competitive Reference Groups, ref. ED431C 2017/04), Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2017/04
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

ScalaParBiBit: Scaling the Binary Biclustering in Distributed-Memory Systems

  • Fraguela, Basilio B.
  • Andrade, Diego
  • González-Domínguez, Jorge
[Abstract] Biclustering is a data mining technique that allows us to find groups of rows and columns that are highly correlated in a 2D dataset. Although there exist several software applications to perform biclustering, most of them suffer from a high computational complexity which prevents their use in large datasets. In this work we present ScalaParBiBit, a parallel tool to find biclusters on binary data, quite common in many research fields such as text mining, marketing or bioinformatics. ScalaParBiBit takes advantage of the special characteristics of these binary datasets, as well as of an efficient parallel implementation and algorithm, to accelerate the biclustering procedure in distributed-memory systems. The experimental evaluation proves that our tool is significantly faster and more scalable that the state-of-the-art tool ParBiBit in a cluster with 32 nodes and 768 cores. Our tool together with its reference manual are freely available at https://github.com/fraguela/ScalaParBiBit., This research was supported by the Ministry of Science and Innovation of Spain (TIN2016-75845-P and PID2019-104184RB-I00, AEI/FEDER/EU, 10.13039/ 501100011033), and by the Xunta de Galicia co-founded by the European Regional Development Fund (ERDF) under the Consolidation Programme of Competitive Reference Groups (ED431C 2017/04). We acknowledge also the support from the Centro Singular de Investigación de Galicia “CITIC”, funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014-2020 Program), by grant ED431G 2019/01. We also acknowledge the Centro de Supercomputación de Galicia (CESGA) for the usage of their resources, Xunta de Galicia; ED431C 2017/04, Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

CUDA acceleration of MI-based feature selection methods

  • Beceiro, Bieito
  • González-Domínguez, Jorge
  • Morán-Fernández, Laura
  • Bolón-Canedo, Verónica
  • Touriño, Juan
[Abstract]: Feature selection algorithms are necessary nowadays for machine learning as they are capable of removing irrelevant and redundant information to reduce the dimensionality of the data and improve the quality of subsequent analyses. The problem with current feature selection approaches is that they are computationally expensive when processing large datasets. This work presents parallel implementations for Nvidia GPUs of three highly-used feature selection methods based on the Mutual Information (MI) metric: mRMR, JMI and DISR. Publicly available code includes not only CUDA implementations of the general methods, but also an adaptation of them to work with low-precision fixed point in order to further increase their performance on GPUs. The experimental evaluation was carried out on two modern Nvidia GPUs (Turing T4 and Ampere A100) with highly satisfactory results, achieving speedups of up to 283x when compared to state-of-the-art C implementations., This work was supported by grants PID2019-104184RB-I00, PID- 2019-109238GB-C22, TED2021-130599A-I00 and PID2022-136435NB- I00, funded by MCIN/AEI/ 10.13039/501100011033 (TED2021 also funded by “NextGenerationEU”/PRTR and PID2022 by “ERDF A way of making Europe”, EU). Grant TSI-100925-2023-1, funded by Ministry for Digital Transformation and Civil Service. FPU predoctoral grant of Bieito Beceiro ref. FPU20/00997, funded by the Ministry of Sci- ence, Innovation and Universities. We gratefully thank the Galician Supercomputing Center (CESGA) for the access granted to its super- computing resources. Funding for open access charge: Universidade da Coruña/CISUG., Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

A comprehensive handball dynamics dataset for game situation classification

  • Mures, Omar A.
  • Taibo, Javier
  • Padrón, Emilio J.
  • Iglesias-Guitian, Jose A.
[Abstract] This article presents a comprehensive dataset of labeled game situations obtained from multiple professional handball matches, which corresponds to the research paper entitled “PlayNet: Real-time Handball Play Classification with Kalman Embeddings and Neural Networks” [1]. The dataset encompasses approximately 11 hours of footage from five handball games played in two different arenas, resulting in around 1 million data frames. Each frame has been meticulously labeled using seven distinct game situation classes (left and right attacks, left and right transitions, left and right penalties, and timeouts). Notably, the dataset does not contain video frames, but provides a synthetic normalized representation of each frame. This representation includes information about player, referee, and ball positions, as well as player and referee velocities, for every labeled game situation. We obtained said details automatically by using an object detector to infer the positions of players, referees, and the ball in each frame. After tracking the detected agent positions across frames, the extracted coordinates underwent normalization through a “bird's eye” perspective transform, ensuring that the data remained unaffected by variations in camera configurations across different arenas. Finally, a Kalman filter was applied to improve the robustness of player positions and derive their velocities. The labeling process was performed by domain experts employing a custom system designed to annotate game situations, considering the play type and its contextual setting. In conclusion, researchers can utilize this dataset for several purposes: game analysis, automated broadcasting, or game summarization. Furthermore, this dataset can contribute to a broader understanding of the relationship between player dynamics and game situations, shedding light on the level of granularity required for accurately classifying them., This work has been developed under the European Innovation Council [Pilot No 954040], Xunta de Galicia [ED431F 2021/11, ED431G 2019/01, ED431C 2021/30], Spanish Ministry of Science and Innovation [MCIN/AEI/10.13039/501100011033, AEI/RYC2018-025385-I, PID2019- 104184RB-I00], and Jose A. Iglesias-Guitian also acknowledges the UDC-Inditex InTalent programme. Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED431F 2021/11, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

PATO: genome-wide prediction of lncRNA-DNA triple helices

  • Amatria Barral, Iñaki
  • González-Domínguez, Jorge
  • Touriño, Juan
[Abstract]: Motivation: Long non-coding RNA (lncRNA) plays a key role in many biological processes. For instance, lncRNA regulates chromatin using different molecular mechanisms, including direct RNA-DNA hybridization via triplexes, cotranscriptional RNA-RNA interactions, and RNA-DNA binding mediated by protein complexes. While the functional annotation of lncRNA transcripts has been widely studied over the last 20 years, barely a handful of tools have been developed with the specific purpose of detecting and evaluating lncRNA-DNA triple helices. What is worse, some of these tools have nearly grown a decade old, making new triplex-centric pipelines depend on legacy software that cannot thoroughly process all the data made available by next-generation sequencing (NGS) technologies. Results: We present PATO, a modern, fast, and efficient tool for the detection of lncRNA-DNA triplexes that matches NGS processing capabilities. PATO enables the prediction of triple helices at the genome scale and can process in as little as 1 h more than 60 GB of sequence data using a two-socket server. Moreover, PATO's efficiency allows a more exhaustive search of the triplex-forming solution space, and so PATO achieves higher levels of prediction accuracy in far less time than other tools in the state of the art. Availability and implementation: Source code, user manual, and tests are freely available to download under the MIT License at https://github.com/UDC-GAC/pato., Xunta de Galicia; ED431C 2021/30, This work was supported by the Ministry of Science and Innovation of Spain [PID2019-104184RB-I00/AEI/10.13039/501100011033]; by the Ministry of Education of Spain [FPU21/00491]; and by Xunta de Galicia [Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30]. Funding for open access charge was provided by Universidade da Coruña/CISUG., Funding for open access charge was provided by Universidade da Coruña/CISUG.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

A pipeline architecture for feature-based unsupervised clustering using multivariate time series from HPC jobs

  • Enes, Jonatan
  • Expósito, Roberto R.
  • Fuentes Rodríguez, Jose
  • López Cacheiro, Javier
  • Touriño, Juan
[Abstract]: Time series are key across industrial and research areas for their ability to model behaviour across time, making them ideal for a wide range of use cases such as event monitoring, trend prediction or anomaly detection. This is even more so due to the increasing monitoring capabilities in many areas, with the subsequent massive data generation. But it is also interesting to consider the potential of time series for Machine Learning processing, often fused with Big Data, to search for useful information and solve real-world problems. However, time series can be studied individually, representing a single entity or variable to be analysed, or in a grouped fashion, to study and represent a more complex entity or scenario. In this latter case we are dealing with multivariate time series, which usually imply different approaches when dealt with. In this paper, we present a pipeline architecture to process and cluster multiple groups of multivariate time series. To implement this, we apply a multi-process solution composed by a feature-based extraction stage, followed by a dimension reduction, and finally, several clustering algorithms. The pipeline is also highly configurable in terms of the stage techniques to be used, allowing to perform a search with several combinations for the most promising results. The pipeline has been experimentally applied to batches of HPC jobs from different users of a supercomputer, with the multivariate time series coming from the monitoring of several node resource metrics. The results show how it is possible to apply this multi-process information fusion to create different meaningful clusters from the batches, using only the time series, without any labelling information, thus being an unsupervised scenario. Optionally, the pipeline also supports an outlier detection stage to find and separate jobs that are radically different when compared to others on a dataset. These outliers can be removed for a better clustering, and later reviewed looking for anomalies, or if numerous, fed back to the pipeline to identify possible groupings. The results also include some outliers found in the experiments, as well as scenarios where they are clustered, or ignored and not removed at all. In addition, by leveraging Big Data technologies like Spark, the pipeline is proven to be scalable by working with up to hundreds of jobs and thousands of time series., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30, This research was funded by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00/AEI/10.13039/501100011033), and by Xunta de Galicia, Spain and FEDER funds of the European Union (Centro de Investigación de Galicia accreditation 2019–2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). Funding for open access charge: Universidade da Coruña/CISUG.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

SeQual-Stream: approaching stream processing to quality control of NGS datasets

  • Castellanos Rodríguez, Óscar
  • Expósito, Roberto R.
  • Touriño, Juan
[Abstract]: Background Quality control of DNA sequences is an important data preprocessing step in many genomic analyses. However, all existing parallel tools for this purpose are based on a batch processing model, needing to have the complete genetic dataset before processing can even begin. This limitation clearly hinders quality control performance in those scenarios where the dataset must be downloaded from a remote repository and/or copied to a distributed file system for its parallel processing. Results In this paper we present SeQual-Stream, a streaming tool that allows performing multiple quality control operations on genomic datasets in a fast, distributed and scalable way. To do so, our approach relies on the Apache Spark framework and the Hadoop Distributed File System (HDFS) to fully exploit the stream paradigm and accelerate the preprocessing of large datasets as they are being downloaded and/or copied to HDFS. The experimental results have shown significant improvements in the execution times of SeQual-Stream when compared to a batch processing tool with similar quality control features, providing a maximum speedup of 2.7 when processing a dataset with more than 250 million DNA sequences, while also demonstrating good scalability features. Conclusion Our solution provides a more scalable and higher performance way to carry out quality control of large genomic datasets by taking advantage of stream processing features. The tool is distributed as free open-source software released under the GNU AGPLv3 license and is publicly available to download at https://github.com/UDC-GAC/SeQual-Stream., Grants PID2019-104184RB-I00 and PID2022-136435NB-I00, funded by MCIN/AEI/10.13039/501100011033, PID2022 also funded by “ERDF A way of making Europe”, EU. Grant ED431C 2021/30, funded by Xunta de Galicia under the Consolidation Program of Competitive Reference Groups. Predoctoral grant of Oscar Castellanos-Rodriguez ref. ED481A 2022/067, also funded by Xunta de Galicia. The funding agencies did not participate in the design of the study and collection, analysis, and interpretation of data and in writing the manuscript., Xunta de Galicia; ED431C 2021/30, Xunta de Galicia; ED481A 2022/067
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

A new thread-level speculative automatic parallelization model and library based on duplicate code execution

  • Álvarez Martínez, Millán
  • Fraguela, Basilio B.
  • Cabaleiro, José Carlos
  • Rivera, Francisco F.
Funding for open access charge: Universidade da Coruña/CISUG, Loop-efficient automatic parallelization has become increasingly relevant due to the growing number of cores in current processors and the programming effort needed to parallelize codes in these systems efficiently. However, automatic tools fail to extract all the available parallelism in irregular loops with indirections, race conditions or potential data dependency violations, among many other possible causes. One of the successful ways to automatically parallelize these loops is the use of speculative parallelization techniques. This paper presents a new model and the corresponding C++ library that supports the speculative automatic parallelization of loops in shared memory systems, seeking competitive performance and scalability while keeping user effort to a minimum. The primary speculative strategy consists of redundantly executing chunks of loop iterations in a duplicate fashion. Namely, each chunk is executed speculatively in parallel to obtain results as soon as possible and sequentially in a different thread to validate the speculative results. The implementation uses C++11 threads and it makes intensive use of templates and advanced multithreading techniques. An evaluation based on various benchmarks confirms that our proposal provides a competitive level of performance and scalability., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This research was supported by Grants PID2019-104184RB-I00, PID2019-104834GB-I00, PID2022-141623NB-I00, and PID2022-136435NB-I00, funded by MCIN/AEI/ 10.13039/501100011033, PID2022 also funded by "ERDF A way of making Europe", EU, and the predoctoral Grant of Millán Álvarez Ref. BES-2017-081320, and by the Xunta de Galicia co-founded by the European Regional Development Fund (ERDF) under the Consolidation Programme of Competitive Reference Groups (ED431C 2021/30 and ED431C 2022/16). Funding for open access charge: Universidade da Coruña/CISUG. We also acknowledge the support from the Centro Singular de Investigación de Galicia "CITIC" and the Centro Singular de Investigación en Tecnoloxías Intelixentes "CiTIUS", funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014-2020 Program), by grants ED431G 2019/01 and ED431G 2019/04. We also acknowledge the Centro de Supercomputación de Galicia (CESGA)., Xunta de Galicia; ED431C 2021/30, Xunta de Galicia; ED431C 2022/16, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431G 2019/04
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Interactive Visualization of Large Point Clouds Using an Autotuning Multiresolution Out-Of-Core Strategy

  • Teijeiro, Diego
  • Amor, Margarita
  • Doallo, Ramón
  • Deibe, David
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: Due to the increasingly large amount of data acquired into point clouds, from LiDAR (Light Detection and Ranging) sensors and 2D/3D sensors, massive point clouds processing has become a topic with high interest for several fields. Current client-server applications usually use multiresolution out-of-core proposals; nevertheless, the construction of the data structures required is very time-consuming. Furthermore, these multiresolution approaches present problems regarding point density changes between different levels of detail and artifacts due to the rendering of elements entering and leaving the field of view. We present an autotuning multiresolution out-of-core strategy to avoid these problems. Other objectives are reducing loading times while maintaining low memory requirements, high visualization quality and achieving interactive visualization of massive point clouds. This strategy identifies certain parameters, called performance parameters, and defines a set of premises to obtain the goals mentioned above. The optimal parameter values depend on the number of points per cell in the multiresolution structure. We test our proposal in our web-based visualization software designed to work with the structures and storage format used and display massive point clouds achieving interactive visualization of point clouds with more than 27 billion points., Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033); Galician Government under the Consolidation Program of Competitive Research Units (Ref. ED431C 2021/30); Centro de Investigación de Galicia ”CITIC”; Government of Galicia; European Union (European Regional Development Fund- Galicia 2014-2020 Program by grant ED431G 2019/01); Government of Galicia and the European Social Fund (ESF) of the European Union (predoctoral fellowship ref. ED481A-2019/231 to D.T.); Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED431C 2021/30, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED481A-2019/231
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Fiuncho: a program for any-order epistasis detection in CPU clusters

  • Ponte-Fernández, Christian
  • González-Domínguez, Jorge
  • Martín, María J.
Financiado para publicación en acceso aberto: CRUE/CISUG, [Abstract]: Epistasis can be defined as the statistical interaction of genes during the expression of a phenotype. It is believed that it plays a fundamental role in gene expression, as individual genetic variants have reported a very small increase in disease risk in previous Genome-Wide Association Studies. The most successful approach to epistasis detection is the exhaustive method, although its exponential time complexity requires a highly parallel implementation in order to be used. This work presents Fiuncho, a program that exploits all levels of parallelism present in x86_64 CPU clusters in order to mitigate the complexity of this approach. It supports epistasis interactions of any order, and when compared with other exhaustive methods, it is on average 358, 7 and 3 times faster than MDR, MPI3SNP and BitEpi, respectively., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033), the Xunta de Galicia and FEDER funds of the EU (CITIC-Centro de Investigación de Galicia accreditation 2019–2022, Grant no. ED431G 2019/01), Consolidation Program of Competitive Research (Grant no. ED431C 2021/30), and the FPU Program of the Ministry of Education of Spain (Grant no. FPU16/01333)., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

PlayNet: real-time handball play classification with Kalman embeddings and neural networks

  • Mures, Omar A.
  • Taibo, Javier
  • Padrón, Emilio J.
  • Iglesias-Guitian, Jose A.
Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature, [Abstract] Real-time play recognition and classification algorithms are crucial for automating video production and live broadcasts of sporting events. However, current methods relying on human pose estimation and deep neural networks introduce high latency on commodity hardware, limiting their usability in low-cost real-time applications. We present PlayNet, a novel approach toreal-time handball play classification. Our method is based on Kalman embeddings, a new low-dimensional representation for game states that enables efficient operation on commodity hardware and customized camera layouts. Firstly, we leverage Kalman filtering to detect and track the main agents in the playing field, allowing us to represent them in a single normalized coordinate space. Secondly,weutilize a neural network trained in nonlinear dimensionality reduction through fuzzy topological data structure analysis. As a result, PlayNet achieves real-time play classification with under 55 ms of latency on commodity hardware, making it a promising addition to automated live broadcasting and game analysis pipelines., This work has been developed under the European Innovation Council Pilot No 954040. This work was supported also by ED431F 2021/11 and ED431G 2019/01 funded by Xunta de Galicia. Emilio J. Padrón’s work was also partially supported through the research projects PID2019-104184RB-I00 funded by MCIN/AEI/10.13039/501100011033, and ED431C 2021/30. Jose A. Iglesias-Guitian also acknowledges the UDC-Inditex InTalent programme and the Spanish Ministry of Science and Innovation (AEI/RYC2018-025385-I)., Xunta de Galicia; ED431F 2021/11, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Cryptic diversity and phylogeographic patterns of Mediodactylus species in the Eastern Mediterranean region

  • Kotsakiozi, Panayiota
  • Antoniou, Aglaia
  • Psonis, Nikolaos
  • Sagonas, Kostas
  • Karameta, Emmanouela
  • Ilgaz, Çetin
  • Kumlutas, Yusuf
  • Aziz, Avcı
  • Jablonski, Daniel
  • Darriba, Diego
Code used for analyses is included in the Supp Material. Genomic data produced have been deposited in SRA NCBI. The Radseq data used in the analyses are available on the NCBI SRA in demultiplexed form, under BioProject number PRJNA1051519 and BioSample accessions SAMN38777126- SAMN38777219., Versión aceptada. ©2024 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/ licenses/bync-nd/4.0/. This version of the article has been accepted for publication in Journal of Controlled Release. The Version of Record is available online at https://doi.org/10.1016/j.ympev.2024.108091, [Abstract]: Cryptic diversity poses a great obstacle in our attempts to assess the current biodiversity crisis and may hamper conservation efforts. The gekkonid genus Mediodactylus, a well-known case of hidden species and genetic diversity, has been taxonomically reclassified several times during the last decade. Focusing on the Mediterranean populations, a recent study within the M. kotschyi species complex using classic mtDNA/nuDNA markers suggested the existence of five distinct species, some being endemic and some possibly threatened, yet their relationships have not been fully resolved. Here, we generated genome-wide SNPs (using ddRADseq) and applied molecular species delimitation approaches and population genomic analyses to further disentangle these relationships. Τhe most extensive nuclear dataset, so far, encompassing 2,360 loci and ∼ 699,000 bp from across the genome of Mediodactylus gecko, enabled us to resolve previously obscure phylogenetic relationships among the five, recently elevated, Mediodactylus species and to support the hypothesis that the taxon includes several new, undescribed species. Population genomic analyses within each of the proposed species showed strong genetic structure and high levels of genetic differentiation among populations., This study was part of a broader research project entitled “Adding more Ecology and Genomics in understanding of the biological Diversity: the role of islands as natural laboratories'' and was funded by NSFR 2007-2013 Program for the development, European Social Fund, operational program, education and life learning Ministry of Education and Religious Affairs, managing authority, Co-financed by Greece and The European Union. A.S. was financially supported by the European Union (EU) under Grant Agreement No 101,087,081 (Comp-Biodiv-GR). DD was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00/AEI/ https://doi-org.accedys.udc.es/10.13039/501100011033) and by the Xunta de Galicia and FEDER funds of the EU under the Centro de Investigación de Galicia accreditation 2019-2022 (ED431G 2019/01)., Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Efficient high-precision integer multiplication on the GPU

  • Pérez Diéguez, Adrián
  • Amor, Margarita
  • Doallo, Ramón
  • Nukada, Akira
  • Matsuoka, Satoshi
Dieguez AP, Amor M, Doallo R, Nukada A, Matsuoka S. Efficient high precision integer multiplication on the GPU. The International Journal of High Performance Computing Applications. 2022;36(3):356-369.© The Author(s) 2022. Publisher: SAGE Publications. https://doi.org/10.1177/10943420221077964, [Abstract]: The multiplication of large integers, which has many applications in computer science, is an operation that can be expressed as a polynomial multiplication followed by a carry normalization. This work develops two approaches for efficient polynomial multiplication: one approach is based on tiling the classical convolution algorithm, but taking advantage of new CUDA architectures, a novelty approach to compute the multiplication using integers without accuracy lossless; the other one is based on the Strassen algorithm, an algorithm that multiplies large polynomials using the FFT operation, but adapting the fastest FFT libraries for current GPUs and working on the complex field. Previous studies reported that the Strassen algorithm is an effective implementation for “large enough” integers on GPUs. Additionally, most previous studies do not examine the implementation of the carry normalization, but this work describes a parallel implementation for this operation. Our results show the efficiency of our approaches for short, medium, and large sizes., The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work has been supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00), by the Galician Government and FEDER funds under the Consolidation Program of Competitive Reference Groups (UDC/GI-000265, ref. ED431C 2021/30), by the Consolidation Program of Competitive Research Units (ED431G2019/01), and by the FPU Program of the Ministry of Education of Spain (FPU14/02801). It is also partially supported by JST CREST [JPMJCR1303 and JPMJCR1687] and NVIDIA GPU Center of Excellence and conducted as research activities of AIST-TokyoTech Real World Big-Data Computation Open Innovation Laboratory (RWBC-OIL)., Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Multistage strategy for ground point filtering on large-scale datasets

  • Teijeiro, Diego
  • Amor, Margarita
  • Buján, Sandra
  • Richter, Rico
  • Döllner, Jürgen
The point clouds and LiDAR datasets used in this work belong to the LiDAR-PNOA data repository, region of Navarra, and were provided by Gobierno de Navarra. Dataset license: LiDAR-PNOA-cob2 2017 CC-BY 4.0 scne.es., [Abstract]: Ground point filtering on national-level datasets is a challenge due to the presence of multiple types of landscapes. This limitation does not simply affect to individual users, but it is in particular relevant for those national institutions in charge of providing national-level Light Detection and Ranging (LiDAR) point clouds. Each type of landscape is typically better filtered by different filtering algorithms or parameters; therefore, in order to get the best quality classification, the LiDAR point cloud should be divided by the landscape before running the filtering algorithms. Despite the fact that the manual segmentation and identification of the landscapes can be very time intensive, only few studies have addressed this issue. In this work, we present a multistage approach to automate the identification of the type of landscape using several metrics extracted from the LiDAR point cloud, matching the best filtering algorithms in each type of landscape. An additional contribution is presented, a parallel implementation for distributed memory systems, using Apache Spark, that can achieve up to 34 x of speedup using 12 compute nodes., We wish to acknowledge the support received from the Centro de Investigación de Galicia ”CITIC”, funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014–2020 Program), by grant ED431G 2019/01. This research was funded by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00/AEI/10.13039/501100011033), by the Galician Government under the Consolidation Program of Competitive Research Units (Ref. ED431C 2021/30) and by grant PID2022-136435NB-I00, funded by MCIN/AEI/ 10.13039/501100011033 and by "ERDF A way of making Europe", EU. Diego Teijeiro received financial support from Xunta de Galicia and the European Social Fund (ESF) of the European Union (predoctoral fellowship ref. ED481A-2019/231). Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30, Xunta de Galicia; ED481A-2019/231
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

PyToxo: a Python tool for calculating penetrance tables of high-order epistasis models

  • González-Seoane, Borja
  • Ponte-Fernández, Christian
  • González-Domínguez, Jorge
  • Martín, María J.
[Abstract] Background Epistasis is the interaction between different genes when expressing a certain phenotype. If epistasis involves more than two loci it is called high-order epistasis. High-order epistasis is an area under active research because it could be the cause of many complex traits. The most common way to specify an epistasis interaction is through a penetrance table. Results This paper presents PyToxo, a Python tool for generating penetrance tables from any-order epistasis models. Unlike other tools available in the bibliography, PyToxo is able to work with high-order models and realistic penetrance and heritability values, achieving high-precision results in a short time. In addition, PyToxo is distributed as open-source software and includes several interfaces to ease its use. Conclusions PyToxo provides the scientific community with a useful tool to evaluate algorithms and methods that can detect high-order epistasis to continue advancing in the discovery of the causes behind complex diseases., This study and publication costs were funded by the Ministry of Science and Innovation of Spain (grant PID2019-104184RB-I00/AEI/10.13039/501100011033) and by Xunta de Galicia and FEDER funds of the EU (CITIC-Centro de Investigación de Galicia accreditation, grant ED431G 2019/01; Consolidation Program of Competitive Reference Groups, grant ED431C 2021/30). CP was funded by the Ministry of Education of Spain (grant FPU16/01333). The funders did not play any role in the design of the study, the collection, analysis, and interpretation of data, or in writing of the manuscript, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

MPI-dot2dot: A Parallel Tool to Find DNA Tandem Repeats on Multicore Clusters

  • González-Domínguez, Jorge
  • Martín Martínez, José Manuel
  • Expósito, Roberto R.
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] Tandem Repeats (TRs) are segments that occur several times in a DNA sequence, and each copy is adjacent to other. In the last few years, TRs have gained significant attention as they are thought to be related with certain human diseases. Therefore, identifying and classifying TRs have become a highly important task in bioinformatics in order to analyze their disorders and relationships with illnesses. Dot2dot, a tool recently developed to find TRs, provides more accurate results than the previous state-of-the-art, but it requires a long execution time even when using multiple threads. This work presents MPI-dot2dot, a novel version of this tool that combines MPI and OpenMP so that it can be executed in a cluster of multicore nodes and thus reduces its execution time. The performance of this new parallel implementation has been tested using different real datasets. Depending on the characteristics of the input genomes, it is able to obtain the same biological results as Dot2dot but more than 100 times faster on a 16-node multicore cluster (384 cores). MPI-dot2dot is publicly available to download from https://sourceforge.net/projects/mpi-dot2dot., This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033), and by Xunta de Galicia and FEDER funds (Centro de Investigación de Galicia accreditation 2019-2022 and Consolidation Program of Competitive Reference Groups, under Grants ED431G 2019/01 and ED431C 2021/30, respectively). The authors would like to thank the Galician Supercomputing Center (CESGA) for providing access to the Finis Terrae II supercomputer. Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Land consolidation through parcel exchange among landowners using a distributed Spark-based genetic algorithm

  • Teijeiro, Diego
  • Amor, Margarita
  • Doallo, Ramón
  • Corbelle-Rico, Eduardo
  • Porta, Juan
  • Parapar López, Jorge
Financiado para publicación en acceso aberto: CRUE-CSIC/Springer Nature., [Abstract]: Land consolidation is an essential tool for public administrations to reduce the fragmentation of land ownership. In particular, parcel exchange shows promising potential for restructuring parcel holdings, even more when the number of parcels and owners involved is large. Unfortunately, the number of possible exchange combinations grows very quickly with the number of participating landowners and parcels, with the associated challenge of finding an acceptable solution. In this paper, we present a high-performance solution for parcel exchange based on genetic algorithms. Our proposal, using Apache Spark framework, is based on the exploiting of distributed-memory systems with effortless access in order to reduce the execution time. This also allows increasing the search width through multiple populations that share their advances. This can be achieved without compromising the search depth thanks to the higher amount of resources available from using distributed-memory systems. Our proposal is capable of achieving better solutions in lower amounts of time compared to previous works, showing that genetic algorithms on a high performance system can be used to propose fair parcel exchanges under strict time constraints, even in complex scenarios. The performance achieved allows for fast trial of several options, reducing the time usually needed to perform administrative procedures associated with land fragmentation problems. Specifically, our proposal is capable of combining the benefits of both depth-focused and width-focused multithreaded parallelization. It matches the speedup gains of depth-focused multithreaded parallelization. The width-focused parallelization provides local minimum resilience and fitness value reduction potential. In this paper, multithreading solutions and Spark-based solutions are tested., We would like to thank the anonymous reviewers, whose insightful comments greatly improved the quality of this paper. This research was funded by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033), by Xunta de Galicia and FEDER funds of the EU under the Centro de Investigación de Galicia accreditation 2019-2022 (ED431G 2019/01), as well as under the Consolidation Program of Competitive Reference Groups (UDC/GI-000265, ref ED431C/2021/30) and one of the authors received financial support from Xunta de Galicia and the European Social Fund (ESF) of the European Union (predoctoral fellowship ref. ED481A-2019/231)., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C/2021/30, Xunta de Galicia; ED481A-2019/231
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Serverless-like platform for container-based YARN clusters

  • Castellanos Rodríguez, Óscar
  • Expósito, Roberto R.
  • Enes, Jonatan
  • Taboada, Guillermo L.
  • Touriño, Juan
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: Serverless computing is an emerging paradigm that has gained a lot of relevance in recent years, as it allows users to consume computing resources without worrying about the underlying infrastructure and pay only for what they actually use. Most current services that implement this paradigm typically rely on the Function-as-a-Service (FaaS) model, which works perfectly for simple applications based on stateless functions triggered by specific events. However, these services are not designed to run more complex applications with intricate interactions, usually presenting a significant degree of configuration difficulty and/or low ability to customise the execution environment. They also tend to be designed for short and simple workloads, with some services even limiting their maximum runtime to just a few minutes. In this paper, we present a platform based on Hadoop YARN oriented to the execution of Big Data workloads in a containerised and serverless way, so that the resources allocated to such containers are automatically and dynamically scaled according to their actual usage. An experimental evaluation has been carried out to compare our serverless-like platform with a standard YARN deployment when executing Big Data workloads concurrently. Our results have shown experimental evidence of enhancing both performance and overall resource efficiency, providing runtime reductions and resource usage improvements of up to 41% and 50%, respectively., This work was supported by grants PID2019-104184RB-I00, PDC20 21-121309-I00, TED2021-129177B-I00 and PID2022-136435NB-I00, funded by the Ministry of Science and Innovation of Spain, MCIN/AEI/ 10.13039/501100011033 (PDC2021 and TED2021 also funded by ‘‘NextGenerationEU’’/PRTR, and PID2022 by ‘‘ERDF A way of making Europe’’, EU). It was also supported by Xunta de Galicia, Spain (predoctoral fellowship ED481A 2022/067). Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED481A 2022/067
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Implementation of a motion estimation algorithm for Intel FPGAs using OpenCL

  • Castro, Manuel de
  • Osorio, Roberto
  • López Vilariño, David
  • González-Escribano, Arturo
  • Llanos, Diego R.
Financiado para publicación en acceso aberto: CRUE-CSIC, [Abstract]: Motion Estimation is one of the main tasks behind any video encoder. It is a computationally costly task; therefore, it is usually delegated to specific or reconfigurable hardware, such as FPGAs. Over the years, multiple FPGA implementations have been developed, mainly using hardware description languages such as Verilog or VHDL. Since programming using hardware description languages is a complex task, it is desirable to use higher-level languages to develop FPGA applications.The aim of this work is to evaluate OpenCL, in terms of expressiveness, as a tool for developing this kind of FPGA applications. To do so, we present and evaluate a parallel implementation of the Block Matching Motion Estimation process using OpenCL for Intel FPGAs, usable and tested on an Intel Stratix 10 FPGA. The implementation efficiently processes Full HD frames completely inside the FPGA. In this work, we show the resource utilization when synthesizing the code on an Intel Stratix 10 FPGA, as well as a performance comparison with multiple CPU implementations with varying levels of optimization and vectorization capabilities. We also compare the proposed OpenCL implementation, in terms of resource utilization and performance, with estimations obtained from an equivalent VHDL implementation., Junta de Castilla y León; VA226P20, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30, This work has been funded by the Consejería de Educación of Junta de Castilla y León, Project PROPHET-2 (VA226P20), and Ministerio de Economía, Industria y Competitividad of Spain, European Regional Development Fund (ERDF) program: Project PCAS (TIN2017-88614-R). David L. Vilariño is funded by Ministerio de Economía, Industria y Competitividad of Spain (PID2019-104834 GB-I00). Roberto R. Osorio is funded by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI / 10.13039/501100011033), and by Xunta de Galicia and FEDER funds of the EU (Centro de Investigacion de Galicia accreditation 2019-2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). This work was also supported in part by grant TED2021-130367B-I00 funded by MCIN/AEI/10.13039/501100011033 and by “European Union NextGenerationEU/PRTR”.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

ParRADMeth: Identification of Differentially Methylated Regions on Multicore Clusters

  • Fernández-Fraga, Alejandro
  • González-Domínguez, Jorge
  • Touriño, Juan
© 2023 IEEE. This version of the article has been accepted for publication, after peer review. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The Version of Record is available online at: https://doi.org/10.1109/TCBB.2022.3230473, Versión aceptada final de: A. Fernandez-Fraga, J. Gonzalez-Dominguez and J. Tourino, "ParRADMeth: Identification of Differentially Methylated Regions on Multicore Clusters" in IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 20, no. 03, pp. 2041-2049, 2023. https://doi.org/10.1109/TCBB.2022.3230473, [Abstract]: The discovery of Differentially Methylated (DM) regions is an important research field in biology, as it can help to anticipate the risk of suffering from specific diseases. Nevertheless, the high computational cost of the bioinformatic tools developed for this purpose prevents their application to large-scale datasets. Hence, much faster tools are required to further progress in this research field. In this work we present ParRADMeth, a parallel tool that applies beta-binomial regression for the identification of these DM regions. It is based on the state-of-the-art sequential tool RADMeth, which proved superior biological accuracy compared to counterparts in previous experimental evaluations. ParRADMeth provides the same DM regions as RADMeth but at significantly reduced runtime thanks to exploiting the compute capabilities of common multicore CPU clusters. For example, our tool is up to 189 times faster for real data experiments on a cluster with 16 nodes, each one containing two eight-core processors. The source code of ParRADMeth, as well as a reference manual, are available at https://github.com/UDC-GAC/ParRADMeth., This work was supported in part by the Ministry of Science and Innovation of Spain under Grants PID2019-104184RB-I00 and / AEI / 10.13039/501100011033, and in part by the Xunta de Galicia and FEDER funds (Centro de Investigacion de Galicia accreditation 2019-2022 and Consolidation Program of Competitive Reference Groups) under Grants ED431 G 2019/01 and ED431 C 2021/30., Xunta de Galicia; ED431 G 2019/01, Xunta de Galicia; ED431 C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

BigDEC: A multi-algorithm Big Data tool based on the k-mer spectrum method for scalable short-read error correction

  • Expósito, Roberto R.
  • González-Domínguez, Jorge
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: Despite the significant improvements in both throughput and cost provided by modern Next-Generation Sequencing (NGS) platforms, sequencing errors in NGS datasets can still degrade the quality of downstream analysis. Although state-of-the-art correction tools can provide high accuracy to improve such analysis, they are limited to apply a single correction algorithm while also requiring long runtimes when processing large NGS datasets. Furthermore, current parallel correctors generally only provide efficient support for shared-memory systems lacking the ability to scale out across a cluster of multicore nodes, or they require the availability of specific hardware devices or features. In this paper we present a Big Data Error Correction (BigDEC) tool that overcomes all those limitations by: (1) implementing three different error correction algorithms based on the widely extended k-mer spectrum method; (2) providing scalable performance for large datasets by efficiently exploiting the capabilities of Big Data technologies on multicore clusters based on commodity hardware; (3) supporting two different Big Data processing frameworks (Spark and Flink) to provide greater flexibility to end users; (4) including an efficient, stream-based merge operation to ease downstream processing of the corrected datasets; and (5) significantly outperforming existing parallel tools, being up to 79% faster on a 16-node multicore cluster when using the same underlying correction algorithm. BigDEC is publicly available to download at https://github.com/UDC-GAC/BigDEC., This work was supported by grants PID2019-104184RB-I00 and PID2022-136435NB-I00, funded by the Ministry of Science and Innovation of Spain, MCIN/AEI/10.13039/501100011033 (PID2022 also funded by “ERDF A way of making Europe”, EU). It was also funded by Xunta de Galicia [Consolidation Program of Competitive Reference Groups, grant ED431C 2021/30]. Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED431C 2021/30
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Parallel-FST: A feature selection library for multicore clusters

  • Beceiro, Bieito
  • González-Domínguez, Jorge
  • Touriño, Juan
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: Feature selection is a subfield of machine learning focused on reducing the dimensionality of datasets by performing a computationally intensive process. This work presents Parallel-FST, a publicly available parallel library for feature selection that includes seven methods which follow a hybrid MPI/multithreaded approach to reduce their runtime when executed on high performance computing systems. Performance tests were carried out on a 256-core cluster, where Parallel-FST obtained speedups of up to 229x for representative datasets and it was able to analyze a 512 GB dataset, which was not previously possible with a sequential counterpart library due to memory constraints., This research was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00/AEI/10.13039/ 501100011033), by the Ministry of Universities of Spain under grant FPU20/00997, and by Xunta de Galicia and FEDER funds of the EU (CITIC, Centro de Investigación de Galicia accreditation 2019-2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ED431C 2021/30)., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/30
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Spark implementation of the enhanced Scatter Search metaheuristic: Methodology and assessment

  • Pardo, Xoán C.
  • Argüeso-Alejandro, Pablo
  • González, Patricia
  • Banga, Julio R.
  • Doallo, Ramón
15 pages, 9 figures, 5 tables, Optimization problems arise nowadays in all disciplines, not only in the scientific area but also in the field of engineering or economics, and in many others. Currently, challenging optimization problems require solution methods that consume a significant amount of computational resources. The application of High-Performance Computing techniques is a common approach to obtain efficient implementations in traditional parallel computing systems. However, more recent approaches are exploring distributed programming frameworks developed in recent years to achieve efficient computations on clusters and cloud systems. In this paper we present a parallel implementation of the enhanced Scatter Search metaheuristic using Spark. The parallel program was obtained as a particularization of a general software framework we developed to support different realisations of the Scatter Search metaheuristic. The aim of this paper is to provide helpful guidance to readers interested in applying, or developing their own, parallel metaheuristics to solve challenging problems in the Cloud. With the twofold objective of demonstrating the potential of the parallelization with Spark and also of studying the factors that influence the performance of the solution, the proposal has been thoroughly evaluated on two different platforms, a cluster and a cloud platform, using a representative set of parameter estimation problems in the field of Computational Systems Biology, This work was supported by the Ministry of Science and Innovation of Spain (DPI2017-82896-C2-2-R, TIN2016-75845-P and PID2019-104184RB-I00, AEI/FEDER/UE, 10.13039/501100011033); and by Xunta de Galicia and FEDER funds (Centro de Investigación de Galicia accreditation 2019-2022, ref. ED431G 2019/01, as well as Consolidation Program of Competitive Reference Groups, ref. ED431C 2017/04), Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

An efficient ant colony optimization framework for HPC environments

  • González, Patricia
  • Osorio, Roberto R.
  • Pardo, Xoán C.
  • Banga, Julio R.
  • Doallo, Ramón
14 pages, 8 tables, 14 figures.-- Under a Creative Commons license, Combinatorial optimization problems arise in many disciplines, both in the basic sciences and in applied fields such as engineering and economics. One of the most popular combinatorial optimization methods is the Ant Colony Optimization (ACO) metaheuristic. Its parallel nature makes it especially attractive for implementation and execution in High Performance Computing (HPC) environments. Here we present a novel parallel ACO strategy making use of efficient asynchronous decentralized cooperative mechanisms. This strategy seeks to fulfill two objectives: (i) acceleration of the computations by performing the ants’ solution construction in parallel; (ii) convergence improvement through the stimulation of the diversification in the search and the cooperation between different colonies. The two main features of the proposal, decentralization and desynchronization, enable a more effective and efficient response in environments where resources are highly coupled. Examples of such infrastructures include both traditional HPC clusters, and also new distributed environments, such as cloud infrastructures, or even local computer networks. The proposal has been evaluated using the popular Traveling Salesman Problem (TSP), as a well-known NP-hard problem widely used in the literature to test combinatorial optimization methods. An exhaustive evaluation has been carried out using three medium and large size instances from the TSPLIB library, and the experiments show encouraging results with superlinear speedups compared to the sequential algorithm (e.g. speedups of 18 with 16 cores), and a very good scalability (experiments were performed with up to 384 cores improving execution time even at that scale), This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00 / AEI/10.13039/501100011033), and by Xunta de Galicia and FEDER funds of the EU (Centro de Investigación de Galicia accreditation 2019–2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). JRB acknowledges funding from the Ministry of Science and Innovation of Spain MCIN/AEI/10.13039/501100011033 through grant PID2020-117271RB-C22 (BIODYNAMICS), and from MCIN/AEI /10.13039/501100011033 and “ERDF A way of making Europe” through grant DPI2017-82896-C2-2-R (SYNBIOCONTROL), Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Parallel ant colony optimization for the training of cell signaling networks

  • González, Patricia
  • Prado Rodríguez, Roberto
  • Gábor, Attila
  • Sáez-Rodríguez, Julio
  • Banga, Julio R.
  • Doallo, Ramón
Acquiring a functional comprehension of the deregulation of cell signaling networks in disease allows progress in the development of new therapies and drugs. Computational models are becoming increasingly popular as a systematic tool to analyze the functioning of complex biochemical networks, such as those involved in cell signaling. CellNOpt is a framework to build predictive logic-based models of signaling pathways by training a prior knowledge network to biochemical data obtained from perturbation experiments. This training can be formulated as an optimization problem that can be solved using metaheuristics. However, the genetic algorithm used so far in CellNOpt presents limitations in terms of execution time and quality of solutions when applied to large instances. Thus, in order to overcome those issues, in this paper we propose the use of a method based on ant colony optimization, adapted to the problem at hand and parallelized using a hybrid approach. The performance of this novel method is illustrated with several challenging benchmark problems in the study of new therapies for liver cancer., This work was supported by the Ministry of Science and Innovation of Spain (PID2019-104184RB-I00/AEI/10.13039/501100011033), and by Xunta de Galicia, Spain and FEDER funds of the EU (Centro de Investigación de Galicia accreditation 2019–2022, ref. ED431G 2019/01; Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). JRB acknowledges funding from the Ministry of Science and Innovation of Spain MCIN/AEI/10.13039/501100011033 through grant PID2020-117271RB-C22 (BIODYNAMICS). AG acknowledges funding from the European Union Innovative Medicines Initiative TransQST (agreement No.116030). Authors also acknowledge the Galician Supercomputing Center (CESGA) for the access to its facilities. Funding for open access charge: Universidade da Coruña/CISUG., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Improved cooperative Ant Colony Optimization for the solution of binary combinatorial optimization applications

  • Prado-Rodríguez, Roberto
  • González, Patricia
  • Banga, Julio R.
  • Doallo, Ramón
19 páginas, 11 figuras, 6 tablas, Binary combinatorial optimization plays a crucial role in various scientific and engineering fields. While deterministic approaches have traditionally been used to solve these problems, stochastic methods, particularly metaheuristics, have gained popularity in recent years for efficiently handling large problem instances. Ant Colony Optimization (ACO) is among the most successful metaheuristics and is frequently employed in non-binary combinatorial problems due to its adaptability. Although for binary combinatorial problems ACO can suffer from issues such as rapid convergence to local minima, its eminently parallel structure means that it can be exploited to solve large and complex problems also in this field. In order to provide a versatile ACO implementation that achieves competitive results across a wide range of binary combinatorial optimization problems, we introduce a parallel multicolony strategy with an improved cooperation scheme to maintain search diversity. We evaluate our proposal (Binary Parallel Cooperative ACO, BiPCACO) using a comprehensive benchmark framework, showcasing its performance and, most importantly, its flexibility as a successful all-purpose solver for binary combinatorial problems., RPR, PGG and RDB acknowledges funding from Grants PID2019-104184RB-I00 and PID2022-136435NB-I00, funded by MCIN/AEI/10.13039/501100011033, PID2022 also funded by ‘ERDF A way of making Europe’, EU; Xunta de Galicia and FEDER funds of the EU (Consolidation Program of Competitive Reference Groups, ref. ED431C 2021/30). JRB acknowledges funding from the Ministry of Science and Innovation of Spain MCIN/AEI/10.13039/501100011033 through grant PID2020-117271RB- C22 (BIODYNAMICS). Authors also acknowledge the Galician Supercom- puting Center (CESGA) for the access to its facilities. Funding for open access charge: Universidade da Coruña/CISUG, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Population based metaheuristics in Spark: Towards a general framework using PSO as a case study

  • Pardo, Xoán C.
  • Gonzalez, Patricia
  • Banga, Julio R.
  • Doallo, Ramón
26 pages, 19 figures, 16 tables; The code and data used for this research are available in public repositories referenced in the article., Over the years metaheuristics have been successfully applied to optimization problems in many real-world applications. The increasing complexity and scale of the problems addressed has posed new challenges to researchers in the field. The application of distributed metaheuristics is a common approach to speed up the time to solution or improve its quality by leveraging traditional parallel programming models on platforms like multicore processors or computer clusters. More recently, the emergence of Cloud Computing and new programming models and frameworks for Big Data has facilitated access to an unprecedented amount of computational resources, which led to a growing interest in optimization frameworks that support the development and execution of distributed metaheuristics taking advantage of this potential. In this paper, we present the current status of development of one such framework that aims to provide support for the application of distributed population-based metaheuristics to the global optimization of large-scale problems in Spark. The framework provides a reduced set of abstractions to represent the general structure of population-based metaheuristics as templates and strategies to particularize them into concrete metaheuristics, as well as other nice features like out of the box implementations of the most common distributed models, full configurability through a human-friendly format, and the possibility of rapid prototyping and testing metaheuristics in the Spark shell. To validate the approach, a template for Particle Swarm Optimization (PSO) was implemented as a proof of concept, which includes strategies for instantiating different variants of the algorithm, configurable topologies, and sequential and distributed execution models., This work was supported by MCIN/AEI/10.13039/501100011033 [grant numbers PID2019-104184RB-I00, PID2022-136435NB-I00 and PID2020-117271RB-C22 (BIODYNAMICS)], PID2022 also funded by “ERDF A way of making Europe”, EU. Also supported by Xunta de Galicia [grant number ED431C 2021/30]. Funding for open access charge: Universidade da Coruña/CISUG ., Peer reviewed