Search

Showing total 3 results
Start Over Topic [info.info-dc] computer science [cs]/distributed, parallel, and cluster computing [cs.dc]
3 results

1. Deciding Non-Compressible Blocks in Sparse Direct Solvers using Incomplete Factorization

Author

Korkmaz, Esragul, Faverge, Mathieu, Pichon, Grégoire, Ramet, Pierre, Korkmaz, Esragul, APPEL À PROJETS GÉNÉRIQUE 2018 - Solveur linéaire creux exploitant des matrices hierarchiques - - SaSHiMi2018 - ANR-18-CE46-0006 - AAPG2018 - VALID, High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), 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, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), 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), ANR-18-CE46-0006,SaSHiMi,Solveur linéaire creux exploitant des matrices hierarchiques(2018), 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, É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), This work is supported by the Agence Nationale de la Recherche, under grant ANR-18-CE46-0006 (SaSHiMi). Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d’Aquitaine (https://www.plafrim.fr/)., Inria Bordeaux - Sud Ouest, and Plafrim

Subjects
ILU factorization, Compression de rang faible, Factorisation ILU, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Solveur direct creux, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Sparse direct solvers, Low-rank compression
Abstract

Low-rank compression techniques are very promising for reducing memory footprintand execution time on a large spectrum of linear solvers. Sparse direct supernodal approaches areone these techniques. However, despite providing a very good scalability and reducing the memoryfootprint, they suffer from an important flops overhead in their unstructured low-rank updates. As a consequence, the execution time is not improved as expected. In this paper, we study asolution to improve low-rank compression techniques in sparse supernodal solvers. The proposedmethod tackles the overprice of the low-rank updates by identifying the blocks that have poorcompression rates. We show that block incomplete LU factorization, thanks to the block fill-inlevels, allows to identify most of these non-compressible blocks at low cost.This identification enables to postpone the low-rank compression step to trade small extra memory consumption fora better time to solution. The solution is validated within thePaStiXlibrary with a large set ofapplication matrices. It demonstrates sequential and multi-threaded speedup up to 8.5x, for smallmemory overhead of less than 1.49xwith respect to the original version., Les techniques de compression de rang faible sont très prometteuses au niveau de l’empreinte mémoire et du temps d’exécution sur un large spectre de solveurs linéaires. Les approches supernodales directes creuses font partie de ce spectre. Cependant, malgré leur très bonne scalabilité et leur empreinte mémoire plus faible, elles souffrent d’un surcoût calculatoire important dû aux mises à jour non-structurées de rang faible impliquées. En conséquence, le temps d’exécution n’est pas amélioré comme prévu. Dans cet article, nous étudions une solution pour améliorer les techniques de compression de rang faible dans les solveurs supernodaux creuses. La méthode proposée s’intéresse à ces mises à jour de rang faible plus coûteuses en identifiant les blocs avec de faibles taux de compression. Nous montrons que la factorisation LU incomplète par blocs, grâce aux niveaux de remplissage des blocs, permet d’identifier, à faible coût, la plupart de ces blocs non compressibles. Cette identification permet de reporter l’étape de compression de rang faible pour permettre un meilleur temps de résolution en échange d’une légère sur-consommation mémoire. La solution est validée dans la bibliothèque PaStiX avec un large ensemble de matrices issues d’applications. Il démontre une accélération séquentielle et multithread jusqu’à 8.5x, pour une augmentation de la consommation mémoire inférieure à 1.49x par rapport à la version originale.

Published
2021
Full Text
View/download PDF

2. READYS: A Reinforcement Learning Based Strategy for Heterogeneous Dynamic Scheduling

Author

Nathan Grinsztajn, Olivier Beaumont, Emmanuel Jeannot, Philippe Preux, Jeannot, Emmanuel, Scool (Scool), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), 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), Topology-Aware System-Scale Data Management for High-Performance Computing (TADAAM), Experiments presented in this paper were partially carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations. Nathan Grinsztajn is recipient of a PhD funding from AMX program, Ecole polytechnique., 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
Schedule, Theoretical computer science, Job shop scheduling, Computer science, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Reinforcement learning, Dynamic priority scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Directed acyclic graph, Scheduling (computing), Cholesky decomposition, Task (project management)
Abstract

International audience; In this paper, we propose READYS, a reinforcement learning algorithm for the dynamic scheduling of computations modeled as a Directed Acyclic Graph (DAGs). Our goal is to develop a scheduling algorithm in which allocation and scheduling decisions are made at runtime, based on the state of the system, as performed in runtime systems such as StarPU or ParSEC. Reinforcement Learning is a natural candidate to achieve this task, since its general principle is to build step by step a strategy that, given the state of the system (the state of the resources and a view of the ready tasks and their successors in our case), makes a decision to optimize a global criterion. Moreover, the use of Reinforcement Learning is natural in a context where the duration of tasks (and communications) is stochastic. We propose READYS that combines Graph Convolutional Networks (GCN) with an Actor-Critic Algorithm (A2C): it builds an adaptive representation of the scheduling problem on the fly and learns a scheduling strategy, aiming at minimizing the makespan. A crucial point is that READYS builds a general scheduling strategy which is neither limited to only one specific application or task graph nor one particular problem size, and that can be used to schedule any DAG. We focus on different types of task graphs originating from linear algebra factorization kernels (CHOLESKY, LU, QR) and we consider heterogeneous platforms made of a few CPUs and GPUs. We first propose to analyze the performance of READYS when learning is performed on a given (platform, kernel, problem size) combination. Using simulations, we show that the scheduling agent obtains performances very similar or even superior to algorithms from the literature, and that it is especially powerful when the scheduling environment contains a lot of uncertainty. We additionally demonstrate that our agent exhibits very promising generalization capabilities. To the best of our knowledge, this is the first paper which shows that reinforcement learning can really be used for dynamic DAG scheduling on heterogeneous resources.

Published
2021

3. On the Communication Complexity of Distributed Name-Independent Routing Schemes

Author

Nicolas Hanusse, Christian Glacet, David Ilcinkas, Cyril Gavoille, 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), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, and Experimental UpdateLess Evolutive Routing - EULER - - EC:FP7:ICT2010-10-01 - 2014-06-30 - 258307 - VALID

Subjects
TheoryofComputation_MISCELLANEOUS, distributed routing algorithm, compact routing, Routing table, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, bounded stretch, 01 natural sciences, Combinatorics, Asynchronous algorithms, 010201 computation theory & mathematics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Shortest path problem, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Communication complexity, name-independent, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.

Published
2013