Skip to main content

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Dual Fast-Track Cache: Organizing Ring-Shaped Racetracks to Work as L1 Caches

  • Valero, Alejandro
  • Lorente Garcés, Vicente Jesús
  • Petit Martí, Salvador Vicente|||0000-0003-2426-4134
  • Sahuquillo Borrás, Julio|||0000-0001-8630-4846
[EN] Static Random-Access Memory (SRAM) is the fastest memory technology and has been the common design choice for implementing first-level (L1) caches in the processor pipeline, where speed is a key design issue that must be fulfilled. On the contrary, this technology offers much lower density compared to other technologies like Dynamic RAM, limiting L1 cache sizes of modern processors to a few tens of KB. This paper explores the use of slower but denser Domain Wall Memory (DWM) technology for L1 caches. This technology provides slow access times since it arranges multiple bits sequentially in a magnetic racetrack. To access these bits, they need to be shifted in order to place them under a header. A 1-bit shift usually takes one processor cycle, which can significantly hurt the application performance, making this working behavior inappropriate for L1 caches. Based on the locality (temporal and spatial) principles exploited by caches, this work proposes the Dual Fast-Track Cache (Dual FTC) design, a new approach to organizing a set of racetracks to build set-associative caches. Compared to a conventional SRAM cache, Dual FTC enhances storage capacity by 5x while incurring minimal shifting overhead, thereby rendering it a practical and appealing solution for L1 cache implementations. Experimental results show that the devised cache organization is as fast as an SRAM cache for 78% and 86% of the L1 data cache hits and L1 instruction cache hits, respectively (i.e., no shift is required). Consequently, due to the larger L1 cache capacities, significant system performance gains (by 22% on average) are obtained under the same silicon area., This work was supported in part by Agencia Estatal de Investigacion (AEI) under Grant PID2022-136454NB-C22/AEI/10.13039/501100011033; in part by the Spanish Ministerio de Ciencia e Innovacion and European ERDF under Grant PID2021-123627OB-C51 and Grant TED2021-130233B-C32; in part by European Union-NextGenerationE under Grant PDC2023-145851-00/MCIN/AEI/10.13039/501100011033; and in part by the Department of Science, University, and Knowledge Society, Government of Aragon under Grant gaZ: T58_23R research group.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Flip-and-Patch: A Fault-Tolerant Technique for On-Chip Memories of CNN Accelerators at Low Supply Voltage

  • Toca-Díaz, Yamilka
  • Hernández Palacios, Reynier
  • Gran Tejero, Rubén
  • Valero, Alejandro
Aggressively reducing the supply voltage () below the safe threshold voltage () can effectively lead to significant energy savings in digital circuits. However, operating at such low supply voltages poses challenges due to a high occurrence of permanent faults resulting from manufacturing process variations in current technology nodes. This work addresses the impact of permanent faults on the accuracy of a Convolutional Neural Network (CNN) inference accelerator using on-chip activation memories supplied at low below Based on a characterization study of fault patterns, this paper proposes two low-cost microarchitectural techniques, namely Flip-and-Patch, which maintain the original accuracy of CNN applications even in the presence of a high number of faults caused by operating at. Unlike existing techniques, Flip-and-Patch remains transparent to the programmer and does not rely on application characteristics, making it easily applicable to real CNN accelerators. Experimental results show that Flip-and-Patch ensures the original CNN accuracy with a minimal impact on system performance (less than 0.05% for every application), while achieving average energy savings of 10.5% and 46.6% in activation memories compared to a conventional accelerator operating at safe and nominal supply voltages, respectively. Compared to the state-of-the-art ThUnderVolt technique, which dynamically adjusts the supply voltage at run time and discarding any energy overhead for such an approach, the average energy savings are by 3.2%.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

GenArchBench: A genomics benchmark suite for arm HPC processors

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

Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming

  • Torres-Macías, Alitzel Galilea
  • Segarra Flor, Juan
  • Briz Velasco, José Luis
  • Ramírez-Treviño, Antonio
  • Blanco-Alcaine, Héctor
Time-Sensitive Networking (TSN) is an in-development technology that enables predictability over Ethernet or wireless networks. Network interfaces compliant with the IEEE 802.1Qbv standard provide different queues/gates on each bridge egress port. In this way, a global network schedule can be set by defining the opening and closing times (Gate Control List, GCL) for each gate. In this paper, we propose a new method to schedule GCLs by dividing the problem into several subproblems. We use Weighted Fair Queuing (WFQ) to set the ordering of frames, and then generate an Integer Linear Programming (ILP) model to optimize the TSN scenario. Next, we assign gates to the scheduled windows, trying to ensure frame isolation whenever possible. Our results show that we can schedule GCLs around 2 times faster than previous studies and up to 5.5 orders of magnitude faster if we choose to obtain any valid solution instead of the optimal one. In addition, we are able to schedule systems with utilization up to 85%, whereas previous papers reach 65%. Moreover, our approach does not need to predefine the number of windows or gates, as required by other methods.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Shift-and-Safe: Addressing permanent faults in aggressively undervolted CNN accelerators

  • Toca-Díaz, Yamilka
  • Gran Tejero, Rubén
  • Valero, Alejandro
Underscaling the supply voltage () to ultra-low levels below the safe-operation threshold voltage () holds promise for substantial power savings in digital CMOS circuits. However, these benefits come with pronounced challenges due to the heightened risk of bitcell permanent faults stemming from process variations in current technology node sizes. This work delves into the repercussions of such faults on the accuracy of a 16-bit fixed-point Convolutional Neural Network (CNN) inference accelerator powering on-chip activation memories at ultra-low voltages. Through an in-depth examination of fault patterns, memory usage, and statistical analysis of activation values, this paper introduces Shift-and-Safe: two novel and cost-effective microarchitectural techniques exploiting the presence of outlier activation values and the underutilization of activation memories. Particularly, activation outliers enable a shift-based data representation that reduces the impact of faults on the activation values, whereas the memory underutilization is exploited to maintain a safe replica of affected activations in idle memory regions. Remarkably, these mechanisms do not add any burden to the programmer and are independent of application characteristics, rendering them easily deployable across real-world CNN accelerators. Experimental results show that Shift-and-Safe maintains the CNN accuracy even in the presence of almost a quarter of the total activations with faults. In addition, average energy savings are by 5% and 11% compared to the state-of-the-art approach and a conventional accelerator supplied at , respectively.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

A complexity-effective local delta prefetcher

  • Navarro-Torres, Agustín
  • Panda, Biswabandan
  • Alastruey-Benedé, Jesús
  • Ibáñez, Pablo
  • Viñals-Yufera, Víctor
  • Ros, Alberto
Data prefetching is crucial for performance in modern processors by effectively masking long-latency memory accesses. Over the past decades, numerous data prefetching mechanisms have been proposed, which have continuously reduced the access latency to the memory hierarchy. Several state-of-the-art prefetchers, namely Instruction Pointer Classifier Prefetcher (IPCP) and Berti, target the first-level data cache, and thus, they are able to completely hide the miss latency for timely prefetched cache lines. Berti exploits timely local deltas to achieve high accuracy and performance. This paper extends Berti with a larger evaluation and with extra optimizations on top of the previous conference paper. The result is a complexity-effective version of Berti that outperforms it for a large amount of workloads and simplifies its control logic. The key for those advancements is a simple mechanism for learning timely deltas without the need to track the fetch latency of each cache miss. Our experiments conducted with a wide range of workloads (CVP traces by Qualcomm, SPEC CPU2017, and GAP) show performance improvements by 4.0% over a mainstream stride prefetcher, and by a non-negligible 1.4% over the previously published version of Berti requiring similar storage.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Ensuring the Accuracy of CNN Accelerators Supplied at Ultra-Low Voltage

  • Toca-Díaz, Yamilka
  • Gran Tejero, Rubén
  • Valero, Alejandro
Underscaling the supply voltage (Vdd) to ultra-low levels below the safe-operation threshold voltage (Vmin) brings significant energy savings in digital CMOS circuits but introduces reliability challenges due to increased risk of bitcell permanent faults. This work explores the impact of such faults on the accuracy of a CNN inference accelerator supplying on-chip activation memories at ultra-low Vdd. By examining fault pat-terns, activation values, and memory usage, this paper proposes two microarchitectural techniques exploiting activation outliers and activation memory underutilization. These approaches are cost-effective, do not require programmer intervention, and are application-independent. Experimental results show that the proposed approaches maintain the original CNN accuracy and achieve energy savings by 2.1 % and 8.2 % compared to the state-of-the-art technique and a conventional accelerator supplied at Vmin, respectively, with a negligible impact on the system performance (less than 0.25 %).
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

SpectralWaste Dataset: Multimodal Data for Waste Sorting Automation

  • Casao, Sara
  • Peña, Fernando
  • Sabater, Alberto
  • Castillón, Rosa
  • Suárez, Darío
  • Montijano, Eduardo
  • Murillo, Ana C.
The increase in non-biodegradable waste is a worldwide concern. Recycling facilities play a crucial role, but their automation is hindered by the complex characteristics of waste recycling lines like clutter or object deformation. In addition, the lack of publicly available labeled data for these environments makes developing robust perception systems challenging. Our work explores the benefits of multimodal perception for object segmentation in real waste management scenarios. First, we present SpectralWaste, the first dataset collected from an operational plastic waste sorting facility that provides synchronized hyperspectral and conventional RGB images. This dataset contains labels for several categories of objects that commonly appear in sorting plants and need to be detected and separated from the main trash flow for several reasons, such as security in the management line or reuse. Additionally, we propose a pipeline employing different object segmentation architectures and evaluate the alternatives on our dataset, conducting an extensive analysis for both multimodal and unimodal alternatives. Our evaluation pays special attention to efficiency and suitability for real-time processing and demonstrates how hyperspectral imaging can bring a boost to RGB-only perception in these realistic industrial settings without much computational overhead.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Modeling Time-Sensitive Networking Using Timed Continuous Petri Nets

  • Torres-Macías, A.G.
  • Ramírez-Treviño, A.
  • Briz, J.L.
  • Segarra, J.
  • Blanco-Alcaine, H.
Time-Sensitive Networking (TSN) is a set of standards designed to provide determinism to Ethernet or wireless networks for real-time applications. Network Calculus (NC) is the best-known formal tool for TSN analysis, but it is hard to apply in scenarios of changing conditions. Petri Nets can potentially overcome some limitations of NC, but they have rarely been used as an analytical tool for TSN. This work presents a novel modeling methodology exploiting Timed Continuous Petri Nets (TCPNs) to abstract and analyze TSN nodes.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

ILVES: Accurate and Efficient Bond Length and Angle Constraints in Molecular Dynamics

  • López-Villellas, Lorién
  • Mikkelsen, Carl Christian Kjelgaard
  • Galano-Frutos, Juan José
  • Marco-Sola, Santiago
  • Alastruey-Benedé, Jesús
  • Ibáñez, Pablo
  • Echenique, Pablo
  • Moretó, Miquel
  • De Rosa, Maria Cristina
  • García-Risueño, Pablo
All-atom, force field-based molecular dynamics simulations are essential tools in computational chemistry, enabling the prediction and analysis of biomolecular systems with atomic-level resolution. However, as system sizes and simulation time scales increase, so does the associated computational cost. To extend simulated time using the same resources, a common strategy is to constrain the fastest degrees of freedom, such as bond lengths, allowing for larger integration time steps without compromising accuracy. The de facto state-of-the-art algorithms for this purpose─SHAKE, LINCS, and P-LINCS─are integrated into most molecular dynamics packages and widely adopted across the field. Despite their impact, these methods exhibit limitations: all converge slowly when high numerical accuracy is required, and the LINCS and P-LINCS algorithms cannot handle general angular constraints, limiting further increases in time step. In this article, we introduce ILVES, a family of parallel algorithms that converge so rapidly that it is now practical to solve bond length and associated angular constraint equations as accurately as the hardware will allow. We have integrated ILVES into Gromacs, and our analysis demonstrates that it is superior to the state-of-the-art when constraining bond lengths. Due to its better convergence properties, we also show that if the time step is increased up to 3.5 fs by enforcing angular constraints, ILVES enables a 1.65× increase in simulated time using the same computational resources and wall-clock time, an outcome unattainable with current methods. This advance can significantly reduce the computational cost of most all-atom molecular dynamics simulations while improving their accuracy and extending access to larger systems and longer time scales.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Improving detection and figures of merit in single-particle inductively coupled plasma-mass spectrometry via transient event heights

  • Bazo, Antonio
  • López-Villellas, Lorién
  • Mataloni, Matilde
  • Bolea-Fernandez, Eduardo
  • Rua-Ibarz, Ana
  • Grotti, Marco
  • Aramendía, Maite
  • Resano, Martín
Background: Single-particle inductively coupled plasma-mass spectrometry (SP-ICP-MS) is a powerful method for characterizing micro- and nanoparticulate materials. The technique primarily relies on the linear relationship between the integrated intensities of individual events (peak areas) and the analyte mass, though transit times (peak widths) have also been used for quantitative purposes. This work (1) evaluates the potential of using peak heights as analytical signals in SP-ICP-MS, (2) introduces a new method for determining peak heights, and (3) explores scenarios in which peak height offers added value over the commonly used SP-ICP-MS signals. Results: A new method was proposed to estimate peak height values in SP-ICP-MS accurately. The cumulative intensity across consecutive dwell times was modeled using a third-degree polynomial, from which the adjusted peak height was derived. This approach reduces the uncertainty associated with using raw maximum intensity values, yielding NP distributions comparable to those obtained via integrated intensities. The effect of dwell time on peak height was also evaluated. An optimal range (50 μs–200 μs) was identified, where a linear relationship was observed between the peak height and the square of the NP diameter. Within this range, peak height showed the lowest bias when characterizing smaller NPs, indicating the potential to improve the limit of quantification (LoQ). Additionally, peak heights proved helpful in determining the limit of detection (LoD) and setting appropriate threshold values for data processing, thereby helping to flag incorrect resultsand addressing a challenge in SP-ICP-MS analysis. Significance: This is the first study to evaluate peak height as an analytical signal in SP-ICP-MS. The results highlight its advantages in specific applications, such as sizing NPs near the LoD, and in supporting the more reliable use of other signals, such as peak areas, by helping to identify incorrect threshold selection that could lead to biased distributions. Finally, monitoring peak heights allows for a more realistic and assumption-free determination of the LoD.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Contribución de congreso (ConferenceOutput)

Squire: a general-purpose accelerator to exploit fine-grain parallelism on dependency-bound kernels

  • Langarita, Rubén
  • Alastruey-Benedé, Jesús
  • Ibáñez-Marín, Pablo
  • Marco-Sola, Santiago
  • Moretó, Miquel
  • Armejach, Adrià
Multiple HPC applications are often bottlenecked by compute-intensive kernels implementing complex dependency patterns (data-dependency bound). Traditional general-purpose accelerators struggle to effectively exploit fine-grain parallelism due to limitations in implementing convoluted data-dependency patterns (like SIMD) and overheads due to synchronization and data transfers (like GPGPUs). In contrast, custom FPGA and ASIC designs offer improved performance and energy efficiency at a high cost in hardware design and programming complexity and often lack the flexibility to process different workloads. We propose Squire, a general-purpose accelerator designed to exploit fine-grain parallelism effectively on dependency-bound kernels. Each Squire accelerator has a set of general-purpose low-power in-order cores that can rapidly communicate among themselves and directly access data from the L2 cache. Our proposal integrates one Squire accelerator per core in a typical multicore system, allowing the acceleration of dependency-bound kernels within parallel tasks with minimal software changes. As a case study, we evaluate Squire’s effectiveness by accelerating five kernels that implement complex dependency patterns. We use three of these kernels to build an end-to-end read-mapping tool that will be used to evaluate Squire. Squire obtains speedups up to 7.64× in dynamic programming kernels. Overall, Squire provides an acceleration for an end-to-end application of 3.66×. In addition, Squire reduces energy consumption by up to 56% with a minimal area overhead of 10.5% compared to a NeoverseN1 baseline.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

How Accurate is Richardson's Error Estimate?

  • Kjelgaard Mikkelsen, Carl Christian
  • López-Villellas, Lorién
ABSTRACT We consider the fundamental problem of estimating the difference between the exact value and approximations that depend on a single real parameter . It is well‐known that if the error satisfies an asymptotic expansion, then we can use Richardson extrapolation to approximate . In this paper, our primary concern is the accuracy of Richardson's error estimate , that is, the size of the relative error . In practice, the computed value is different from the exact value . We show how to determine when the computational error is irrelevant and how to estimate the accuracy of Richardson's error estimate in terms of Richardson's fraction . We establish monotone convergence theorems and derive upper and lower bounds for in terms of and . We classify asymptotic error expansions according to their practical value rather than the order of the primary error term. We present a sequence of numerical experiments that illustrate the theory. Weierstrass's function is used to define a sequence of smooth problems for which it is impractical to apply Richardson's techniques.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Floating-point atomic memory operations

  • Soria-Pardos, Víctor
  • Armejach, Adrià
  • Suárez, Darío
  • Moretó, Miquel
Modern computing systems are increasingly adopting chiplet-based architectures, enabling the integration of different vendor devices, such as Central Processing Units (CPUs), Graphic Processing Units (GPUs), within a single package. These heterogeneous systems require efficient inter-chip synchronization mechanisms, including Atomic Memory Operations (AMOs). However, efficient synchronization demands that all integrated devices support the same AMO capabilities. While GPUs natively support floating-point AMOs (FAMOs), CPUs do not, creating an architectural asymmetry that leads to synchronization inefficiencies. To address this gap, Arm has recently introduced the Large System Floating-point Extension (LSFE), which introduces novel FAMO support to CPUs. This work characterizes and models the impact of FAMOs on graph processing, Machine Learning (ML), and High-Performance Computing (HPC) workloads. Our analysis reveals that a substantial fraction of AMOs target floating-point data and are currently implemented using inefficient compare-and-swap (CAS) built-ins. Replacing CAS-based constructs with hardware native FAMOs significantly improves performance across a wide range of workloads. Furthermore, we examine the trade-offs of executing FAMOs at different levels of the memory hierarchy, comparing execution in private caches (near) versus shared caches (far). Our results show that near FAMOs achieve an average speed-up of 1.3× speed-up, while far FAMOs deliver an average speed-up of 1.5×. Overall, we demonstrate that FAMOs can enable more efficient synchronization across key application domains.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Singletrack: an algorithm for improving memory consumption and performance of gap-affine sequence alignment

  • López-Villellas, Lorién
  • Iñiguez, Cristian
  • Jiménez-Blanco, Albert
  • Aguado-Puig, Quim
  • Moretó, Miquel
  • Alastruey-Benedé, Jesús
  • Ibáñez, Pablo
  • Marco-Sola, Santiago
Motivation Advances in DNA sequencing have outpaced advances in computation, making sequence alignment a major bottleneck in genome data analyses. Classical dynamic programming (DP) algorithms are particularly memory-intensive, especially when computing gap-affine and dual gap-affine alignments. Existing strategies to reduce memory consumption often sacrifice speed or alignment accuracy. Results We present Singletrack, an efficient algorithm for backtrace gap-affine and dual gap-affine alignments that requires storing a single DP matrix while preserving optimal alignment results. Compared to classical DP algorithms, Singletrack removes the need to store additional matrices (i.e. 2 for gap-affine and 4 for dual gap-affine), significantly reducing memory consumption and, in turn, reducing pressure on the memory hierarchy and improving overall performance. Most importantly, Singletrack is a general backtrace method compatible with state-of-the-art DP-based algorithms and heuristics, such as the Suzuki-Kasahara (SK) and the Wavefront Alignment (WFA) algorithms. We demonstrate that Singletrack reduces memory consumption for both SK and WFA algorithms, lowering SK usage by 2× and 4× and WFA usage by 3× and 5× for gap-affine and dual gap-affine alignments, respectively. Moreover, replacing KSW2’s memory-reduction technique with Singletrack accelerates its SK implementation by up to 1.4× at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2–2.1×. Compared to the efficient linear-memory BiWFA algorithm, the Singletrack-accelerated version of WFA trades a practical increase in memory usage for up to 5.2× higher performance.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Rethinking Per‐Thread Computation for Machine Learning Design Exploration: A Work‐Efficient GPU Strategy for K‐Means and XGBoost

  • Barros, Olavo
  • Freitas, Isabela
  • Pereira, Pedro H.
  • Neto, Walter de B.
  • Alcolea, Adrián
  • Villarroya-Gaudó, María
  • Resano, Javier
  • Nacif, José Augusto M.
  • Ferreira, Ricardo
ABSTRACT This paper presents novel GPU implementation strategies that effectively exploit the available parallelism, based on the “more work per thread” approach, for three machine learning design exploration tasks: Multiple K‐means evaluation, dimensionality reduction through parallel K‐means encoding for XGBoost trees, and XGBoost tree pruning optimization. Our experimental results demonstrate significant performance improvements across all implementations. For multiple K‐means evaluations, we achieve substantial speedups of 20 to 70 compared to Nvidia's cuML library. The dimensionality reduction approach, which uses parallel K‐means encoding, achieves encoding reductions of up to two orders of magnitude while preserving classification accuracy within 1%–2% of the original performance. Additionally, we propose a Gini coefficient‐based design exploration optimization that greatly reduces the number of models to be trained during the design space optimal search, achieving a 400 speedup. Furthermore, a parallel post‐pruning evaluation framework for XGBoost demonstrates the ability to remove up to 50% of tree nodes without significant loss of accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Theseus: fast and optimal affine-gap sequence-to-graph alignment

  • Jiménez-Blanco, Albert
  • López-Villellas, Lorién
  • Moure, Juan Carlos
  • Moreto, Miquel
  • Marco-Sola, Santiago
Motivation Sequence-to-graph alignment is a central problem in bioinformatics, with applications in multiple sequence alignment (MSA) and pangenome analysis, among others. However, current algorithms for optimal affine-gap alignment impose high memory and computational requirements, limiting their scalability to aligning long sequences to complex graphs. Practical solutions partially address this problem using heuristic strategies that ultimately trade off optimality for speed. Results This work presents Theseus, a novel, fast, and optimal affine-gap sequence-to-graph alignment algorithm. Theseus leverages similarities between genomic sequences to accelerate the alignment computation and reduces the overall memory requirements without compromising optimality. To that end, Theseus processes only a subset of the dynamic programming cells, using a sparse-data strategy that enables efficient sequence-to-graph alignment. Moreover, our algorithm supports optimal affine-gap alignment on arbitrary directed graphs, including those with cycles. We evaluate Theseus on two key problems: MSA and pangenome read mapping. For MSA, we compare it against SPOA, abPOA, and POASTA. Theseus is 1.6× to 17.6× faster than POASTA, and 7.3× faster, on average, than SPOA, both optimal aligners. Compared with abPOA, Theseus ensures optimality and scales to the largest problems. For pangenome read mapping, we benchmark Theseus against the alignment stage of the mapping tool vg map, along with the alignment kernels of SPOA, abPOA, and POASTA. Theseus outperforms the other methods, showing a 1.9× to 16.9× speedup on short reads. Moreover, Theseus is 1.5× to 36.3× faster than vg when aligning against synthetic cyclic graphs.