INRIA a CCSD electronic archive server
Not a member yet
122212 research outputs found
Sort by
Wronski Pairs of Honeycomb Curves
No full textInternational audienceWe study certain generic systems of real polynomial equations associated with triangulations of convex polytopes and investigate their number of real solutions. Our main focus is set on pairs of plane algebraic curves which form a so-called Wronski system. The computational tasks arising in the analysis of such Wronski pairs lead us to the frontiers of current computer algebra algorithms and their implementations, both via Gröbner bases and numerical algebraic geometry
Consolidation of virtual machines to reduce energy consumption of data centers by using ballooning, sharing and swapping mechanisms
No full textInternational audienceData centers have major environmental impacts due to their energy consumption and the manufacturing of equipment. They emit greenhouse gases and consume energy and resources, such as rare earth and water. Efficient computing resource management is therefore a key challenge for Cloud service providers today as they need to meet a growing demand while limiting the oversizing of their infrastructures. Mechanisms derived from virtualization, such as Virtual Machines (VMs) consolidation, are used to optimize resource management and infrastructure sizing, but economic and technical constraints can hinder their adoption. They require prior infrastructure knowledge and usage study to evaluate their potential, involve complex placement algorithms, and are sometimes difficult to implement in hypervisors. In this paper, we propose ORCA (OuR Consolidation Algorithm), a complete consolidation methodology designed to facilitate the production implementation of such mechanisms. This methodology includes the study of VM usage, the use of prediction models, and a VM placement algorithm that takes advantage of resource oversubscription. The choice of relevant oversubscription ratios is also addressed, with a focus on memory overcommitment through the study of memory overcommitment mechanisms:ballooning, page sharing, and swapping. Results from a detailed simulation process and deployment on a production infrastructure are presented. The methodology is tested in simulation on two production infrastructure datasets, with power consumption reduction as high as 29.8% and without consolidation error. The production deployment using VMWare vSphere and considering fault tolerance requirements reduces the energy consumption by 6.12% without causing any performance degradation
Turnpike property of linear quadratic control problems with unbounded control operators
No full textInternational audienceWe establish the turnpike property for linear quadratic control problems for which the control operator is admissible and may be unbounded, under quite general and natural assumptions. The turnpike property has been well studied for bounded control operators, based on the theory of differential and algebraic Riccati equations. For unbounded control operators, there are only few results, limited to some special cases of hyperbolic systems in dimension one or to analytic semigroups. Our analysis is inspired by the pioneering work of Porretta and Zuazua \cite{PZ13}. We start by approximating the admissible control operator with a sequence of bounded ones. We then prove the convergence of the approximate problems to the initial one in a suitable sense. Establishing this convergence is the core of the paper. It requires to revisit in some sense the linear quadratic optimal control theory with admissible control operators, in which the roles of energy and adjoint states, and the connection between infinite-horizon and finite-horizon optimal control problems with an appropriate final cost are investigated
Nonlinear model calibration through bifurcation curves
No full textInternational audienceNonlinear systems exhibit a plethora of complex dynamic behaviours that are difficult to model and predict accurately. This difficulty often arises from a lack of knowledge of the physics that induces the nonlinear behaviours and the strong sensitivity of the nonlinear dynamics to parameter variation. We introduce in this paper a methodology to carry out nonlinear model updating based on bifurcations. The proposed approach involves minimising the distance between experimental and numerical bifurcation curves, which are key dynamic features that define stability boundaries and regions of multi-stability. For the model, bifurcation curves are computed via standard numerical bifurcation tracking analyses. In the experiment, we use control-based continuation to obtain the data. The approach is first demonstrated on a Duffing and a beam system using synthetic data, before being applied to experimental data collected on a base-excited energy harvester with magnetic nonlinearity
The Harmonious Coloring Game
No full textInternational audienceA harmonious k-coloring of a graph G is a 2-distance proper k-coloring of its vertices such that each edge is uniquely identified by the colors of its endpoints. Here, we introduce its game version: the harmonious coloring game. In this two-player game, Alice and Bob alternately select an uncolored vertex and assigns to it a color in {1,...,k} with the constraint that, at every turn, the set of colored vertices induces a valid partial harmonious coloring. Alice wins if all vertices are colored; otherwise, Bob wins. The harmonious game chromatic number is the minimum integer k such that Alice has a winning strategy with colors. In this paper, we prove the PSPACE-hardness of three variants of this game. As a by-product, we prove that a variant introduced by Chen et al. in 1997 of the classical graph coloring game is PSPACE-hard even in graphs with diameter two. We also obtain lower and upper bounds for in graph classes, such as paths, cycles, grids and forests of stars
Knock-Knock: Black-Box, Platform-Agnostic DRAM Address-Mapping Reverse Engineering
No full textInternational audienceModern Systems-on-Chip (SoCs) employ undocumented linear address-scrambling functions to obfuscate DRAM addressing, which complicates DRAM-aware performance optimizations and hinders proactive security analysis of DRAM-based attacks; most notably, Rowhammer. Although previous work tackled the issue of reversing physical-to-DRAM mapping, existing heuristic-based reverse-engineering approaches are partial, costly, and impractical for comprehensive recovery. This paper establishes a rigorous theoretical foundation and provides efficient practical algorithms for black-box, complete physical-to-DRAM address-mapping recovery.We first formulate the reverse-engineering problem within a linear algebraic model over the finite field GF(2). We characterize the timing fingerprints of row-buffer conflicts, proving a relationship between a bank addressing matrix and an empirically constructed matrix of physical addresses. Based on this characterization, we develop an efficient, noise-robust, and fully platform-agnostic algorithm to recover the full bankmask basis in polynomial time, a significant improvement over the exponential search from previous works. We further generalize our model to complex row mappings, introducing new hardware-based hypotheses that enable the automatic recovery of a row basis instead of previous human-guided contributions.Evaluations across embedded and server-class architectures confirm our method's effectiveness, successfully reconstructing known mappings and uncovering previously unknown scrambling functions. Our method provides a 99% recall and accuracy on all tested platforms. Most notably, Knock-Knock runs in under a few minutes, even on systems with more than 500GB of DRAM, showcasing the scalability of our method. Our approach provides an automated, principled pathway to accurate DRAM reverse engineering
Nondeterminism in Interactive Markov Chains, with Application to the Erlangen Mainframe
No full textInternational audienc
Comportement quasi-limite du processus de branchement bi-sexué multi-type de Galton-Watson sous-critique
No full textInternational audienceWe investigate the quasi-limiting behaviour of bisexual subcritical Galton-Watson branching processes. While classical subcritical Galton-Watson processes have been extensively analyzed, bisexual Galton-Watson branching processes present unique difficulties because of the lack of the branching property. To prove the existence of and convergence to one or several quasi-stationary distributions, we leverage on recent developments linking bisexual Galton-Watson branching processes extinction to the eigenvalue of a concave operator
ROOFS: RObust biOmarker Feature Selection
No full textFeature selection (FS) is essential for biomarker discovery and in the analysis of biomedical datasets. However, challenges such as high-dimensional feature space, low sample size, multicollinearity, and missing values make FS non-trivial. Moreover, FS performances vary across datasets and predictive tasks. We propose roofs, a Python package available at https://gitlab.inria.fr/compo/roofs, designed to help researchers in the choice of FS method adapted to their problem. Roofs benchmarks multiple FS methods on the user's data and generates reports that summarize a comprehensive set of evaluation metrics, including downstream predictive performance estimated using optimism correction, stability, reliability of individual features, and true positive and false positive rates assessed on semi-synthetic data with a simulated outcome. We demonstrate the utility of roofs on data from the PIONeeR clinical trial, aimed at identifying predictors of resistance to anti-PD-(L)1 immunotherapy in lung cancer. The PIONeeR dataset contained 374 multi-source blood and tumor biomarkers from 435 patients. A reduced subset of 214 features was obtained through iterative variance inflation factor pre-filtering. Of the 34 FS methods gathered in roofs, we evaluated 23 in combination with 11 classifiers (253 models in total) and identified a filter based on the union of Benjamini-Hochberg false discovery rate-adjusted p-values from t-test and logistic regression as the optimal approach, outperforming other methods including the widely used LASSO. We conclude that comprehensive benchmarking with roofs has the potential to improve the robustness and reproducibility of FS discoveries and increase the translational value of clinical models
PyroBuildS: Speeding up the exploration of large configuration spaces with incremental build
No full textInternational audienceSoftware developers are acutely aware that software build is an essential but resource-intensive step in any software development process, all the more when building large and/or highly configurable systems, whose vast number of configuration options leads to an explosion in the number of variants to build and evaluate. A potential approach to speed up the builds of multiple configurations is to do incremental build, i.e., to not clean the build environment and reuse previous builds when building a new configuration. Previous exploratory studies showed some benefits and limitations of incremental build, but mainly on small configurable software systems and on a limited set of close configurations. However, for large configuration spaces, little is known whether the large distance across configurations impacts the correctness and efficiency of incremental build.This paper presents PyroBuildS, a new approach to speed up incremental builds while keeping reproducibility, featuring a configuration variation operator parameterized by two deny lists of problematic options and a mutation size (diversity).We evaluate PyroBuildS through an empirical study on three large complex configurable systems, namely Linux, BusyBox, and ToyBox, with respectively 18637, 1078, 330 configuration options. We first show that for all configurations PyroBuildS produces the exact same binaries as a clean build, except for Linux with some non-reproducible random configurations. We identify the reasons why incremental build speeds up or slows down the build of large configuration spaces – a knowledge that can be integrated into PyroBuildS. Incremental build systematically pays off, since problematic options are avoided in the first place — something only PyroBuildS does. We also show that a naive use of incremental build on random Linux configurations backfires, taking more time than clean builds. Thus, PyroBuildS controls diversity to avoid too many differences across configurations to perform efficient incremental builds.Thanks to its ability to operate over non-problematic options and close enough configurations, PyroBuildS significantly speeds up the exploration of large configuration spaces, with a gain in build time from 16% to 22% in all three systems with mutated configurations. Finally, with random configurations, PyroBuildS also speeds up the build time from 15% to 20% for ToyBox and BusyBox