Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
EasyDRAM: An FPGA-based Infrastructure for Fast and Accurate End-to-End Evaluation of Emerging DRAM Techniques
No full textInternational audienceDRAM is a critical component of modern computing systems. Recent works propose numerous techniques (that we call DRAM techniques) to enhance DRAM-based computing systems’ throughput, reliability, and computing capabilities (e.g., in-DRAM bulk data copy). Evaluating the system-wide benefits of DRAM techniques is challenging as they often require modifications across multiple layers of the computing stack. Prior works propose FPGA-based platforms for rapid end-to-end evaluation of DRAM techniques on real DRAM chips. Unfortunately, existing platforms fall short in two major aspects: (1) they require deep expertise in hardware description languages, limiting accessibility; and (2) they are not designed to accurately model modern computing systems.We introduce EasyDRAM, an FPGA-based framework for rapid and accurate end-to-end evaluation of DRAM techniques on real DRAM chips. EasyDRAM overcomes the main drawbacks of prior FPGA-based platforms with two key ideas. First, EasyDRAM removes the need for hardware description language expertise by enabling developers to implement DRAM techniques using a high-level language (C++). At runtime, EasyDRAM executes the high-level software-defined memory system design in a programmable memory controller. Second, EasyDRAM tackles a fundamental challenge in accurately modeling modern systems: real processors typically operate at significantly higher clock frequencies than DRAM, a disparity that is difficult to replicate on FPGA platforms. EasyDRAM addresses this challenge by decoupling the processor–DRAM interface and advancing the system state using a novel technique we call time scaling, which faithfully captures the timing behavior of the modeled system.We validate EasyDRAM’s evaluation accuracy by comparing the memory latency profile of a real CPU-based system and its modeled implementation using EasyDRAM. We demonstrate the ease of use of EasyDRAM by evaluating two DRAM techniques end-to-end in a real FPGA-based system: (1) in-DRAM bulk data copy (i.e., RowClone) and (2) reduced-latency DRAM access that exploits the latency variation across DRAM cells. Implementing these two techniques requires no hardware modifications and only 325 lines of C++ code over EasyDRAM’s extensible code base. We compare our results to prior FPGA-based platforms. EasyDRAM yields more accurate results (e.g., by ≈20× for execution time) than the state-of-the-art related platform. We believe and hope that EasyDRAM will enable innovative ideas in memory system design to rapidly come to fruition. To aid future research, we open-source our EasyDRAM implementation at https://github.com/CMU-SAFARI/EasyDRAM
Exploring Cache Policies on FPGA-Accelerated Simulations: Tradeoffs Between Usability and Simulation Speed
No full textInternational audienceFPGA-accelerated simulation offers a promising path toward achieving fast and cycle-accurate architectural evaluations. However, while platforms like FireSim significantly improve simulation speed compared to traditional software-based simulators, they still pose usability challenges for rapid microarchitectural prototyping due to the complexity of register-transfer level (RTL) development. In this work, we present a modular and latency-insensitive interface that simplifies the integration of cache replacement policies into FireSim's L2 cache. Our approach supports multiple implementation strategies, including host-based software, RTL, and high-level synthesis (HLS), thereby enabling multiple tradeoffs between simulation speed, hardware resource usage, and development effort. We use the advanced Hawkeye replacement policy as a case study to demonstrate the versatility of our approach and evaluate tradeoffs among the different implementation strategies. Our results show that, with the proposed latency-insensitive L2 interface, the HLS strategy strikes a favorable balance: It incurs only a 1.57× simulation slowdown compared to baseline FireSim, while avoiding the need for RTL expertise and significantly reducing design effort. Latency-insensitive interfaces therefore make it practical and efficient for non-hardware experts to evaluate advanced cache replacement policies on FPGA-accelerated simulators
Exact and Approximate Digraph Bandwidth
No full textInternational audienceIn this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph and an ordering of its vertices, the digraph bandwidth of with respect to is equal to the maximum value of over all arcs of going forward along (that is, when {\sigma (u)} < {\sigma (v)} . The Digraph Bandwidth problem takes as input a digraph and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidth easily reduces to Digraph Bandwidth and thus, it immediately implies that Digraph Bandwidth is -hard. While an time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form . In particular, we obtain the following results. Here, and denote the number of vertices and arcs of the input digraph , respectively. Digraph Bandwidth can be solved in time. This result implies a time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let be the underlying undirected graph of the input digraph. If the treewidth of is at most , then Digraph Bandwidth can be solved in time . This result implies a algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph as a minor. Digraph Bandwidth can be solved in time, where denotes the optimal digraph bandwidth of . This allow us to deduce a algorithm in many cases, for example when . Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth . In particular, we show that for any fixed real {\epsilon } > {0}, we can find an ordering whose digraph bandwidth is at most times the optimal digraph bandwidth, in time
Convergence of the Number of Period sets in Strings
No full textInternational audienceConsider words of length . The set of all periods of a word of length is a subset of . However, not every subset of {0, 1, 2, …,-1} . However, not every subset of {0, 1, 2, …,-1} can be a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko proposed encoding the set of periods of a word into a binary string of length , called an autocorrelation, where a 1 at position i denotes the period i. They considered the question of recognizing a valid period set, and also studied the number of valid period sets for strings of length . They conjectured that asymptotically converges to a constant times (ln . Although improved lower bounds for (ln were proved in 2001, the question of a tight upper bound has remained open since Guibas and Odlyzko’s paper. Here, we exhibit an upper bound for this fraction, which implies its convergence and closes this longstanding conjecture. Moreover, we extend our result to find similar bounds for the number of correlations: a generalization of autocorrelations that encodes the overlaps between two strings
Robust Contraction Decomposition for Minor-Free Graphs and Its Applications
No full textInternational audienceWe prove a robust contraction decomposition theorem for H-minor-free graphs, which states that given an H-minor-free graph G and an integer p, one can partition in polynomial time the vertices of G into p sets Z₁,… ,Z_p such that tw(G/(Z_i ⧵ Z')) = O(p + |Z'|) for all i ∈ [p] and Z' ⊆ Z_i. Here, tw(⋅) denotes the treewidth of a graph and G/(Z_i ⧵ Z') denotes the graph obtained from G by contracting all edges with both endpoints in Z_i ⧵ Z'. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning E(G), and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time or for every vertex/edge deletion problems on H-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on H-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on H-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time
Cracking the mask: SASCA against local-masked NTT for CRYSTALS-Kyber
No full textInternational audienceSoft-Analytical Side-Channel Attacks (SASCAs) on lattice-based cryptography implementations have become a prominent vector of attack in the recent years, specially against the Number-Theoretic Transform (NTT). To address this issue, local masking with twiddle factors has been proposed as a countermeasure to protect the NTT against such attacks. In this paper we propose an adaptation of SASCA to local-masked NTT implementations, by modifying the factor graph representation to include the masking nodes. We evaluate the success rate of the attack with respect to the level of noise of simulated traces and the number of masks u per layer. We show that the attack proves very successful in the lower values of u , by even outperforming the attack on the unmasked case. When u is increased there is a gradual augmentation of security, which comes with an important overhead on performance. Thus, we question the practicality of this countermeasure when compared to other analyzed countermeasures in the state of the art, such as shuffling
From Presence‐Only to Abundance Species Distribution Models Using Transfer Learning
No full textInternational audienceSpecies Distribution Models based on Convolutional Neural Networks (CNN‐SDMs) have recently emerged, demonstrating greater effectiveness than traditional SDMs in several contexts. A limited number of studies, however, have focused on species abundance patterns, as the datasets available for this purpose are generally too small to effectively learn a deep learning model with millions of parameters. Our study demonstrated that CNN‐SDMs can circumvent the small sample size of species abundance datasets through the combined use of a large presence‐only species dataset and transfer learning to significantly improve the performance of abundance‐based CNN‐SDMs. Applied to Mediterranean coastal fishes, our approach significantly improves the abundance prediction performance of CNN‐SDMs, with average gains of 35% (D‐squared regression score). This allows CNN‐SDMs to perform better than classical SDMs in abundance prediction, with average gains of 10%. These gains are stemming from enhanced abundance predictions for rare species and where widespread species are locally rare
SCOOP : une méthode d'optimisation de réseaux de neurones adaptée aux attaques par canaux auxiliaires
No full textInternational audienceCet article présente un nouvel algorithme d'optimisation pour l'entrainement des réseaux de neurones dans le cadre des attaques par canaux auxiliaires (DL-SCA). Cet algorithme, appelé SCOOP, est une descente de miroir stochastique de second ordre. Nous montrons que SCOOP est capable de repousser significativement les limites actuelles du DL-SCA en présence de masquage. Grâce à SCOOP, nous avons pu mener à bien la première attaque DL-SCA sur le jeu de données ASCADv2
TUTPFL: Triple Node Upset-Tolerant and Single-Event Transient-Filtered Low-Power Latch With HSPICE and FPGA-Based Verifications
No full textInternational audienceIn nanoscale CMOS technology, harsh radiations in the environment can now easily cause soft errors, e.g., singleevent transients (SETs) and triple node upsets (TNUs), severely affecting the reliability of space applications. In this article, TNUs tolerant and SET-pulses filtered latch (TUTPFL) with low power is proposed, which comprises from four input-stage C-elements (CEs), four inverters, and three output-stage CEs. The CEs' delay differential enables the TUTPFL latch to effectively filter SET-pulse, while the CEs' multilevel error-interception property enables the TUTPFL latch to tolerate any possible TNU. The results of HSPICE-based simulations and FPGA-based emulations demonstrate the TNU tolerance and SET filterability of the TUTPFL latch. Meanwhile, compared to the alternative radiation-hardened latches, the TUTPFL latch reduces power dissipation by roughly 20.43% on average
A note on locating-dominating sets in twin-free graphs
No full textInternational audienceIn this short note, we prove that every twin-free graph on n vertices contains a locating-dominating set of size at most . This improves the earlier bound of due to Foucaud, Henning, Löwenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, González and Márquez