Author: "Laboratoire de l'Informatique du Parallélisme ( LIP )" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Laboratoire de l'Informatique du Parallélisme ( LIP )"' showing total 4,363 results

Start Over Author "Laboratoire de l'Informatique du Parallélisme ( LIP )"

4,363 results on '"Laboratoire de l'Informatique du Parallélisme ( LIP )"'

1. Implicit Differentiation for Hyperparameter Tuning the Weighted Graphical Lasso

Author: Pouliquen, Can, Gonçalves, Paulo, Massias, Mathurin, Vayer, Titouan, Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Droit des Affaires et Nouvelles Technologies (DANTE), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)
Subjects: FOS: Computer and information sciences, Optimization, Computer Science - Machine Learning, Implicit differentiation, Machine Learning (stat.ML), Hyperparameter Selection, Machine Learning (cs.LG), Graphical Lasso, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, [INFO]Computer Science [cs], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: International audience; We provide a framework and algorithm for tuning the hyperparameters of the Graphical Lasso via a bilevel optimizationproblem solved with a first-order method. In particular, we derive the Jacobian of the Graphical Lasso solution with respect to itsregularization hyperparameters.
Published: 2023

2. Latency-Aware Strategies for Deploying Data Stream Processing Applications on Large Cloud-Edge Infrastructure

Author: Laurent Lefèvre, Alexandre da Silva Veith, Marcos Dias De Assuncao, Department of Computer Science [University of Toronto] (DCS), University of Toronto, Ecole de Technologie Supérieure [Montréal] (ETS), Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire de l'Informatique du Parallélisme (LIP), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer Networks and Communications, business.industry, Data stream mining, Computer science, 020206 networking & telecommunications, Cloud computing, 02 engineering and technology, Computer Science Applications, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Hardware and Architecture, Scalability, 0202 electrical engineering, electronic engineering, information engineering, Overhead (computing), 020201 artificial intelligence & image processing, The Internet, Enhanced Data Rates for GSM Evolution, Latency (engineering), business, Software, Edge computing, Information Systems, Computer network
Abstract: International audience; Internet of Things (IoT) applications often require the processing of data streams generated by devices dispersed over a large geographical area. Traditionally, these data streams are forwarded to a distant cloud for processing, thus resulting in high application end-to-end latency. Recent work explores the combination of resources located in clouds and at the edges of the Internet, called cloud-edge infrastructure, for deploying Data Stream Processing (DSP) applications. Most previous work, however, fails to scale to very large IoT settings. This paper introduces deployment strategies for the placement of DSP applications on to cloud-edge infrastructure. The strategies split an application graph into regions and consider regions with stringent time requirements for edge placement. The proposed Aggregate End-to-End Latency Strategy with Region Patterns and Latency Awareness (AELS+RP+LA) decreases the number of evaluated resources when computing an operator’s placement by considering the communication overhead across computing resources. Simulation results show that, unlike the state-of-the-art, AELS+RP+LA scales to environments with more than 100k resources with negligible impact on the application end-to-end latency.
Published: 2023

3. Does a sparse ReLU network training problem always admit an optimum?

Author: Le, Quoc-Tung, Riccietti, Elisa, Gribonval, Rémi, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Réseaux dynamiques : approche structurelle et temporelle (DANTE), Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio (PANAMA), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)
Subjects: FOS: Computer and information sciences, Sparse ReLU Neural Network, Computer Science - Neural and Evolutionary Computing, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Topology, Functional Analysis (math.FA), Mathematics - Functional Analysis, Mathematics - Algebraic Geometry, Best Approximation Property, Optimization and Control (math.OC), FOS: Mathematics, Neural and Evolutionary Computing (cs.NE), [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Closedness, Mathematics - Optimization and Control, Algebraic Geometry (math.AG)
Abstract: Given a training set, a loss function, and a neural network architecture, it is often taken for granted that optimal network parameters exist, and a common practice is to apply available optimization algorithms to search for them. In this work, we show that the existence of an optimal solution is not always guaranteed, especially in the context of {\em sparse} ReLU neural networks. In particular, we first show that optimization problems involving deep networks with certain sparsity patterns do not always have optimal parameters, and that optimization algorithms may then diverge. Via a new topological relation between sparse ReLU neural networks and their linear counterparts, we derive -- using existing tools from real algebraic geometry -- an algorithm to verify that a given sparsity pattern suffers from this issue. Then, the existence of a global optimum is proved for every concrete optimization problem involving a shallow sparse ReLU neural network of output dimension one. Overall, the analysis is based on the investigation of two topological properties of the space of functions implementable as sparse ReLU neural networks: a best approximation property, and a closedness property, both in the uniform norm. This is studied both for (finite) domains corresponding to practical training on finite training sets, and for more general domains such as the unit cube. This allows us to provide conditions for the guaranteed existence of an optimum given a sparsity pattern. The results apply not only to several sparsity patterns proposed in recent works on network pruning/sparsification, but also to classical dense neural networks, including architectures not covered by existing results.
Published: 2023

4. Trading performance for memory in sparse direct solvers using low-rank compression

Author: Grégoire PICHON, Thibault Marette, Loris Marchal, Frédéric Vivien, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), ANR-19-CE46-0009,SOLHARIS,Solveurs pour architectures hétérogènes utilisant des supports d'exécution, objectif scalabilité(2019), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), This work is part of the SOLHARIS project, supported by the Agence Nationale de la Recherche, under grant ANR-19-CE46-0009., INRIA, ANR-18-CE46-0006,SaSHiMi,Solveur linéaire creux exploitant des matrices hierarchiques(2018), Roma, Equipe, Solveurs pour architectures hétérogènes utilisant des supports d'exécution, objectif scalabilité - - SOLHARIS2019 - ANR-19-CE46-0009 - AAPG2019 - VALID, APPEL À PROJETS GÉNÉRIQUE 2018 - Solveur linéaire creux exploitant des matrices hierarchiques - - SaSHiMi2018 - ANR-18-CE46-0006 - AAPG2018 - VALID, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Contraintes mémoire, Computer Networks and Communications, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 010103 numerical & computational mathematics, [INFO] Computer Science [cs], [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Solveurs directs creux, 01 natural sciences, 010101 applied mathematics, Compression Low-rank, low-rank compression, Hardware and Architecture, [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], Ordonnancement, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO]Computer Science [cs], scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, sparse direct solvers, memory constraints, Software
Abstract: Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A main characteristic of a sparse direct solver using low-rank compression is when compression is performed. There are two distinct approaches: (1) all blocks are compressed before starting the factorization, which reduces the memory as much as possible, or (2) each block is compressed as late as possible, which usually leads to better speedup. The objective of this paper is to design a composite approach, to speedup computations while staying under a given memory limit. This should allow to solve large problems that cannot be solved with Approach 2 while reducing the execution time compared to Approach 1.We propose a memory-aware strategy where each block can be compressed either at the beginning or as late as possible. We first consider the problem of choosing when to compress each block, under the assumption that all information on blocks is perfectly known, i.e., memory requirement and execution time of a block when compressed or not. We show that this problem is a variant of the NP-complete Knapsack problem, and adapt an existing 2-approximation algorithm for our problem. Unfortunately, the required information on blocks depends on numerical properties and in practice cannot be known in advance. We thus introduce models to estimate those values. Experiments on the PaStiX solver demonstrate that our new approach can achieve an excellent trade-off between memory consumption and computational cost. For instance on matrix Geo1438, Approach 2 uses three times as much memory as Approach 1 while being three times faster. Our new approach leads to an execution time only 30% larger than Approach 2 when given a memory 30% larger than the one needed by Approach 1., Les solveurs directs creux utilisant de la compression low-rank ont montré leur efficacité pour résoudre de grands systèmes. Les améliorer permetde 1) résoudre de plus grands problèmes et 2) accélérer la résolution. Une caractéristique principale de ces solveurs est quand la compression est réalisée. Il existe deux approches: (1) tous les blocs sont compressés avant le début de la factorisation, ce qui minimise la consommation mémoire, ou (2) chaque bloc est compressé au plus tard, ce qui permet d’avoir de meilleures performances. L’objectif de cet article est de proposer une approche intermédiaire, qui accélère les calculs au maximum tout en restant en dessous d’une limite mémoire donnée. Cela devrait permettre de résoudre de grands problèmes que l’approche 2 ne peut pas résoudre ou de réduire le temps d’exécution de l’approche 1. Nous proposonsune stratégie memory-aware où chaque bloc peut ˆêtre compressé au début ou au plus tard. Nous commençons par considérer le problème où toutes les informations (consommation mémoire et temps d’exécution en version compressée ou non) sont parfaitement connues. Nous montrons que ce problème est une variante du problème NP-complet Knapsack et adaptons une 2-approximation pour notre problème. Malheureusement, toutes ces informations dépendent de propriétés numériques et ne sont pas connues `a l’avance. Des modèles sont donc introduits afin d’estimer ces valeurs. Des expérimentations avec le solveur PaStiX montrent que notre approche permet d’avoir un excellent compromis entre consommation mémoire et temps d’exécution. Par exemple, pour la matrice Geo1438, l’approche 2 utilise trois fois plus de mémoire que l’approche 1, qui est trois fois plus lente. Notre nouvelle méthode permet d’obtenir à la fois un temps d’exécution seulement 30% supérieur à celui de l’approche 2 tout en ayant une consommation mémoire seulement supérieure de 30% à celle de l’approche 1.
Published: 2022

5. Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning

Author: Vayer, Titouan, Gribonval, Rémi, Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), ANR-16-IDEX-0005,IDEXLYON,IDEXLYON(2016), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, Réseaux dynamiques : approche structurelle et temporelle (DANTE), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI)
Subjects: FOS: Computer and information sciences, Inverse problems, Computer Science - Machine Learning, Statistical Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Kernel norms, Optimal Transport, Machine Learning (stat.ML), Machine Learning (cs.LG)
Abstract: International audience; Comparing probability distributions is at the crux of many machine learning algorithms. Maximum Mean Discrepancies (MMD) and Wasserstein distances are two classes of distances between probability distributions that have attracted abundant attention in past years. This paper establishes some conditions under which the Wasserstein distance can be controlled by MMD norms. Our work is motivated by the compressive statistical learning (CSL) theory, a general framework for resource-efficient large scale learning in which the training data is summarized in a single vector (called sketch) that captures the information relevant to the considered learning task. Inspired by existing results in CSL, we introduce the Hölder Lower Restricted Isometric Property and show that this property comes with interesting guarantees for compressive statistical learning. Based on the relations between the MMD and the Wasserstein distances, we provide guarantees for compressive statistical learning by introducing and studying the concept of Wasserstein regularity of the learning task, that is when some task-specific metric between probability distributions can be bounded by a Wasserstein distance.
Published: 2023

6. Accurate calculation of Euclidean Norms using Double-word arithmetic

Author: Vincent Lefèvre, Nicolas Louvet, Jean-Michel Muller, Joris Picot, Laurence Rideau, Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), Sûreté du logiciel et Preuves Mathématiques Formalisées (STAMP), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), Muller, Jean-Michel, and Sûreté numérique pour les preuves assistées par ordinateur - - NuSCAP2020 - ANR-20-CE48-0014 - AAPG2020 - VALID
Subjects: Formalization, Euclidean norms, Applied Mathematics, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Square-root, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Floating-Point arithmetic, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Underflow, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], Overflow, Coq, Double-double arithmetic, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, Hardware_ARITHMETICANDLOGICSTRUCTURES, Proof assistant, Software, Double-word arithmetic, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract: We consider the computation of the Euclidean (or L2) norm of an n -dimensional vector in floating-point arithmetic. We review the classical solutions used to avoid spurious overflow or underflow and/or to obtain very accurate results. We modify a recently published algorithm (that uses double-word arithmetic) to allow for a very accurate solution, free of spurious overflows and underflows. To that purpose, we use a double-word square-root algorithm of which we provide a tight error analysis. The returned L2 norm will be within very slightly more than 0.5 ulp from the exact result, which means that we will almost always provide correct rounding.
Published: 2023

7. Des règles de quadrature dans les RKHSs à base de DPPs

Author: Belhadji, Ayoub, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and Belhadji, Ayoub
Subjects: [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA]
Abstract: We study quadrature rules based on configurations of nodes that follow the distribution of a determinantal point process (DPP).These quadrature rules are suitable for functions that belong to reproducing kernel Hilbert spaces (RKHS). We prove that the rate of convergencedepends principally on the eigenvalues of the corresponding integration operator. In particular, this work furnishes a unified analysis of numericalintegration and offers a new perspective on the use of DPPs in this field., On étudie des règles de quadrature à base de configurations de noeuds qui suivent la distribution d'un processus ponctuel déterminantal (DPP). Ces règles de quadrature sont adaptées à des fonctions qui appartiennent à des espaces d'Hilbert à noyau reproduisant. On montre que le taux de convergence dépend principalement des valeurs propres de l'opérateur d'intégration correspondant. En particulier, ce travail fournit une analyse unifiée de l'intégration numérique et offre un nouveau regard sur l'utilisation des DPPs dans ce domaine.
Published: 2022

8. A Polyhedral Approach for Scalar Promotion

Author: Sadler, Alec, Alias, Christophe, Thievenaz, Hugo, Compilation et Analyse, Logiciel et Matériel (CASH), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Kalray, CASH - Compilation and Analysis, Software and Hardware (CASH), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut National de Recherche en Informatique et en Automatique (INRIA), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: parallélisation automatique, scalar promotion, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], compilation, array scalarization, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, automatic parallelization, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], promotion scalaire, modèle polyédrique, compiler optimization, polyhedral model
Abstract: Memory accesses are a well known bottleneck whose impact might be mitigated by using properly the memory hierarchy until registers. In this paper, we address array scalarization, a technique to turn temporary arrays into a collection of scalar variables to be allocated to registers. We revisit array scalarization in the light of the recent advances of the polyhedral model, a general framework to design optimizing program transformations. We propose a general algorithm for array scalarization, ready to be plugged in a polyhedral compiler, among other passes. Our scalarization algorithm operates on the polyhedral intermediate representation. In particular, our scalarization algorithm is parametrized by the program schedule possibly computed by a previous compilation pass. We rely on schedule-directed array contraction and we propose a loop tiling algorithm able to reduce the footprint down to the available amount of registers on the target architecture. Experimental results con rm the e ectiveness and the e ciency of our approach.; Les accès mémoires sont un goulot d'étranglement bien connu, dont l'impact peut être limité en utilisant correctement la hiérarchie mémoire jusqu'aux registres. Dans ce rapport, nous étudions la scalaration de tableaux, une technique pour transformer un tableau en une collection de variables scalaires à allouer à des registres. Nous revisitons la scalarisation de tableau à la lumière des avancées récentes du modèle polyédrique, un cadre général pour construire des transformations de programme. Nous proposons un algorithme pour la scalarisation de tableaux, directement intégrable comme passe d'un compilateur polyédrique. Notre algorithme de scalarisation opère sur la représentation intermédiaire polyédrique. En particulier, notre algorithme est paramétré par un ordonnancement possiblement calcul e par une passe précédente. Nous utilisons la contraction de tableaux sous contrainte d’ordonnancement et nous proposons un nouvel algorithme de tuilage de boucles pour régler l'empreinte mémoire et ainsi utiliser le bon nombre de registres. Les résultats expérimentaux confirment l’intérêt et l’efficacité de notre approche.
Published: 2022

9. Fast Learning of Fast Transforms, with Guarantees

Author: Quoc-Tung Le, Léon Zheng, Elisa Riccietti, Rémi Gribonval, Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Valeo.ai, VALEO, ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)
Subjects: [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Butterfly structure, Matrix factorization, NP-hardness, Hierarchical factorization, Sparsity
Abstract: This paper is associated to code for reproducible research available at https://hal.inria.fr/hal-03552956; International audience; Approximating a matrix by a product of few sparse factors whose supports possess the butterfly structure, which is common to many fast transforms, is key to learn fast transforms and speedup algorithms for inverse problems. We introduce a hierarchical approach, that recursively approximates the considered matrix into two factors. Using recent advances on the well-posedness and tractability of the two-factor fixedsupport sparse matrix factorization problem, we establish exact recovery guarantees for the proposed algorithm. Experiments show that the speed and accuracy of the factorization can be jointly improved by several orders of magnitude, compared to gradient-based optimization methods.This paper is associated to code for reproducible research available at https://hal.inria.fr/hal-03552956
Published: 2022

10. Fast Multiscale Diffusion On Graphs

Author: Marcotte, Sibylle, Barbe, Amélie, Gribonval, Rémi, Vayer, Titouan, Sebban, Marc, Borgnat, Pierre, Gonçalves, Paulo, École normale supérieure - Rennes (ENS Rennes), Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Physique de l'ENS Lyon (Phys-ENS), École normale supérieure de Lyon (ENS de Lyon)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Work supported by the ACADEMICS grant of the IDEXLYON, project of the Université de Lyon, PIA operated by ANR-16-IDEX-0005, ANR-16-IDEX-0005,IDEXLYON,IDEXLYON(2016), ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, and Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-Institut d'Optique Graduate School (IOGS)
Subjects: Signal Processing (eess.SP), Numerical Analysis (math.NA), [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Approximate computing, Polynomials, Computational efficiency, Estimation error, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Chebyshev approximation, Mathematics - Numerical Analysis, Electrical Engineering and Systems Science - Signal Processing, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: International audience; Diffusing a graph signal at multiple scales requires computing the action of the exponential of several multiples of the Laplacian matrix. We tighten a bound on the approximation error of truncated Chebyshev polynomial approximations of the exponential, hence significantly improving a priori estimates of the polynomial order for a prescribed error. We further exploit properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus reducing drastically its computational cost.
Published: 2022

11. Dynamic DAG Scheduling Under Memory Constraints for Shared-Memory Platforms

Author: Yves Robert, Samuel Thibault, Gabriel Bathie, Loris Marchal, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), STatic Optimizations, Runtime Methods (STORM), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-CE46-0009,SOLHARIS,Solveurs pour architectures hétérogènes utilisant des supports d'exécution, objectif scalabilité(2019), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest
Subjects: Polynomial, Schedule, Linear programming, Heuristic, Computer science, Rounding, 010103 numerical & computational mathematics, 0102 computer and information sciences, Parallel computing, 01 natural sciences, Scheduling (computing), Shared memory, 010201 computation theory & mathematics, [INFO]Computer Science [cs], 0101 mathematics, Integer (computer science)
Abstract: International audience; This work focuses on dynamic DAG scheduling under memory constraints. We target a shared-memory platform equipped with p parallel processors. The goal is to bound the maximum amount of memory that may be needed by any schedule using p processors to execute the DAG. We refine the classical model that computes maximum cuts by introducing two types of memory edges in the DAG, black edges for regular precedence constraints and red edges for actual memory consumption during execution. A valid edge cut cannot include more than p red edges. This limitation had never been taken into account in previous works, and dramatically changes the complexity of the problem, which was polynomial and becomes NP-hard. We introduce an Integer Linear Program (ILP) to solve it, together with an efficient heuristic based on rounding the rational solution of the ILP. In addition, we propose an exact polynomial algorithm for series-parallel graphs. We further study the extension of the approach where the scheduler is dynamically constrained to select tasks (among ready tasks) so that the total memory used does not exceed some threshold. We provide an extensive set of experiments, both with randomly-generated graphs and with graphs arising from practical applications, which demonstrate the impact of resource constraints on peak memory usage.
Published: 2021

12. Resilient Scheduling Heuristics for Rigid Parallel Jobs

Author: Padma Raghavan, Hongyang Sun, Valentin Le Fèvre, Anne Benoit, Yves Robert, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Vanderbilt University [Nashville], Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), University of Kansas [Kansas City], Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: rigid parallel jobs, Mathematical optimization, Resilience, Job shop scheduling, Computer science, Approximation algorithm, shelf schedules, list schedules, Supercomputer, Scheduling (computing), Set (abstract data type), silent errors, [INFO]Computer Science [cs], Transient (computer programming), scheduling, approximation algorithms, Resilience (network), Heuristics
Abstract: International audience; This paper focuses on the resilient scheduling of parallel jobs on highperformance computing (HPC) platforms to minimize the overall completion time, or the makespan. We revisit the classical problem while assuming that jobs are subject to failures caused by transient or silent errors, and hence may need to be re-executed each time they fail to complete successfully. This work generalizes the classical framework where jobs are known offline and do not fail: in this framework, list scheduling that gives priority to the longest jobs is known to be a 3-approximation when imposing to use shelves, and a 2-approximation without this restriction. We show that when jobs can fail, using shelves can be arbitrarily bad, but unrestricted list scheduling remains a 2-approximation. The paper focuses on the design of several heuristics, some list-based and some shelf-based, along with different priority rules and backfilling strategies. We assess and compare their performance through an extensive set of simulations using both synthetic jobs and log traces from the Mira supercomputer.
Published: 2021

13. Energy-aware mapping and scheduling strategies for real-time workflows under reliability constraints

Author: Wu, Zhiwei, Han, Li, Liu, Jing, Robert, Yves, Vivien, Frédéric, East China Normal University [Shangaï] (ECNU), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), INRIA , LIP - ENS Lyon, Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: reliability, tri-criteria optimization, energy-aware, makespan, real-time workflows, placement, ordonnancement, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], consommation énergétique, faibilité, tricriteria optimization, [INFO]Computer Science [cs], scheduling, mapping, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], graphes de tâches temps-réel, optimisation multi-critère
Abstract: This paper focuses on energy minimization for the mapping and scheduling of real-time workflows under reliability constraints. Workflow instances are input periodically to the system. Each instance is composed of several tasks and must complete execution before the arrival of the next instance, and with a prescribed reliability threshold. While the shape of the dependence graph is identical for each instance, task execution times are stochastic and vary from one instance to the next. The reliability threshold is met by using several replicas for each task. The target platform consists of identical processors equipped with Dynamic Voltage and Frequency Scaling (DVFS) capabilities. A different frequency can be assigned to each task replica.This difficult tri-criteria mapping and scheduling problem (energy, deadline, reliability) has been studied only recently for workflows with arbitrary dependence constraints [20, 11]. We investigate new mapping and scheduling strategies based upon layers in the task graph, and which better balance replicas across processors, thereby decreasing the time overlap between the different replicas of the same task and saving energy. We compare these strategies with the two competitor approaches [20, 11] and a reference baseline [33] on a variety of benchmark workflows. Our best heuristics achieve an average energy gain of 40% over the competitors and of 80% over the baseline.; Ce travail s’intéresse à la minimisation de la consommation énergétique lors du placement et de l’ordonnancement de graphes de tâches temps-réel soumis à des contraintes de fiabilité. Des instances d’un graphe de tâches sont soumises périodiquement à un système. Chaque instance est composée de plusieurs tâches et son exécution doit être terminée avant l’arrivée de l’instance suivante tout en respectant un niveau de fiabilité donné. Ce niveau de fiabilité est atteint en répliquant un certain nombre de fois chacune des tâches. La plateforme de calcul est constituée de processeurs identiques dont le voltage et la fréquence peuvent être modifiés (système DVFS). Chaque réplica de tâche peut se voir attribuer sa propre fréquence.Ce problème tri-critère de placement et d’ordonnancement (énergie, dates butoir, fiabilité) n’a commencé à être étudié que très récemment avec des dépendances arbitraires [20, 11]. Nous étudions de nouvelles stratégies de placement et d’ordonnancement basées sur une notion de couche du graphe de tâches, et qui équilibrent mieux les réplicas entre les processeurs, ce qui permet de réduire le recouvrement temporel entre les différents réplicas d’une même tâche et, de ce fait, la consommation énergétique. Nous comparons ces stratégies à deux approches concurrentes [20, 11] et à une approche de référence [33], sur un tout un ensemble de graphes de tâches. Nos meilleures heuristiques obtiennent un gain d’énergie de 40% par rapport aux approches concurrentes et de 80% vis-à-vis de l’approche de référence.
Published: 2022

14. Optimal Checkpointing Strategies for Iterative Applications

Author: Yves Robert, Guillaume Pallez, Loris Marchal, Yishu Du, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Tongji University, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Topology-Aware System-Scale Data Management for High-Performance Computing (TADAAM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: 020203 distributed computing, Computer science, Iterative method, 02 engineering and technology, checkpoint strategy, Approx, Execution time, Combinatorics, Task (computing), Computational Theory and Mathematics, Hardware and Architecture, Iterative application, fail-stop error, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], resilience
Abstract: This work provides an optimal checkpointing strategy to protect iterative applications from fail-stop errors. We consider a general framework, where the application repeats the same execution pattern by executing consecutive iterations, and where each iteration is composed of several tasks. These tasks have different execution lengths and different checkpoint costs. Assume that there are $n$ n tasks and that task $a_{i}$ a i , where $0 \leq i 0 ≤ i n , has execution time $t_{i}$ t i and checkpoint cost $c_{i}$ c i . A naive strategy would checkpoint after each task. Another naive strategy would checkpoint at the end of each iteration. A strategy inspired by the Young/Daly formula would work for $\sqrt{2 \mu c_{{ave}} }$ 2 μ c a v e seconds, where $\mu$ μ is the application MTBF and $c_{{ave}}$ c a v e is the average checkpoint time, and checkpoint at the end of the current task (and repeat). Another strategy, also inspired by the Young/Daly formula, would select the task $a_{\min }$ a min with smallest checkpoint cost $c_{\min }$ c min and would checkpoint after every $p^{\text{th}}$ p th instance of that task, leading to a checkpointing period $p T$ p T , where $T = \sum _{i=0}^{n-1} a_{i}$ T = ∑ i = 0 n - 1 a i is the time per iteration. One would choose the period so that $p T \approx \sqrt{2 \mu c_{\min }}$ p T ≈ 2 μ c min to obey the Young/Daly formula. All these naive and Young/Daly strategies are suboptimal. Our main contribution is to show that the optimal checkpoint strategy is globally periodic, and to design a dynamic programming algorithm that computes the optimal checkpointing pattern. This pattern may well checkpoint many different tasks, and this across many different iterations. We show through simulations, both from synthetic and real-life application scenarios, that the optimal strategy outperforms the naive and Young/Daly strategies.
Published: 2022

15. Checkpointing strategies to protect parallel jobs from non-memoryless fail-stop errors

Author: Benoit, Anne, Perotin, Lucas, Robert, Yves, Vivien, Frédéric, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Inria - Research Centre Grenoble – Rhône-Alpes, Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: non-memoryless, checkpoint, fautes, distributions d’erreurs générales, parallel jobs, failures, tâches parallèles, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: This paper studies checkpointing strategies for parallel jobs subject to fail-stop errors. The optimal strategy is well known when failure inter-arrival times obey an Exponential law, but it is unknown for non-memoryless failure distributions. We explain why the latter fact is misunderstood in recent literature. We propose a general strategy that maximizes the expected efficiency until the next failure, and we show that this strategy is asymptotically optimal for very long jobs. Through extensive simulations, we show that the new strategy is always at least as good as the Young/Daly strategy for various failure distributions. For distributions with a high infant mortality (such as LogNormal 2.51 or Weibull 0.5), the execution time is divided by a factor 1.9 on average, and up to a factor 4.2 for recently deployed platforms.; Cet article étudie les stratégies de checkpoint pour des tâches parallèles sujettes `a des erreurs fatales. La stratégie optimale est bien connue lorsque les temps d’inter-arrivée des pannes obéissent `a une loi exponentielle, mais elle est inconnue pour les distributions d’erreurs générales. Nous expliquons pourquoi ce dernier fait est mal compris dans la littérature récente. Nous proposons une stratégie générale qui maximise l’efficacité attendue jusqu’`a la prochaine d´défaillance, et nous montrons que cette stratégie est asymptotiquement optimale pour les travaux très longs. Par des simulations extensives, nous montrons que la nouvelle stratégie est toujours au moins aussi bonne que la stratégie de Young/Daly pour diverses distributions de pannes. Pour les distributions avec une mortalité infantile élevée (comme LogNormal 2.51 ou Weibull 0.5), le temps d’exécution est divisé par un facteur 1.9 en moyenne, et jusqu’`a un facteur 4.2 pour des plates-formes récemment déployées.
Published: 2022

16. Efficient and Validated Numerical Evaluation of Abelian Integrals

Author: Bréhard, Florent, Brisebarre, Nicolas, Joldeş, Mioara, Tucker, Warwick, Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), School of Mathematics [Australia], Monash University [Melbourne], ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), Brisebarre, Nicolas, and Sûreté numérique pour les preuves assistées par ordinateur - - NuSCAP2020 - ANR-20-CE48-0014 - AAPG2020 - VALID
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], limit cycles, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Abelian integral, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], Newton-like operator, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], rigorous numerics, Hilbert's 16th problem, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], 2020 AMS classification: Primary: 34C07, Secondary: 37G15, 37M20, 42A10, 42A15, 65G20, [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, trigonometric polynomial interpolation
Abstract: Abelian integrals play a key role in the infinitesimal version of Hilbert's 16th problem. Being able to evaluate such integrals - with guaranteed error bounds - is a fundamental step in computer-aided proofs aimed at this problem. Using interpolation by trigonometric polynomials and quasi-Newton-Kantorovitch validation, we develop a validated numerics method for computing Abelian integrals in a quasi-linear number of arithmetic operations. Our approach is both effective, as exemplified on two practical perturbed integrable systems, and amenable to an implementation in a formal proof assistant, which is key to provide fully reliable computer-aided proofs.
Published: 2022

17. Scaling matrices and counting the perfect matchings in graphs

Author: Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, Uçar, Bora, Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: matrices bistochastiques, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, Permanent approximation, algorithmes randomisés, randomized algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Sinkhorn-Knopp scaling, doubly stochastic matrices, permanent, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general undirected graphs. Our approach is based on assigning probabilities to edges, randomly selecting an edge to be in a perfect matching, and discarding edges that cannot be put in a perfect matching. The probabilities are chosen according to the entries in the doubly stochastically scaled version of the adjacency matrix of the given graph. The experimental analysis on random and real-life graphs shows improvements in the approximation over previous and similar methods from the literature.
Published: 2022

18. Fast computation of approximant bases in canonical form

Author: Claude-Pierre Jeannerod, Vincent Neiger, Gilles Villard, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, Divide and conquer algorithms, Algebra and Number Theory, shifted Popov form, Logarithm, Basis (linear algebra), Degree (graph theory), Computation, 010102 general mathematics, minimal approximant basis, Hermite-Padé approximation, 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), 01 natural sciences, Polynomial matrix, Computational Mathematics, Applied mathematics, order basis, Multiplication, Canonical form, 0101 mathematics, polynomial matrix, Mathematics
Abstract: In this article, we design fast algorithms for the computation of approximant bases in shifted Popov normal form. We first recall the algorithm known as PM-Basis, which will be our second fundamental engine after polynomial matrix multiplication: most other fast approximant basis algorithms basically aim at efficiently reducing the input instance to instances for which PM-Basis is fast. Such reductions usually involve partial linearization techniques due to Storjohann, which have the effect of balancing the degrees and dimensions in the manipulated matrices. Following these ideas, Zhou and Labahn gave two algorithms which are faster than PM-Basis for important cases including Hermite-Pade approximation, yet only for shifts whose values are concentrated around the minimum or the maximum value. The three mentioned algorithms were designed for balanced orders and compute approximant bases that are generally not normalized. Here, we show how they can be modified to return the shifted Popov basis without impact on their cost bound; besides, we extend Zhou and Labahn's algorithms to arbitrary orders. Furthermore, we give an algorithm which handles arbitrary shifts with one extra logarithmic factor in the cost bound compared to the above algorithms. To the best of our knowledge, this improves upon previously known algorithms for arbitrary shifts, including for particular cases such as Hermite-Pade approximation. This algorithm is based on a recent divide and conquer approach which reduces the general case to the case where information on the output degree is available. As outlined above, we solve the latter case via partial linearizations and PM-Basis., 37 pages, 8 algorithms
Published: 2020

19. Efficient Identification of Butterfly Sparse Matrix Factorizations

Author: Léon Zheng, Elisa Riccietti, Rémi Gribonval, Valeo.ai, VALEO, Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), CIFRE N°2020/1643, ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), and Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Matrix factorization, Identifiability, General Medicine, General Chemistry, Hierarchical factorization, Sparsity, Machine Learning (cs.LG), Butterfly factorization
Abstract: Many well-known matrices $\mathbf{Z}$ are associated to fast transforms corresponding to factorizations of the form $\mathbf{Z} = \mathbf{X}^{(J)} \ldots \mathbf{X}^{(1)} $, where each factor $ \mathbf{X}^{(\ell)} $ is sparse and possibly structured. This paper investigates essential uniqueness of such factorizations. Our first main contribution is to prove that any $N \times N$ matrix having the so-called butterfly structure admits a unique factorization into $J$ butterfly factors (where $N = 2^J$), and that the factors can be recovered by a hierarchical factorization method. This contrasts with existing approaches which fit the product of the butterfly factors to a given matrix via gradient descent. The proposed method can be applied in particular to retrieve the factorizations of the Hadamard or the Discrete Fourier Transform matrices of size $2^J$. Computing such factorizations costs $\mathcal{O}(N^2)$, which is of the order of dense matrix-vector multiplication, while the obtained factorizations enable fast $\mathcal{O}(N \log N)$ matrix-vector multiplications. This hierarchical identifiability property relies on a simple identifiability condition in the two-layer and fixed-support setting that was recently established. While the butterfly structure corresponds to a fixed prescribed support for each factor, our second contribution is to obtain identifiability results with more general families of allowed sparsity patterns, taking into account permutation ambiguities when they are unavoidable. Typically, we show through the hierarchical paradigm that the butterfly factorization of the Discrete Fourier Transform matrix of size $2^J$ admits a unique sparse factorization into $J$ factors, when enforcing only $2$-sparsity by column and a block-diagonal structure on each factor.
Published: 2022

20. Toward an intelligent and efficient beehive: A survey of precision beekeeping systems and services

Author: Hadjur, Hugo, Ammar, Doreid, Lefèvre, Laurent, aivancity School for Technology, Business & Society, Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), aivancity School for Technology, Business & Society [Cachan], École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 2. Zero hunger, 0106 biological sciences, [INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR], Honey bee, Precision Beekeeping, Internet of Things, [SPI.NRJ]Engineering Sciences [physics]/Electric power, Forestry, Horticulture, 010603 evolutionary biology, 01 natural sciences, Computer Science Applications, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 010602 entomology, Smart Agriculture, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Artificial Intelligence, [SDV.SA.STA]Life Sciences [q-bio]/Agricultural sciences/Sciences and technics of agriculture, [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Agronomy and Crop Science
Abstract: International audience; Since the end of the 20 th century, bees are suffering from increasing stress factors, leading domesticated colonies to die or at least be less productive. Precision beekeeping (PB) is an emerging field of agriculture that aims at protecting bees, supporting beekeepers, and optimizing apiary production thanks to digital infrastructures. The digitalization of apiculture first involves systems from the field of the Internet of Things (IoT), with the development of sensors to collect and transfer bee-related data. Then, data analysis comes into play, providing models that connect the data with the biological states of beehives, sometimes thanks to artificial intelligence (AI). In this paper, we describe the recent advances in precision beekeeping as systems and as services. Different types of sensors, networks, and power sources in PB are covered. The collection and use of data are described, and the performances of PB services are assessed. We also estimate the sustainability of the proposed solutions, taking into account their scalability, efficiency, and economic cost, because beekeepers need deployable research results.
Published: 2022

21. Affine Iterations and Wrapping Effect: Various Approaches

Author: Revol, Nathalie, Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: SVD factorization, matrix powers, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, QR factorization, FOS: Mathematics, Mathematics - Numerical Analysis, Lohner's QR algorithm, Numerical Analysis (math.NA), [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], interval analysis, affine iterations
Abstract: International audience; Affine iterations of the form x(n+1) = Ax(n) + b converge, using real arithmetic, if the spectral radius of the matrix A is less than 1. However, substituting interval arithmetic to real arithmetic may lead to divergence of these iterations, in particular if the spectral radius of the absolute value of A is greater than 1. We will review different approaches to limit the overestimation of the iterates, when the components of the initial vector x(0) and b are intervals. We will compare, both theoretically and experimentally, the widths of the iterates computed by these different methods: the naive iteration, methods based on the QR-and SVD-factorization of A, and Lohner's QR-factorization method. The method based on the SVD-factorization is computationally less demanding and gives good results when the matrix is poorly scaled, it is superseded either by the naive iteration or by Lohner's method otherwise.
Published: 2022
Full Text: View/download PDF

22. Absolute Root Separation

Author: Andrej Dujella, Bruno Salvy, Yann Bugeaud, Tomislav Pejković, Wenjie Fang, Institut de Recherche Mathématique Avancée (IRMA), Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics [Zagreb], Faculty of Science [Zagreb], University of Zagreb-University of Zagreb, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), ANR-14-CE25-0018,Fast Relax,Approximation rapide et fiable(2014), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Computer Science - Symbolic Computation, FOS: Computer and information sciences, Polynomial, Current (mathematics), General Mathematics, Root (chord), Absolute value, 0102 computer and information sciences, Symbolic Computation (cs.SC), 01 natural sciences, Integer, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Applied mathematics, Number Theory (math.NT), 0101 mathematics, Mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Mathematics - Number Theory, Degree (graph theory), 010102 general mathematics, Symmetric function, Mathematics - Classical Analysis and ODEs, 010201 computation theory & mathematics, Bounded function, polynomials, root separation
Abstract: International audience; The absolute separation of a polynomial is the minimum nonzero difference between the absolute values of its roots. In the case of polynomials with integer coefficients, it can be bounded from below in terms of the degree and the height (the maximum absolute value of the coefficients) of the polynomial. We improve the known bounds for this problem and related ones. Then we report on extensive experiments in low degrees, suggesting that the current bounds are still very pessimistic.
Published: 2019

23. Affine Multibanking for High-Level Synthesis

Author: Ilham Lasfar, Christophe Alias, Matthieu Moy, Rémy Neveu, Alexis Carré, CASH - Compilation and Analysis, Software and Hardware (CASH), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Inria - Research Centre Grenoble – Rhône-Alpes, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Compilation et Analyse, Logiciel et Matériel (CASH), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: polyhedral mode, data restructuring, multibanking, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, High-Level Synthesis, FPGA
Abstract: In the last decade, FPGAs appeared as a credible alternative for big data and high-performance computing applications. However, programming an FPGA is tedious: given a function to implement, the circuit configuration must be built from scratch by the developer. Hence the emergence of high-level circuit compilers (high-level synthesis, HLS), able to translate a C program to an FPGA circuit configuration. Unlike software parallelization, there is no operating system to place the computation and the memory at runtime. All the parallelization decisions must be done at compile time. In this report, we address the compilation of data placement under parallelism and resource constraints. We propose an HLS algorithm able to partition the data across memory banks, so parallel access will target distinct banks to avoid data transfer serialization. Our algorithm is able to minimize the number of banks and the maximal bank size.; Dans la derniere decennie, les FPGA sont apparus comme une alternative credible pour le big data et le calcul haute performance. Malheureusement, la programmation des FPGA requiert la conception d’une configuration de circuit, ce qui est hors d’atteinte pour un programmeur. D’où l’émergence de la synthèse de circuit haut-niveau (High-Level Synthesis, HLS), capable de compiler un code C canonique en configuration de circuit FPGA. Contrairement `a la parallélisation logicielle, toutes les décisions de placement des données et des calculs doivent être prises statiquement, à la compilation. Dans ce rapport, nous ́étudions la compilation d’un placement de données sous contrainte de parallélisme et de taille. Nous proposons un algorithme de HLS capable de partitionner les données sur des bancs, de sorte que deux données accédées en même temps soient sur deux bancs différents, et puissent ainsi être accessibles en parallèle.Notre algorithme est capable de trouver une partition qui minimise le nombre de bancs et la taille maximale d’un banc.
Published: 2021

24. Shared-memory implementation of the Karp-Sipser kernelization process

Author: Langguth, Johannes, Panagiotas, Ioannis, Uçar, Bora, University of Bergen (UiB), ComplexNetworks, LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We investigate the parallelization of the Karp-Sipser kernelization technique, which constitutes the central part of the well-known Karp-Sipser heuristic for the maximum cardinality matching problem. The technique reduces a given problem instance to a smaller but equivalent one, by repeated applications of two operations: vertex removal, and merging two vertices. The operation of merging two vertices poses the principal challenge in parallelizing the technique. We describe an algorithm that minimizes the need for synchronization and present an efficient shared-memory parallel implementation of the kernelization technique for bipartite graphs. Using extensive experiments on a variety of multicore CPUs, we show that our implementation scales well up to 32 cores on one socket.
Published: 2021

25. Solution de gestion pilotée par les données pour les applications Deep Learning basées sur des microservices

Author: Houmani, Zeina, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Rutgers Discovery Informatics Institute (RDI2), Rutgers, The State University of New Jersey [New Brunswick] (RU), Rutgers University System (Rutgers)-Rutgers University System (Rutgers), Université de Lyon, Eddy Caron, and Daniel Balouek-Thomert
Subjects: Apprentissage profond, Qualité de service, Real-time processing, Software architecture, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Traitement en temps réel, Edge computing, Load shedding, Computing Continuum, Data-driven management, Architecture logicielle, Deep Learning, Microservices, Quality of service, Gestion pilotée par les données, Répartition des tâches, Cloud computing, Task allocation
Abstract: We live in a new era of Big Data, the era of insights. While our capacity to collect real-time data has grown significantly over the past decade, our ability to analyze that data to turn it into knowledge has not kept pace. With new generations of devices and network technologies, the focus of Big Data is shifting toward the design of tools and applications able to extract information from collected data. The majority of emerging applications present expectations of near-real-time processing to maintain the validity of their results. However, guaranteeing their performance requirements is hampered by the traditional Cloud system designs and management strategies. Current systems for Big Data applications rely on heterogeneous resources distributed across the constrained Edge and the powerful Cloud. In addition, the applications are now created as a set of self-contained microservices, developed by independent teams following the DevOps practices. This evolution of systems designs has introduced extreme heterogeneity and uncertainty into emerging applications, highlighting the limitations of traditional management strategies.In this thesis, we focus on designing a system for Big Data applications that rethinks existing management strategies with a particular emphasis on the heterogeneity of incoming data, applications, and resources. We first study the decoupling of data producers and consumers in emerging microservice-based applications as the entry point to effectively leverage available services, even newly published ones. Accordingly, we propose a data-driven service discovery framework based on data-centric service descriptions and rely on a Peer-to-Peer data-driven architecture. In addition, we present an adaptation scheme that scales deployed microservices to tackle the impact of fluctuating load on real-time performance. Second, we investigate the trade-off between the quality and urgency of the results in Big Data applications as a promising strategy to overcome the limited and heterogeneous capacity of system resources. In particular, we present a data-driven workflow scheduling approach to distribute microservices across the edge of the network, the core, and along the data path. Additionally, we propose a data adaptation strategy that reduces the quality of incoming data when potential quality-latency trade-off optimizations are available. We then apply the proposed approaches in the context of Deep Learning applications.; La capacité à collecter des données en temps réel a considérablement augmenté au cours de la dernière décennie. Pourtant, la capacité d'analyser ces données pour les exploiter n'a pas suivi la même progression. Avec le développement des appareils connectés et des technologies réseau, le Big Data a fait émerger des outils et des applications capables d'extraire des informations à partir des données collectées. La majorité des applications issues du Big Data nécessitent un traitement en temps réel pour maintenir la pertinence de leurs résultats. Cependant, garantir la performance en temps réel est entravé par les stratégies de gestion traditionnelles des systèmes Cloud. Les systèmes actuels pour les applications Big Data reposent sur des ressources hétérogènes allant de la périphérie du réseau (faible latence mais puissance limitée) jusqu'au Cloud (latence importante mais disposant d'importante puissance de traitement). Par ailleurs, les applications sont de plus en plus créées sous la forme d'un ensemble de services autonomes, développés par des équipes indépendantes selon les pratiques DevOps. Cette évolution des conceptions de systèmes a introduit une hétérogénéité et une incertitude extrêmes dans les applications émergentes, mettant en évidence les limites des stratégies de gestion traditionnelles. Cette thèse s'intéresse à la conception d'un système pour les applications Big Data (puis plus précisément des applications de Deep Learning) qui repense les stratégies de gestion existantes avec un accent particulier sur l'hétérogénéité des données entrantes, des applications et des ressources. Nous étudions d'abord le découplage des producteurs et consommateurs de données dans les applications basées sur des microservices en tant que point d'entrée pour exploiter efficacement les services disponibles, même ceux récemment publiés. En conséquence, nous proposons une approche de découverte de services basé sur des descriptions de services et sur une architecture Peer-to-Peer centrées sur les données. De plus, nous présentons un schéma d'adaptation qui adapte les microservices déployés pour contrôler l'impact de la fluctuation de la charge sur les performances des applications. Deuxièmement, pour surmonter la capacité limitée et hétérogène des ressources système, nous étudions le compromis entre la qualité et l'urgence des résultats dans les applications Big Data distribuées sur un continuum Edge-to-Cloud. En particulier, nous présentons une approche basée sur les données pour distribuer les workflows basés sur des microservices sur le continuum. De plus, nous proposons une stratégie d'adaptation des données qui réduit la qualité des données entrantes lorsque des optimisations potentielles de compromis qualité-latence sont disponibles. Nous appliquons ensuite les approches proposées dans le cadre d'applications de Deep Learning.
Published: 2021

26. Towards Trace-Based Array Contraction

Author: Thievenaz, Hugo, Kimura, Keiji, Alias, Christophe, CASH - Compilation and Analysis, Software and Hardware (CASH), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria), Waseda University, Inria, Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), and Waseda University [Tokyo, Japan]
Subjects: [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], contraction de tableaux, ACM: D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.4: Processors/D.3.4.1: Compilers, array contraction, analyse dynamique, dynamic analysis, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Compilation, polyhedral model, modèle polyédrique
Abstract: Array contraction is a compilation optimization used to reduce the memory con-sumption, by shrinking the size of temporary arrays while preserving the correctness. The usualapproach to this problem is to perform a static analysis of the given program, creating overhead inthe compilation cycle. In this report, we take a look at exploiting execution traces of programs ofthe polyhedral model, in order to infer reduced sizes for the temporary arrays used during calcu-lations. We designed a five step process to reduce the storage requirements of a temporary arrayof a given scheduled program, in which we used an algorithm to deduce array access functionsfor which bounds are modulos of affine functions of parameters and counters of the program. Ourpreliminary results show reductions of an order of magnitude on several benchmarks examples fromthe polyhedral community.; La contraction de tableau est une optimisation de compilation servant à amoindrir les coûts en mémoire, en réduisant la taille des tableaux temporaires sans en altérer l’exactitude du résultat. L’approche habituelle pour ce problème est l’analyse statique du programme, ce qui engendre plus de travail dans le cycle de compilation. Nous étudions les traces d’exécution de programmes du modèle polyédrique, afin d’en inférer des tailles réduites pour ces tableaux temporaires. Nous proposons une méthode en cinq étapes pour réaliser la contraction de tableaux sur un programme déjà ordonné, comprenant l’utilisation d’un algorithme pour déduire des fonctions d’accès aux tableaux affines. Nos résultats préliminaires comprennent des réductions d’un ordre de grandeur sur plusieurs exemples de la communauté polyédrique.
Published: 2021

27. Distances de Diffusion-Wasserstein pour les graphes attribués

Author: Barbe, Dominique, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Université de Lyon, Paulo Gonçalvès, and STAR, ABES
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Heat Equation, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, Optimal Transport, Théorie des, Équation de la chaleur, Traitement du signal, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Graphes, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Graph Theory, Signal Processing, Transport optimal de mesure, Graphes, Théorie des
Abstract: This thesis is about the definition and study of the Diffusion-Wasserstein distances between attributed graphs.An attributed graph is a collection of points with individual descriptions (features) and links between them (structure), like molecules or a social network. The Diffusion-Wasserstein distance is a generalization of the Wasserstein distance. It defines a metric for attributed graphs, and allow the computation of a transport map between them. It exploits the graph diffusion process to define new features for the nodes, and compare them. The diffusion time τ acts as a hyper-parameter, weighting the relative importance of the features and the structure. Compared to other transport distances that take into account features and a graph structure, the Diffusion-Wasserstein distance is faster to compute and yields better results in Domain Adaptation tasks.The computational side of the diffusion process received special attention. We used polynomial approximation using a Chebychev basis to accelerate these computations. We proved a new bound for the approximation error of the exponential operator, and showed how parts of the computation can be re-used for new diffusion times τ.A specific heuristic was developed to choose the diffusion time τ. It works by minimizing a function akin to a triplet-loss. I uses impostors, synthetic graphs built to be dissimilar in specific ways to the original attributed graphs whose distance is required. This heuristic yields better results for our method than the circular validation criterion used in Domain Adaptation., Ces travaux ont porté sur la définition et l’étude de la distance de Diffusion-Wasserstein entre graphes attribués. Les graphes attribués sont des collections de points avec une description individuelle (attributs) et des liens entre eux (structure de graphe), comme une molécule ou un réseau social. La distance de Diffusion-Wasserstein est une généralisation de la distance de Wasserstein ; elle permet de définir une distance entre des graphes attribués, et de calculer un plan de transport entre eux. Son fonctionnement exploite la diffusion dans le graphe pour définir de nouveaux attributs et les comparer. Le temps de diffusion τ joue le rôle d’hyper-paramètre, contrôlant l’importance donnée aux attributs et à la structure. Comparée à d’autres distances de transport qui prennent en compte attributs et structure de graphe, la distance de Diffusion-Wasserstein est plus rapide à calculer, et donne les meilleures performances dans plusieurs tâches d’apprentissage.Le calcul du processus de diffusion a reçu une attention particulière. Ces travaux ont porté sur une approximation à base de polynômes de Tchebychev. Cette approximation permet d’accélérer le calcul de la diffusion, et une nouvelle borne de l’erreur d’approximation qui améliore l’état de l’art a été prouvée. Un heuristique spéciale pour le choix du temps de diffusion τ a été définie. Celle-ci se base sur la minimisation d’une fonction, semblable à une triplet-loss, qui utilise des imposteurs, des graphes attribués construits pour être dissimilaires aux données initiales. Cette heuristique obtient de meilleurs résultats que le critère de validation circulaire utilisé jusqu’ici.
Published: 2021

28. Subspace Detours Meet Gromov-Wasserstein

Author: Clément Bonet, Titouan Vayer, Nicolas Courty, François Septier, Lucas Drumetz, Université de Bretagne Sud (UBS), Laboratoire de Mathématiques de Bretagne Atlantique (LMBA), Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Equipe Observations Signal & Environnement (Lab-STICC_OSE), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), Département Mathematical and Electrical Engineering (IMT Atlantique - MEE), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), École normale supérieure de Lyon (ENS de Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Observation de l’environnement par imagerie complexe (OBELIX), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), IMT Atlantique (IMT Atlantique), ANR-16-IDEX-0005,IDEXLYON,IDEXLYON(2016), École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Industrial engineering. Management engineering, Machine Learning (stat.ML), 010103 numerical & computational mathematics, T55.4-60.8, 01 natural sciences, Machine Learning (cs.LG), Theoretical Computer Science, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Knothe-Rosenblatt, FOS: Mathematics, Gromov-Wasserstein, subspace detours, 0101 mathematics, [STAT.CO]Statistics [stat]/Computation [stat.CO], Mathematics - Optimization and Control, Gromov–Wasserstein, Knothe–Rosenblatt, Numerical Analysis, [STAT.AP]Statistics [stat]/Applications [stat.AP], 010102 general mathematics, QA75.5-76.95, optimal transport, Computational Mathematics, Computational Theory and Mathematics, Optimization and Control (math.OC), Electronic computers. Computer science, [STAT.ME]Statistics [stat]/Methodology [stat.ME], [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract: International audience; In the context of optimal transport methods, the subspace detour approach was recently presented by Muzellec and Cuturi (2019). It consists in building a nearly optimal transport plan in the measures space from an optimal transport plan in a wisely chosen subspace, onto which the original measures are projected. The contribution of this paper is to extend this category of methods to the Gromov-Wasserstein problem, which is a particular type of transport distance involving the inner geometry of the compared distributions. After deriving the associated formalism and properties, we also discuss a specific cost for which we can show connections with the Knothe-Rosenblatt rearrangement. We finally give an experimental illustration on a shape matching problem.
Published: 2021

29. An analysis of Ermakov-Zolotukhin quadrature using kernels

Author: Belhadji, Ayoub, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), University of Lyon, ENS de Lyon, Univ. Claude Bernard, Lyon, 69007, France, ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML)
Subjects: Physics::Computational Physics, [STAT.CO]Statistics [stat]/Computation [stat.CO], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Mathematics::Numerical Analysis
Abstract: International audience; We study a quadrature, proposed by Ermakov and Zolotukhin in the sixties, through the lens of kernel methods. The nodes of this quadrature rule follow the distribution of a determinantal point process, while the weights are defined through a linear system, similarly to the optimal kernel quadrature. In this work, we show how these two classes of quadrature are related, and we prove a tractable formula of the expected value of the squared worst-case integration error on the unit ball of an RKHS of the former quadrature. In particular, this formula involves the eigenvalues of the corresponding kernel and leads to improving on the existing theoretical guarantees of the optimal kernel quadrature with determinantal point processes.
Published: 2021

30. An Anonymous Trace-and-Revoke Broadcast Encryption Scheme

Author: Damien Stehlé, Olivier Blazy, Duong Hieu Phan, Huyen Nguyen, Sayantan Mukherjee, XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institut Polytechnique de Paris (IP Paris), Département Informatique et Réseaux (INFRES), Télécom ParisTech, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Cybersécurité et Cryptographie (C2), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, and ANR-16-CE39-0004,IDFIX,Cryptographie basée sur l'identité, pour l'identification et les échanges(2016)
Subjects: 0303 health sciences, Software_OPERATINGSYSTEMS, Cryptographic primitive, Traceability, Revocation, business.industry, Computer science, Data_CODINGANDINFORMATIONTHEORY, 0102 computer and information sciences, 01 natural sciences, Set (abstract data type), 03 medical and health sciences, 010201 computation theory & mathematics, Ciphertext, [INFO]Computer Science [cs], business, Broadcast encryption, 030304 developmental biology, Functional encryption, Computer network, Anonymity
Abstract: International audience; Broadcast Encryption is a fundamental cryptographic primitive, that gives the ability to send a secure message to any chosen target set among registered users. In this work, we investigate broadcast encryption with anonymous revocation, in which ciphertexts do not reveal any information on which users have been revoked. We provide a scheme whose ciphertext size grows linearly with the number of revoked users. Moreover, our system also achieves traceability in the black-box confirmation model.Technically, our contribution is threefold. First, we develop a generic transformation of linear functional encryption toward trace-and-revoke systems. It is inspired from the transformation by Agrawal et al. (CCS’17) with the novelty of achieving anonymity. Our second contribution is to instantiate the underlying linear functional encryptions from standard assumptions. We propose a DDH-based construction which does no longer require discrete logarithm evaluation during the decryption and thus significantly improves the performance compared to the DDH-based construction of Agrawal et al.. In the LWE-based setting, we tried to instantiate our construction by relying on the scheme from Wang et al. (PKC’19) but finally found an attack to this scheme. Our third contribution is to extend the 1-bit encryption from the generic transformation to n-bit encryption. By introducing matrix multiplication functional encryption, which essentially performs a fixed number of parallel calls on functional encryptions with the same randomness, we can prove the security of the final scheme with a tight reduction that does not depend on n, in contrast to employing the hybrid argument.
Published: 2021

31. Improving the Spatial Reuse in IEEE 802.11ax WLANs: A Multi-Armed Bandit Approach

Author: Anthony Bardou, Anthony Busson, Thomas Begin, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Holistic Wireless Networks (hownet), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), and Université de Lyon
Subjects: Computer science, Distributed computing, Quality of service, 020206 networking & telecommunications, 02 engineering and technology, Reuse, Thompson Sampling, Network topology, Clear Channel Assessment, Multi-armed bandit, IEEE 802.11ax, Network simulation, Machine Learning, WLAN, Channel Reuse, Power Control, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Thompson sampling, Power control
Abstract: International audience; The latest amendment 802.11ax to the IEEE 802.11 standard, better known by its commercial name Wi-Fi 6, includes a feature that aims at improving the spatial reuse of a channel: each device can adapt its Clear Channel Assessment sensitivity threshold and its transmission power. In this paper, we use the Multi-Armed Bandit (MAB) framework to propose a centralized solution to dynamically adapt these parameters. We propose a new approach based on a Gaussian mixture to sample new network configurations, a specific reward function that prevents starvations when maximized, as well as a method based on Thompson Sampling to select the best network configuration. We evaluate our solution using the network simulator ns-3 and different topologies. Simulation results confirm the large benefits that 802.11ax may bring to spatial reuse. They also demonstrate the efficiency of our solution in finding appropriate parameter configurations that significantly improve the quality of service of the networks. CCS CONCEPTS • General and reference → Performance; • Networks → Network control algorithms; Network simulations; Wireless local area networks; • Theory of computation → Bayesian analysis; Reinforcement learning.
Published: 2021

32. Exploiting Frame Aggregation to Enhance Access Point Selection

Author: Anthony Busson, Hervé Rivano, Nour El Houda Bouzouita, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, ALGorithmes et Optimisation pour Réseaux Autonomes (AGORA), CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria), Holistic Wireless Networks (hownet), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)
Subjects: Markov chain, Wireless network, Computer science, business.industry, Aggregated MAC protocol data unit (A-MPDU), 020302 automobile design & engineering, 020206 networking & telecommunications, 02 engineering and technology, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Frame aggregation, 0203 mechanical engineering, Telecommunications link, Metric (mathematics), 0202 electrical engineering, electronic engineering, information engineering, Performance evaluation, Network load, [INFO]Computer Science [cs], Quality of experience, business, Mobile device, Communication channel, Computer network, IEEE 802.11 networks
Abstract: International audience; IEEE 802.11 (known as Wi-Fi) has emerged as a vital wireless network access technology for mobile devices. By providing the potential for high connectivity speeds, this technology has led to a dramatic rise in the number of access points (APs). In such environments, mobile devices have the choice to join several Wi-Fi networks. Despite its importance to user Quality of Experience (QoE), the AP selection is still trivial since it focuses at best on the received signal strength if not only the user's history. Crucial metrics that capture the overall dynamics of the AP load condition, such as the network load, are not taken into account. In this paper, we propose to use the Busy Time Fraction (BTF) as a metric to choose the best AP to attach to. The BTF level of a given channel is inferred based on the frame aggregation scheme proposed since the 802.11n standard. In this regard, we propose an analytical model based on a Discrete-Time Markov chain that discerns the theoretical DownLink aggregation levels for probe traffic concurrent to cross traffic. We validate the accuracy of our proposed approach against ns-3 simulations under several scenarios.
Published: 2021

33. Towards a Throughput and Energy Efficient Association Strategy for Wi-Fi/LiFi Heterogeneous Networks

Author: Thomas Begin, Esther Guérin, Isabelle Guérin Lassous, Anthony Busson, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Holistic Wireless Networks (hownet), Laboratoire de l'Informatique du Parallélisme (LIP), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer science, media_common.quotation_subject, local search, Fidelity, 02 engineering and technology, 0203 mechanical engineering, energy consumption, 0202 electrical engineering, electronic engineering, information engineering, score, Local search (optimization), [INFO]Computer Science [cs], heterogeneous, Baseline (configuration management), Throughput (business), Wi-Fi, media_common, SIMPLE (military communications protocol), business.industry, association, 020206 networking & telecommunications, 020302 automobile design & engineering, Energy consumption, business, strategy, Heterogeneous network, Computer network, Efficient energy use, LiFi
Abstract: International audience; In very dense or ultra-dense scenarios wherein Wi-Fi alone may not be enough to accommodate the needs of all stations, LiFi access points can help alleviate the strain on the Wi-Fi by offloading some Wi-Fi traffic to LiFi. We study the issue of associating stations in a Wi-Fi/LiFi heterogeneous network composed of a Wi-Fi access point and multiples LiFi access points. We propose a conceptually simple and easy to implement solution to search and find an efficient mapping for the associations between stations and access points using analytical performance models for the individual throughput of each station and for the overall network energy consumption. Using two realistic deployments of heterogeneous networks for offices, we have evaluated the effectiveness of our solution at discovering better trade-offs than baseline strategies. Our numerical results show that significant gains can be obtained in terms of the throughput of the stations as well as overall energy consumption. CCS CONCEPTS • Networks → Wireless access networks.
Published: 2021

34. Aspects cryptographiques des réseaux orthogonaux

Author: Nguyen, Thanh Huyên, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon, and Damien Stehlé
Subjects: Trace and Revoke, Orthogonal lattices, Anonymat, Leftover hash lemma, Integer-SIS, Systèmes de traçage et de révocation, Integer-LWE, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Lemme des restes du hachage, Paramètre de lissage, Anonymity, Cryptographie basée sur les réseaux euclidiens, Smoothing parameter, Réseaux orthogonaux, Lattice-based cryptography
Abstract: Lattice-based cryptography aims at harnessing the security of cryptographic primitives in the conjectured hardness of well-identified and well-studied algorithmic problems involving Euclidean lattices. This approach leads to more efficient primitives, increased security (the most common lattice problems are conjectured quantum-hard), and improved cryptographic functionalities (fully homomorphic encryption, functional encryption, program obfuscation, etc). A less common but still recurring family of lattices are the so-called orthogonal lattices where the matrix is often sampled from a Gaussian distribution. In this thesis, we study the cryptographic aspects of orthogonal lattices. When lattices have turned into a major build block in designing cryptographic primitives, orthogonal lattices have been used in various constructions such as cryptographic multilinear maps, traitor-tracing schemes, and inner product functional encryption. Firstly, we consider the successive minima and the smoothing parameter of random orthogonal lattices. The main motivation (and our result) is a generalization of the leftover hash lemma (LHL) to lattices and discrete Gaussian distributions. Our results improve the probabilistic upper bound on the smoothing parameter and give a probabilistic upper bound on the last minimum of the orthogonal lattice.Next, we investigate broadcast encryption with anonymous revocation, in which ciphertexts do not reveal any information about which users have been revoked. The orthogonal lattices are involved in the security proofs of these protocols. We describe a generic transformation of linear functional encryption toward the broadcast systems supporting the trace and revoke with the novelty of achieving anonymity.Finally, a fundamental problem related to lattices is the learning with errors (LWE) problem which is an amazingly versatile basis for cryptographic constructions. We introduce a new variant of LWE, called on the integers because it does not involve any modular reduction. We show that the new problem is at least as hard the standard problems over lattices.; La cryptographie à base de réseaux euclidiens vise à faire reposer la sécurité des primitives cryptographiques sur la difficulté conjecturée de problèmes algorithmiques bien identifiés et bien étudiés impliquant les réseaux euclidiens. Cette approche conduit à des primitives plus efficaces, à une sécurité accrue (les problèmes de réseaux les plus courants sont conjecturés quantiquement difficiles) et à des fonctionnalités cryptographiques améliorées (chiffrement entièrement homomorphe, chiffrement fonctionnel, obscurcissement de programme, etc). Une famille de réseaux moins courante mais récurrente sont les réseaux dits orthogonaux où la matrice est souvent échantillonnée à partir d'une distribution gaussienne. Dans cette thèse, nous étudions certains aspects cryptographiques des réseaux orthogonaux. Lorsque les réseaux sont devenus un élément majeur de la conception de primitives cryptographiques, les réseaux orthogonaux ont été utilisés dans diverses constructions telles que les fonctions multilinéaires cryptographiques, les schémas de traçage des traîtres et le chiffrement fonctionnel pour le produit scalaire. Tout d'abord, nous considérons les minima successifs et le paramètre de lissage de réseaux orthogonaux aléatoires. La motivation principale (et notre résultat) est une généralisation du lemme des restes du hachage (LHL pour Left Over Hash Lemma) aux réseaux et aux distributions gaussiennes discrètes. Nos résultats améliorent la borne supérieure probabiliste sur le paramètre de lissage et donnent une borne supérieure probabiliste sur le plus grand minimum du réseau orthogonal.Ensuite, nous étudions le chiffrement de diffusion avec révocation anonyme, dans lequel les chiffrés ne révèlent aucune information portant sur les utilisateurs qui ont été révoqués. Les réseaux orthogonaux sont impliqués dans les preuves de sécurité de ces protocoles. Nous décrivons une transformation générique du chiffrement fonctionnel linéaire vers des systèmes de diffusion supportant le traçage et la révocation, avec comme nouveauté l'obtention d'une propriété d'anonymat. Enfin, un problème fondamental lié aux réseaux est l’apprentissage avec erreurs (LWE pour Learning With Errors) car il est une base polyvalente pour les constructions cryptographiques. Nous introduisons une nouvelle variante de LWE, dite sur les entiers car elle ne fait pas intervenir de réduction modulaire. Nous montrons que ce nouveau problème est au moins aussi difficile que des problèmes standard portant sur les réseaux euclidiens.
Published: 2021

35. S4BXI: the MPI-ready Portals 4 Simulator

Author: Matthieu Moy, Grégoire Pichon, Ludovic Henrio, Julien Emmanuel, Bull atos technologies, CASH - Compilation and Analysis, Software and Hardware (CASH), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: Interconnection, Computer science, Design space exploration, Message Passing Interface, Portals 4, Supercomputer, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, BXI, SimGrid, HPC, Interconnect, MPI, Actor model, Simulation
Abstract: International audience; We present a simulator for High Performance Computing (HPC) interconnection networks. It models Portals 4, a standard low-level API for communication, and it allows running unmodified applications that use higher-level network APIs such as the Message Passing Interface (MPI). It is based on SimGrid, a framework used to build single-threaded simulators based on a cooperative actor model. Unlike existing tools like SMPI, we rely on an actual MPI implementation, hence our simulation takes into account MPI's implementation details in the performance. This paper also presents a case study using the BullSequana eXascale Interconnect (BXI) made by Atos, which highlights how such a simulator can help design space exploration (DSE) for new interconnects.
Published: 2021

36. Shelf schedules for independent moldable tasks to minimize the energy consumption

Author: Benoit, Anne, Canon, Louis-Claude, Elghazi, Redouane, Heam, Pierre-Cyrille, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (INRIA), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), and ANR-17-EURE-0002,EIPHI,Ingénierie et Innovation par les sciences physiques, les savoir-faire technologiques et l'interdisciplinarité(2017)
Subjects: Energy minimization, Évaluation empirique, Shelf scheduling, Minimisation d’énergie, Empirical evaluation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Ordonnancement par étagères
Abstract: International audience; Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan (P||C_max problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather of parallel moldable tasks that can decide their degree of parallelism at execution (i.e., on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One should decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, and simulations are performed to show the performance of the proposed algorithms.; L’ordonnancement de tâches indépendantes sur une plateforme parallèle est un problème vastement étudié, en particulier lorsque le but est de minimiser le temps d’exécution total, ou makespan (P||C_max en utilisant la notation de Graham). De nombreuses applications ne sont pas séquentielles, et sont plutôt des tâches parallélisables moldables, dont le degré de parallélisation peut être choisi à l’exécution (i.e., sur combien de processeurs elles sont exécutées). De plus, étant donné que la consommation énergétique des centres de données devient un sujet de plus en plus important, que ce soit d’un point de vue environnemental ou économique, la minimisation de la consommation d’énergie est un défi majeur à relever. La décision algorithmique à prendre concerne, pour l’exécution de chaque tâche, le nombre de processeurs ainsi que la vitesse des dits processeurs, dans le but de minimiser la consommation totale d’énergie. Nous nous intéressons plus précisément aux co-ordonnancements, dans lesquels les tâches sont partitionnées en étagères, et nous prouvons que la minimisation de la consommation d’énergie est un problème NP-complet lorsque l’énergie statique est consommée pendant la totalité de l’exécution de l’application. Nous fournissons tout de même un algorithme optimal dans le cas d’un ordonnancement sur une seule étagère, i.e., pour un ensemble de tâches commençant simultanément. Plusieurs résultats d’approximation sont prouvés, et des simulations sont effectuées pour exhiber la performance des algorithmes proposés
Published: 2021

37. Enabling microservices management for Deep Learning applications across the Edge-Cloud Continuum

Author: Houmani, Zeina, Balouek-Thomert, Daniel, Caron, Eddy, Parashar, Manish, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Scientific Computing and Imaging Institute (SCI Institute), University of Utah, This research is supported in part by the NSF under grantsnumbers OAC 1640834, OAC 1835692, and OCE 1745246., École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Deep Learning, Microservices, Real-time processing, Cloud computing, [INFO]Computer Science [cs], Edge computing, Computing Continuum, Task allocation
Abstract: International audience; Deep Learning has shifted the focus of traditional batch workflows to data-driven feature engineering on streaming data. In particular, the execution of Deep Learning workflows presents expectations of near-real-time results with user-defined acceptable accuracy. Meeting the objectives of such applications across heterogeneous resources located at the edge of the network, the core, and in-between requires managing trade-offs between the accuracy and the urgency of the results. However, current data analysis rarely manages the entire Deep Learning pipeline along the data path, making it complex for developers to implement strategies in real-world deployments. Driven by an object detection use case, this paper presents an architecture for time-critical Deep Learning workflows by providing a data-driven scheduling approach to distribute the pipeline across Edge to Cloud resources. Furthermore, it adopts a data management strategy that reduces the resolution of incoming data when potential trade-off optimizations are available. We illustrate the system's viability through a performance evaluation of the object detection use case on the Grid'5000 testbed. We demonstrate that in a multiuser scenario, with a standard frame rate of 25 frames per second, the system speed-up data analysis up to 54.4% compared to a Cloud-only-based scenario with an analysis accuracy higher than a fixed threshold.
Published: 2021

38. A Polyhedral Approach for Auto-Parallelization using a Distributed Virtual Machine

Author: de Montis, Damien, Besnard, Jean-Baptiste, Alias, Christophe, ParaTools SAS, CASH - Compilation and Analysis, Software and Hardware (CASH), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), INRIA , LIP - ENS Lyon, Paratools, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: runtime scheduling, automatic parallelization, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Compilation, polyhedral model
Abstract: As parallel systems have to undergo an unprecedented transition towards more parallelism and hybridization, we propose to discuss the consequences on programming models. In particular, MPI and OpenMP may face some complexity barriers due to the added complexity required by such hardware. We propose to build from the ground up a new way to program a parallel system, relying both on a distributed runtime, unifying multiple nodes in a coherent ensemble, and on advanced tools from the Polyhedral model. We first describe the Distributed Virtual Machine(DVM) runtime establishing a data-flow environment suitable to the polyhedral transformations.We present and identify what we have seen as key components in such a system, transposing loop nests to a distributed set of machines thanks to a pragma notation combined with an automatic tiling approach. Eventually, while presenting results we open the discussion of remaining challengesand some potential mitigation.
Published: 2021

39. Compiling pattern matching to in-place modifications

Author: Laure Gonnord, Gabriel Radanne, Paul Iannetta, École normale supérieure de Lyon (ENS de Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), CASH - Compilation and Analysis, Software and Hardware (CASH), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Conception et d'Intégration des Systèmes (LCIS), Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA), Conception et Test de SYStèmes embarqués (CTSYS ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Institut National de Recherche en Informatique et en Automatique (Inria), ANR-17-CE23-0004,CODAS,Ordonnancement de programmes à structures de données complexes(2017), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, and École normale supérieure - Lyon (ENS Lyon)
Subjects: Computer science, Programming language, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, code generation, computer.software_genre, ADT, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], rewriting, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Algebraic data type, compilation, Polytope model, Code generation, Use case, Pattern matching, Compiler, Rewriting, Representation (mathematics), computer
Abstract: International audience; Algebraic data types and pattern matching are popular tools to build programs manipulating complex datastructures in a safe yet efficient manner. On top of its safety advantages, compilation techniques can turn pattern matching into highly efficient deconstruction code for immutable use cases. Conversely, high-performance datastructures and languages prefer to leverage (controlled) mutations to maximize time and memory efficiency. Algebraic data types provide a natural framework to efficiently describe \emph{in-place} transformations as rewrite rules. Such representation coul take advantage of parallelism opportunities that appear in tree-like structures. We present early steps towards a new technique to compile pattern matching as parallel in-place modifications of the underlying memory representation. Towards this goal, we combine the usual language approach which is common in pattern-matching compilation with tools from the polyhedral model, which is commonly used in high-performance code generation to output efficient C code. We present our formalism, along with a prototype implementation.
Published: 2021

40. Bifurcated Signatures: Folding the Accountability vs. Anonymity Dilemma into a Single Private Signing Scheme

Author: Khoa D. Nguyen, Benoît Libert, Moti Yung, Thomas Peters, Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Nanyang Technological University [Singapour], Université Catholique de Louvain = Catholic University of Louvain (UCL), Fonds National de la Recherche Scientifique [Bruxelles] (FNRS), Google Inc, Research at Google, Khoa Nguyen was supported in part by the Gopalakrishnan - NTU PPF 2018, by A*STAR, Singapore under research grant SERC A19E3b0099, and by Vietnam National University HoChiMinh City (VNU-HCM) under grant number NCM2019-18-01. Thomas Peters is a research associate of the Belgian Fund for Scientific Research (F.R.S.-FNRS)., ANR-16-CE39-0006,ALAMBIC,AppLicAtions de la MalléaBIlité en Cryptographie(2016), European Project: 780701,PROMETHEUS(2018), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and UCL - SST/IRMP - Institut de recherche en mathématique et physique
Subjects: Scheme (programming language), Orthogonality (programming), Computer science, Cryptography, group signatures, predicate-based privacy, 0102 computer and information sciences, 02 engineering and technology, Computer security, computer.software_genre, privacy, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, computer.programming_language, Computer Science::Cryptography and Security, anonymity, business.industry, 020206 networking & telecommunications, Folding (DSP implementation), Dilemma, accountability, 010201 computation theory & mathematics, Accountability, business, conditional traceability, Versa, computer, Anonymity, New primitive
Abstract: International audience; Over the development of modern cryptography, often, alternative cryptographic schemes are developed to achieve goals that in some important respect are orthogonal. Thus, we have to choose either a scheme which achieves the first goal and not the second, or vice versa. This results in two types of schemes that compete with each other. In the basic area of user privacy, specifically in anonymous (multi-use credentials) signing, such an orthogonality exists between anonymity and accountability.The conceptual contribution of this work is to reverse the above orthogonality by design, which essentially typifies the last 25 years or so, and to suggest an alternative methodology where the opposed properties are carefully folded into a single scheme. The schemes will support both opposing properties simultaneously in a bifurcated fashion, where:First, based on rich semantics expressed over the message’s context and content, the user, etc., the relevant property is applied point-wise per message operation depending on a predicate; andSecondly, at the same time, the schemes provide what we call “branch-hiding;” namely, the resulting calculated value hides from outsiders which property has actually been locally applied.Specifically, we precisely define and give the first construction and security proof of a “Bifurcated Anonymous Signature” (BiAS): A scheme which supports either absolute anonymity or anonymity with accountability, based on a specific contextual predicate, while being branch-hiding. This novel signing scheme has numerous applications not easily implementable or not considered before, especially because: (i) the conditional traceability does not rely on a trusted authority as it is (non-interactively) encapsulated into signatures; and (ii) signers know the predicate value and can make a conscious choice at each signing time.Technically, we realize BiAS from homomorphic commitments for a general family of predicates that can be represented by bounded-depth circuits. Our construction is generic and can be instantiated in the standard model from lattices and, more efficiently, from bilinear maps. In particular, the signature length is independent of the circuit size when we use commitments with suitable efficiency properties.
Published: 2021

41. Faster Modular Composition

Author: Neiger, Vincent, Salvy, Bruno, Schost, Éric, Villard, Gilles, Sorbonne Université (SU), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), University of Waterloo [Waterloo], Cheriton School of Computer Science [Waterloo] (CS), Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, Computer Science - Symbolic Computation, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Computational Complexity, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Symbolic Computation (cs.SC), Computational Complexity (cs.CC)
Abstract: A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by $n$, the algorithm uses $O(n^{1.43})$ field operations, breaking through the $3/2$ barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require $O(n^{1.63})$ field operations in general, and ${n^{3/2+o(1)}}$ field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in ${n^{5/3+o(1)}}$ operations, while previous ones run in $O(n^2)$ operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation., 78 pages
Published: 2021

42. Semi-relaxed Gromov Wasserstein divergence with applications on graphs

Author: Vincent-Cuaz, Cédric, Flamary, Rémi, Corneli, Marco, Vayer, Titouan, Courty, Nicolas, Université Côte d'Azur (UCA), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, Observation de l’environnement par imagerie complexe (OBELIX), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), SIGNAL, IMAGE ET LANGAGE (IRISA-D6), and ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019)
Subjects: [STAT]Statistics [stat], [INFO]Computer Science [cs], [MATH]Mathematics [math]
Abstract: preprint under review; International audience; Comparing structured objects such as graphs is a fundamental operation involved in many learning tasks. To this end, the Gromov-Wasserstein (GW) distance, based on Optimal Transport (OT), has proven to be successful in handling the specific nature of the associated objects. More specifically, through the nodes connectivity relations, GW operates on graphs, seen as probability measures over specific spaces. At the core of OT is the idea of conservation of mass, which imposes a coupling between all the nodes from the two considered graphs. We argue in this paper that this property can be detrimental for tasks such as graph dictionary or partition learning, and we relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence. Aside from immediate computational benefits, we discuss its properties, and show that it can lead to an efficient graph dictionary learning algorithm. We empirically demonstrate its relevance for complex tasks on graphs such as partitioning, clustering and completion.
Published: 2021

43. Non-applicability of the Gaborit&Aguilar-Melchor patent to Kyber and Saber

Author: Lyubashevsky, Vadim, Stehlé, Damien, IBM Research Europe [Zürich], Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), ENS de Lyon, IBM Zürich, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: [INFO]Computer Science [cs]
Abstract: In the context of the NIST post-quantum cryptography project, there have been claims that the Gaborit&Aguilar-Melchor patent could apply to the Kyber and Saber encryption schemes. In this short note, we argue that these claims are in contradiction with the potential validity of the patent.
Published: 2021

44. Budget-aware Static Scheduling of Stochastic Workflows with DIET

Author: Caniou, Yves, Caron, Eddy, Kong Win Chang, Aurélie, Robert, Yves, Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: [INFO]Computer Science [cs]
Abstract: International audience; Previous work has introduced a Cloud platform model and budget-aware static algorithms to schedule stochastic workflows on such platforms. In this paper, we compare the performance of these algorithms obtained via simulation and via execution on an actual platform, Grid'5000. We focus on DIET, a widely used workflow engine, and detail the extensions that were implemented to conduct the comparison. We also detail additional code that we made available in order to automate and to ease the reproducibility of such experiments.
Published: 2021

45. Scheduling independent tasks under budget and time constraints

Author: Gao, Yiqin, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon, and Frédéric Vivien
Subjects: Deadline, Date limite, Scheduling, Plate-forme cloud, Ordonnancement, Tâches independantes, Budget, Cloud platform, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Independent tasks
Abstract: In this thesis, we design scheduling heuristics for independent tasks under budget and time constraints, in order to satisfy the requirement on performance or on energy consumption. The first three chapters of this thesis have performance as objective, while the fourth chapter focuses on energy-efficiency. The first three chapters have a common framework: We have a bag of tasks whose execution times follow some probability distributions. We can decide at any instant to interrupt the execution of a long running task and to launch a new one instead. The main questions are how many (or which) processors to enroll, and whether and when to interrupt tasks if they have been executing for a long time. In previous work, the problem has been dealt with on a homogeneous platform and with the same release time and deadline for all tasks. Our work extends the state-of-the-art in three directions: In the first work, we consider an heterogeneous platform. In the second work, we assume that the distribution of task execution times is unknown. In the third work, tasks are released periodically and have their own deadline. The fourth work considers a real-time framework. We have periodic tasks and an heterogeneous platform. We consider transient fault. Tasks are replicated to guarantee a pre-defined reliability threshold. We aim at find a heuristic which minimizes the expected energy consumption, while matching the deadline and reliability constraints of all tasks. This alls for a difficult trade-off between reliability and energy consumption.; De nos jours, l'informatique est un outil essentiel dans divers domaines de la recherche scientifique et dans notre vie quotidienne. Beaucoup des travaux informatiques, ou tâches, ont des échéances. D'autre part, le budget dont nous disposons est généralement limité. Afin de répondre aux exigences en termes de performances sous contraintes de budget et d'échéance, nous devons concevoir des heuristiques de planification pour améliorer les performances. En même temps, nous accordons de plus en plus d'attention à la protection de l'environnement. L'efficacité énergétique devient l'un des objectifs critiques dans une variété de problèmes. Ainsi, dans cette thèse, nous présentons des heuristiques d'ordonnancement pour des tâches indépendantes sous contraintes budgétaires et temporelles, qui cherchent à optimiser la performance ou la consommation d'énergie. Les trois premières parties de cette thèse ont la performance comme objectif, et nous traitons l'efficacité énergétique dans le quatrième. Les trois premiers travaux ont des conditions similaires : Nous avons un sac de tâches pour lesquelles les temps d'exécution suivent la même distribution. On peut décider à tout instant d'interrompre l'exécution d'une tâche et d'en lancer une nouvelle. Les principales questions sont de savoir combien (ou quels) processeurs utiliser, et si et quand interrompre les longues tâches. Dans un travail antérieur, les auteurs ont considéré une plateforme homogène et une échéance commune pour toutes les tâches. Nos travaux prolongent les travaux précédents dans trois directions : Premièrement, nous considérons une plateforme hétérogène. Deuxièmement, nous supposons que la distribution des temps d'exécution des tâches est inconnue. Troisièmement, les tâches arrivent périodiquement et ont leur propre échéance. Le quatrième travail se place dans un cadre temps-réel. Nous avons des tâches périodiques et une plateforme hétérogène. Nous considérons des pannes transitoires, et les tâches sont répliquées pour assurer un seuil de fiabilité prescrit. Nous n'avons plus de budget limité. En revanche, nous devons trouver une heuristique qui minimise la consommation d'énergie, tout en respectant les contraintes d'échéance et de fiabilité de toutes les tâches.
Published: 2021

46. Extension of Flocking Models to Environments with Obstacles and Degraded Communications

Author: Bonnefond, Alexandre, Simonin, Olivier, Guérin-Lassous, Isabelle, Robots coopératifs et adaptés à la présence humaine en environnements dynamiques (CHROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Holistic Wireless Networks (hownet), Laboratoire de l'Informatique du Parallélisme (LIP), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, 020901 industrial engineering & automation, [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, International Conferences with Proceedings, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], 02 engineering and technology, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Abstract: In this paper, we study existing flocking models and propose extensions to improve their abilities to deal with environments having obstacles impacting the communication quality. Often depicted as robust systems, there is yet a lack of understanding how flocking models compare and how they are impacted by the communication quality when they exchange control data. We extend two standard models to improve their ability to stay connected while evolving in environments with different obstacles distributions. By taking into account the radio propagation, we model the obstacles impact on communications in a simulator that we use to optimize flocking parameters. The simulation results show the efficiency of the proposed models and how they adapt to different environmental constraints.; International audience; In this paper, we study existing flocking models and propose extensions to improve their abilities to deal with environments having obstacles impacting the communication quality. Often depicted as robust systems, there is yet a lack of understanding how flocking models compare and how they are impacted by the communication quality when they exchange control data. We extend two standard models to improve their ability to stay connected while evolving in environments with different obstacles distributions. By taking into account the radio propagation, we model the obstacles impact on communications in a simulator that we use to optimize flocking parameters. The simulation results show the efficiency of the proposed models and how they adapt to different environmental constraints.
Published: 2021

47. Locality-Aware Scheduling of Independent Tasks for Runtime Systems

Author: Gonthier, Maxime, Marchal, Loris, Thibault, Samuel, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), STatic Optimizations, Runtime Methods (STORM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Grid5000, ANR-19-CE46-0009,SOLHARIS,Solveurs pour architectures hétérogènes utilisant des supports d'exécution, objectif scalabilité(2019), École normale supérieure de Lyon (ENS de Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest
Subjects: Politique d'éviction, Support d'exécution, Memory-aware scheduling, Eviction policy, Ordonnancement sous contrainte mémoire, [INFO]Computer Science [cs], Runtime systems, Tâches partageant des données, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Tasks sharing data
Abstract: International audience; A now-classical way of meeting the increasing demand for computing speed by HPC applications is the use of GPUs and/or other accelerators. Such accelerators have their own memory, which is usually quite limited, and are connected to the main memory through a bus with bounded bandwidth. Thus, particular care should be devoted to data locality in order to avoid unnecessary data movements. Task-based runtime schedulers have emerged as a convenient and efficient way to use such heterogeneous platforms. When processing an application, the scheduler has the knowledge of all tasks available for processing on a GPU, as well as their input data dependencies. Hence, it is able to order tasks and prefetch their input data in the GPU memory (after possibly evicting some previously-loaded data), while aiming at minimizing data movements, so as to reduce the total processing time. In this paper, we focus on how to schedule tasks that share some of their input data (but are otherwise independent) on a GPU. We provide a formal model of the problem, exhibit an optimal eviction strategy, and show that ordering tasks to minimize data movement is NP-complete. We review and adapt existing ordering strategies to this problem, and propose a new one based on task aggregation. These strategies have been implemented in the StarPU runtime system. We present their performance on tasks from tiled 2D and 3D matrix products. Our experiments demonstrate that using our new strategy together with the optimal eviction policy reduces the amount of data movement as well as the total processing time.; Une manière désormais classique de répondre à la demande croissante de puissance de calcul par les applications HPC est l'utilisation de GPU et autres accélérateurs. Ces accélérateurs ont leurs propre mémoire, qui est généralement assez limitée, et sont connectés à la mémoire principale via un bus dont la bande passante est bornée. Ainsi, une attention particulière doit être portée à la localité des données afin d'éviter des mouvements de données inutiles. Les ordonnanceurs des supports d'exécution à base de tâches sont un moyen pratique et efficace d'utiliser de telles plateformes hétérogènes. Lors du traitement d'une application, l'ordonnanceur a la connaissance de toutes les tâches disponibles, ainsi que leurs dépendances. Ainsi, il est capable d'ordonner les tâches et de pré-charger leurs données d'entrée dans la mémoire du GPU (après avoir éventuellement évincé certaines données précédemment chargées), tout minimisant les transferts de données, afin de réduire le temps d'exécution total. Dans ce papier, nous nous concentrons sur la façon de planifier des tâches qui partagent des données (mais sont par ailleurs indépendantes) sur un GPU. Nous fournissons un modèle formel du problème, nous présentons une stratégie d'éviction optimale et nous montrons qu'ordonner des tâches afin de minimiser les mouvement des données est un problème NP-complet. Nous adaptons des stratégies d'ordonnancement existantes à ce problème, et nous en proposons une nouvelle basé sur l'agrégation des tâches. Ces stratégies ont été implémentées sur le support d'exécution StarPU. Nous présentons leurs performances sur des produits matriciels 2D, 3D, la factorisation de Cholesky et un produit matriciel 2D randomisé. Nos expériences démontrent qu'en utilisant notre nouvelle stratégie, avec la politique d'éviction optimale, nous réduisons la quantité de transferts de données ainsi que le temps de traitement total.
Published: 2021

48. Isomorphisms are back!: Smart indexing for function retrieval by unification modulo type isomorphisms

Author: Allain, Clément, Radanne, Gabriel, Gonnord, Laure, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), CASH - Compilation and Analysis, Software and Hardware (CASH), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), ANR-17-CE23-0004,CODAS,Ordonnancement de programmes à structures de données complexes(2017), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: search, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], tries, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], types, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract: International audience; Sometimes, we need a function so deeply that we have to go out and search for it. How do we find it ? Sometimes, we have clues: a function which manipulates list is probably in the Listmodule. . . but not always! Sometimes, all we have is its functionality: doing the sum of a list of integers. Unfortunately, search by functionality is difficult. Rittri [1] proposed an approximation: use the type of the function as a key to search through libraries: in our case, int list->int. To avoid stumbling over details such as the order of arguments, he proposed to use matching modulo type isomorphism – a notion broader than syntactic equality. Unfortunately, algorithms for unification modulo type isomorphisms are extremely costly. Doing an exhaustive search over the whole ML ecosystem was possible at the time (with a standard library of 294 functions), but is certainly not possible anymore for the OCaml ecosystem, with 3259 opam packages, each containing several hundreds or thousands of functions.
Published: 2021

49. Resilient Scheduling of Moldable Parallel Jobs to Cope with Silent Errors

Author: Hongyang Sun, Padma Raghavan, Lucas Perotin, Anne Benoit, Valentin Le Fèvre, Yves Robert, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), Vanderbilt University [Nashville], Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], University of Kansas [Kansas City], École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Mathematical optimization, Schedule, Speedup, Computer science, 02 engineering and technology, Upper and lower bounds, Theoretical Computer Science, Scheduling (computing), Resilient scheduling, Set (abstract data type), symbols.namesake, Approximation ratios, Moldable jobs, Silent errors, 0202 electrical engineering, electronic engineering, information engineering, Parallel jobs, [INFO]Computer Science [cs], Failure scenario, Amdahl's law, Job shop scheduling, List schedule, 020202 computer hardware & architecture, Speedup model, Computational Theory and Mathematics, Hardware and Architecture, Transient errors, symbols, Batch schedule, Heuristics, Software
Abstract: International audience; We study the resilient scheduling of moldable parallel jobs on high-performance computing (HPC) platforms. Moldable jobs allow for choosing a processor allocation before execution, and their execution time obeys various speedup models. The objective is to minimize the overall completion time of the jobs, or the makespan, when jobs can fail due to silent errors and hence may need to be re-executed after each failure until successful completion. Our work generalizes the classical scheduling framework for failure-free jobs. To cope with silent errors, we introduce two resilient scheduling algorithms, LPA-List and Batch-List, both of which use the List strategy to schedule the jobs. Without knowing a priori how many times each job will fail, LPA-List relies on a local strategy to allocate processors to the jobs, while Batch-List schedules the jobs in batches and allows only a restricted number of failures per job in each batch. We prove new approximation ratios for the two algorithms under several prominent speedup models (e.g., roofline, communication, Amdahl, power, monotonic, and a mixed model). An extensive set of simulations is conducted to evaluate different variants of the two algorithms, and the results show that they consistently outperform some baseline heuristics. Overall, our best algorithm is within a factor of 1.6 of a lower bound on average over the entire set of experiments, and within a factor of 4.2 in the worst case.
Published: 2021

50. Coppersmith's block Wiedemann method for polynomial problems

Author: Villard, Gilles, Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: resultant of polynomials, Coppersmith's block Wiedemann algorithm, [SCCO.COMP]Cognitive science/Computer science, structured matrices
Abstract: International audience; Coppersmith has introduced a block version of Wiedemann's algorithm. The method allows to obtain algorithms with best known complexity bounds for various matrix and polynomial problems. We can mention for example: Determinant of a matrix over a ring; Sparse linear systems and inversion of sparse matrices; Annihilating polynomials of structured matrice; Resultant of bivariate polynomials; Fast modular composition of univariate polynomials; Manipulation of zero-dimensional ideal. We review the general approach and discuss new improvement for the resultant problem, using a combination of techniques for structured matrices and high-order lifting.
Published: 2021

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Publication Type

Journal

Database

Publisher

4,363 results on '"Laboratoire de l'Informatique du Parallélisme ( LIP )"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources