Search

Your search keyword '"Uçar, Bora"' showing total 97 results
Start Over Author "Uçar, Bora" Publication Year Range Last 10 years

Refine your results

more »

more »

more »
97 results on '"Uçar, Bora"'

1. Open Problems in (Hyper)Graph Decomposition

Author

Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Karypis, George, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Schulz, Christian, Sharma, Roohani, Strash, Darren, Sullivan, Blair D., Uçar, Bora, and Yzelman, Albert-Jan

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.

Published
2023

2. Fully-dynamic Weighted Matching Approximation in Practice

Author

Angriman, Eugenio, Meyerhenke, Henning, Schulz, Christian, and Uçar, Bora

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Finding large or heavy matchings in graphs is a ubiquitous combinatorial optimization problem. In this paper, we engineer the first non-trivial implementations for approximating the dynamic weighted matching problem. Our first algorithm is based on random walks/paths combined with dynamic programming. The second algorithm has been introduced by Stubbs and Williams without an implementation. Roughly speaking, their algorithm uses dynamic unweighted matching algorithms as a subroutine (within a multilevel approach); this allows us to use previous work on dynamic unweighted matching algorithms as a black box in order to obtain a fully-dynamic weighted matching algorithm. We empirically study the algorithms on an extensive set of dynamic instances and compare them with optimal weighted matchings. Our experiments show that the random walk algorithm typically fares much better than Stubbs/Williams (regarding the time/quality tradeoff), and its results are often not far from the optimum.

Published
2021

3. Streaming Hypergraph Partitioning Algorithms on Limited Memory Environments

Author

Taşyaran, Fatih, Demireller, Berkay, Kaya, Kamer, and Uçar, Bora

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Distributed, Parallel, and Cluster Computing, 68W27, 68P05, E.1
Abstract

Many well-known, real-world problems involve dynamic data which describe the relationship among the entities. Hypergraphs are powerful combinatorial structures that are frequently used to model such data. For many of today's data-centric applications, this data is streaming; new items arrive continuously, and the data grows with time. With paradigms such as Internet of Things and Edge Computing, such applications become more natural and more practical. In this work, we assume a streaming model where the data is modeled as a hypergraph, which is generated at the edge. This data then partitioned and sent to remote nodes via an algorithm running on a memory-restricted device such as a single board computer. Such a partitioning is usually performed by taking a connectivity metric into account to minimize the communication cost of later analyses that will be performed in a distributed fashion. Although there are many offline tools that can partition static hypergraphs excellently, algorithms for the streaming settings are rare. We analyze a well-known algorithm from the literature and significantly improve its running time by altering its inner data structure. For instance, on a medium-scale hypergraph, the new algorithm reduces the runtime from 17800 seconds to 10 seconds. We then propose sketch- and hash-based algorithms, as well as ones that can leverage extra memory to store a small portion of the data to enable the refinement of partitioning when possible. We experimentally analyze the performance of these algorithms and report their run times, connectivity metric scores, and memory uses on a high-end server and four different single-board computer architectures., Comment: 8 pages, 6 algorithms, 2 figures, 4 tables, submitted to HPCS'20

Published
2021

4. Programming Strategies for Irregular Algorithms on the Emu Chick

Author

Hein, Eric, Eswar, Srinivas, Yaşar, Abdurrahman, Li, Jiajia, Young, Jeffrey S., Conte, Thomas M., Çatalyürek, Ümit V., Vuduc, Rich, Riedy, Jason, and Uçar, Bora

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

The Emu Chick prototype implements migratory memory-side processing in a novel hardware system. Rather than transferring large amounts of data across the system interconnect, the Emu Chick moves lightweight thread contexts to near-memory cores before the beginning of each remote memory read. Previous work has characterized the performance of the Chick prototype in terms of memory bandwidth and programming differences from more typical, non-migratory platforms, but there has not yet been an analysis of algorithms on this system. This work evaluates irregular algorithms that could benefit from the lightweight, memory-side processing of the Chick and demonstrates techniques and optimization strategies for achieving performance in sparse matrix-vector multiply operation (SpMV), breadth-first search (BFS), and graph alignment across up to eight distributed nodes encompassing 64 nodelets in the Chick system. We also define and justify relative metrics to compare prototype FPGA-based hardware with established ASIC architectures. The Chick currently supports up to 68x scaling for graph alignment, 80 MTEPS for BFS on balanced graphs, and 50\% of measured STREAM bandwidth for SpMV.

Published
2018

6. High Performance Tensor–Vector Multiplication on Shared-Memory Systems

Author

Pawłowski, Filip, Uçar, Bora, Yzelman, Albert-Jan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Wyrzykowski, Roman, editor, Deelman, Ewa, editor, Dongarra, Jack, editor, and Karczewski, Konrad, editor

Published
2020
Full Text
View/download PDF

7. A Backward/Forward Recovery Approach for the Preconditioned Conjugate Gradient Method

Author

Fasi, Massimiliano, Langou, Julien, Robert, Yves, and Ucar, Bora

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Several recent papers have introduced a periodic verification mechanism to detect silent errors in iterative solvers. Chen [PPoPP'13, pp. 167--176] has shown how to combine such a verification mechanism (a stability test checking the orthogonality of two vectors and recomputing the residual) with checkpointing: the idea is to verify every $d$ iterations, and to checkpoint every $c \times d$ iterations. When a silent error is detected by the verification mechanism, one can rollback to and re-execute from the last checkpoint. In this paper, we also propose to combine checkpointing and verification, but we use algorithm-based fault tolerance (ABFT) rather than stability tests. ABFT can be used for error detection, but also for error detection and correction, allowing a forward recovery (and no rollback nor re-execution) when a single error is detected. We introduce an abstract performance model to compute the performance of all schemes, and we instantiate it using the preconditioned conjugate gradient algorithm. Finally, we validate our new approach through a set of simulations.

Published
2015

8. Effective Heuristics for Matchings in Hypergraphs

Author

Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, Uçar, Bora, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kotsireas, Ilias, editor, Pardalos, Panos, editor, Parsopoulos, Konstantinos E., editor, Souravlias, Dimitris, editor, and Tsokas, Arsenis, editor

Published
2019
Full Text
View/download PDF

10. Engineering fast algorithms for the bottleneck matching problem

Author

Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, Uçar, Bora, Neo4j, Université Claude Bernard Lyon 1 (UCBL), Université 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), and Centre National de la Recherche Scientifique (CNRS)

Subjects
bipartite graphs, matching, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], assignment problem
Abstract

International audience; We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to determine a maximum cardinality matching in which the minimum weight of an edge is the maximum. To the best of our knowledge, there are two widely used solvers for this problem based on two different approaches. There exists a third known approach in the literature, which seems inferior to those two which is presumably why there is no implementation of it. We take this third approach, make theoretical observations to improve its behavior, and implement the improved method. Experiments with the existing two solvers show that their run time can be too high to be useful in many interesting cases. Furthermore, their performance is not predictable, and slight perturbations of the input graph lead to considerable changes in the run time. On the other hand, the proposed solver's performance is much more stable; it is almost always faster than or comparable to the two existing solvers, and its run time always remains low.

Published
2023

15. Coping with Silent Errors in HPC Applications

Author

Aupy, Guillaume, Benoit, Anne, Cavelan, Aurlien, Fasi, Massimiliano, Robert, Yves, Sun, Hongyang, Uçar, Bora, Zelinka, Ivan, Series editor, Adamatzky, Andrew, Series editor, and Chen, Guanrong, Series editor

Published
2017
Full Text
View/download PDF

22. LIPIcs, Volume 233, SEA 2022, Complete Volume

Author

Schulz, Christian and Uçar, Bora

Subjects
Data processing Computer science, Theory of computation → Design and analysis of algorithms, ddc:004, LIPIcs, Volume 233, SEA 2022, Complete Volume
Abstract

LIPIcs, Volume 233, SEA 2022, Complete Volume, LIPIcs, Vol. 233, 20th International Symposium on Experimental Algorithms (SEA 2022), pages 1-434

Published
2022

23. A Branch-And-Bound Algorithm for Cluster Editing

Author

Bläsius, Thomas, Fischbeck, Philipp, Gottesbüren, Lars, Hamann, Michael, Heuer, Tobias, Spinner, Jonas, Weyand, Christopher, Wilhelm, Marcus, Schulz, Christian, and Uçar, Bora

Subjects
editing, cluster editing, Mathematics of computing → Graph algorithms, DATA processing & computer science, ddc:004, cluster
Abstract

The cluster editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge., LIPIcs, Vol. 233, 20th International Symposium on Experimental Algorithms (SEA 2022), pages 13:1-13:19

Published
2022
Full Text
View/download PDF

24. Front Matter, Table of Contents, Preface, Conference Organization

Author

Schulz, Christian and Uçar, Bora

Subjects
Conference Organization, Table of Contents, Theory of computation → Design and analysis of algorithms, Preface, Front Matter
Abstract

Front Matter, Table of Contents, Preface, Conference Organization, LIPIcs, Vol. 233, 20th International Symposium on Experimental Algorithms (SEA 2022), pages 0:i-0:xii

Published
2022
Full Text
View/download PDF

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

Author

Langguth, Johannes, Panagiotas, Ioannis, Uçar, Bora, University of Bergen (UiB), ComplexNetworks, LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

26. Algorithms and data structures for hyperedge queries

Author

Bertrand, Jules, Dufossé, Fanny, Uçar, Bora, École normale supérieure - Lyon (ENS Lyon), Data Aware Large Scale Computing (DATAMOVE ), 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)-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), 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), 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), Université Grenoble Alpes (UGA), 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
hypergraphs, Hachage, perfect hashing, Hashing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], hypergraphes, hachage parfait
Abstract

Revised version May 2021; We consider the problem of querying the existence of hyperedges in hypergraphs. More formally, we are given a hypergraph, and we need to answer queries of the form "does the following set of vertices form a hyperedge in the given hypergraph?''. Our aim is to set up data structures based on hashing to answer these queries as fast as possible. We propose an adaptation of a well-known perfect hashing approach for the problem at hand.We analyze the space and run time complexity of the proposed approach, and experimentally compare it with the state of the art hashing-based solutions. Experiments demonstrate that the proposed approach has the shortest query response time than the other considered alternatives, while having a larger construction time than some of the alternatives.; Nous considérons le problème de requêtes d'existences d'hyperarêtes dans des hypergraphes. Plus formellement, pour un hypergraphe donné, nous devons répondre à des requêtes de la forme "est-ce que l'ensemble de sommets suivant forme une hyperarête de l'hypergraphe?". Notre objectif est de mettre en place une structure de donnée basée sur du hachage pour répondre à ces requêtes le plus rapidement possible. Nous proposons une adaptation d'une approche bien connue de hachage parfait pour notre problème. Nous analysons la complexité en temps et en espace de cette approche, et nous la comparons expérimentalement à des solutions de l'état de l'art basées sur le hachage. Les expériences démontrent que cette approche a un temps de réponse aux requêtes plus court que les alternatives considérées, pour un temps de construction plus long que certaines des alternatives.

Published
2021

27. Combinatorial Tiling for Sparse Neural Networks

Author

Pawłowski, Filip, Bisseling, Rob, Uçar, Bora, Yzelman, Albert-Jan, 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), Department of Mathematics [Utrecht], Utrecht University [Utrecht], 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), Huawei Zurich Research Center, 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), Department of Mathematics, Utrecht University, Inria - Research Centre Grenoble – Rhône-Alpes, É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], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; Sparse deep neural networks (DNNs) emerged as the result of search for networks with less storage and lower computational complexity. The sparse DNN inference is the task of using such trained DNN networks to classify a batch of input data. We propose an efficient, hybrid model- and data-parallel DNN inference using hypergraph models and partitioners. We exploit tiling and weak synchronization to increase cache reuse, hide load imbalance, and hide synchronization costs. Finally, a blocking approach allows application of this new hybrid inference procedure for deep neural networks. We initially experiment using the hybrid tiled inference approach only, using the first five layers of networks from the IEEE HPEC 2019 Graph Challenge, and attain up to 2x speedup versus a data-parallel baseline

Published
2020

28. Algorithmes rapides quasi-optimaux pour trouver des couplages dans de graphes bipartis

Author

Panagiotas, Ioannis, Uçar, Bora, 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), 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
matching, randomized algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS, Bipartite graphs
Abstract

International audience; We consider the maximum cardinality matching problem in bipartite graphs.There are a number of exact, deterministic algorithms for this purpose, whose complexities are high in practice.There are randomized approaches for special classes of bipartite graphs.Random 2-out bipartite graphs, where each vertex chooses two neighbors at randomfrom the other side, form one class for which there is an $O(m+n\log n)$-time Monte Carlo algorithm. Regular bipartite graphs, where all vertices have the same degree,form another class for which there is an expected $O(m + n\log n)$-time Las Vegas algorithm.We investigate these two algorithms and turn them into practical heuristics with randomization.Experimental results show that the heuristics are fast and obtain near optimal matchings.They are also more robust than the state of the art heuristics used in the cardinality matching algorithms, and are generally more useful as initialization routines.

Published
2020

29. Algorithmes rapides quasi-optimaux pour trouver des couplages dans de graphes bipartis: Version étendue

Author

Panagiotas, Ioannis, Uçar, Bora, 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), 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), and Inria - Research Centre Grenoble – Rhône-Alpes

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Published
2020

30. Karp-Sipser based kernels for bipartite graph matching

Author

Kaya, Kamer, Langguth, Johannes, Panagiotas, Ioannis, Uçar, Bora, Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Simula Research Laboratory, 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), 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), É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
QA075 Electronic computers. Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract

We consider Karp–Sipser, a well-known matching heuristic in the context of data reduction for the maximum cardinality matching problem. We describe an efficient implementation as well as modifications to reduce its time complexity in worst-case instances, both in theory and in practical cases. We compare experimentally against its widely used simpler variant and show cases for which the full algorithm yields better performance.

Published
2020

31. Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching

Author

Panagiotas, Ioannis and Uçar, Bora

Subjects
bipartite graphs, matching, Theory of computation → Design and analysis of algorithms, randomized algorithm, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We consider the maximum cardinality matching problem in bipartite graphs. There are a number of exact, deterministic algorithms for this purpose, whose complexities are high in practice. There are randomized approaches for special classes of bipartite graphs. Random 2-out bipartite graphs, where each vertex chooses two neighbors at random from the other side, form one class for which there is an O(m+nlog n)-time Monte Carlo algorithm. Regular bipartite graphs, where all vertices have the same degree, form another class for which there is an expected O(m + nlog n)-time Las Vegas algorithm. We investigate these two algorithms and turn them into practical heuristics with randomization. Experimental results show that the heuristics are fast and obtain near optimal matchings. They are also more robust than the state of the art heuristics used in the cardinality matching algorithms, and are generally more useful as initialization routines.

Published
2020
Full Text
View/download PDF

32. Partitionnement, couplage et permutation: Calcul scientifique combinatoire sur des matrices et des tenseurs

Author

Uçar, Bora, 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), 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), Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), ENS de Lyon, Nadia Brauner, É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), 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-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
graphs, Matrices creuses, sparse tensors, hypergraphs, tenseurs creux, graphes, Sparse matrices, [INFO]Computer Science [cs], hypergraphse
Abstract

This HDR investigates three classes of problems at the interplay of discrete algorithms, combinatorial optimization, and numerical methods. The three problem classes are that of partitioning, matching, and ordering.Partitioning problems arise in task decomposition for parallel computing, where load balance and low communication cost are two objectives. We discuss acyclic partitioning of directed acyclic graphs and hypergraphs. While our contributions for the former problem concern combinatorial tools for the desired partitioning objectives and constraints, those for the second problem concern the use of hypergraph partitioning tools for efficient tensor decomposition in distributed memory systems.Matching problems arise in settings where agents compete for exclusive access to resources. We present approximation algorithms for matchings in graphs and effective heuristics for finding matchings in hypergraphs. We also investigate the problem of finding Birkhoff--von Neumann decompositions with a small number of permutation matrices and present complexity results and theoretical insights into this problem. Ordering problems arise when one wants to permute sparse matrices and tensors into desirable forms. We propose heuristics to permute sparse matrices into special forms to reduce the height of the resulting elimination tree. We also propose heuristics to cluster nonzeros of a given sparse tensor around the diagonal in order to improve the performance of certain tensor operations.The general research area is called combinatorial scientific computing (CSC). In CSC, the contributions have practical and theoretical flavor. For all problems discussed in this document, we have the design, analysis, and implementation of algorithms along with many experiments. The theoretical results are included in this document, some with proofs; the reader is invited to the original papers for the omitted proofs. A similar approach is taken for presenting the experiments. While most results for observing theoretical findings in practice are included, the reader is referred to the original papers for some other results (e.g., run time analysis).

Published
2019

33. High performance tensor-vector multiplication on shared-memory systems

Author

Pawlowski, Filip, Uçar, Bora, Yzelman, Albert-Jan, 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), Huawei Technologies France [Boulogne-Billancour], 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 - 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), Huawei Technologies France [Boulogne-Billancourt], 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], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2019

34. Programming Strategies for Irregular Algorithms on the Emu Chick

Author

Hein, Eric R., primary, Eswar, Srinivas, additional, Yaşar, Abdurrahman, additional, Li, Jiajia, additional, Young, Jeffrey S., additional, Conte, Thomas M., additional, Çatalyürek, Ümit V., additional, Vuduc, Richard, additional, Riedy, Jason, additional, and Uçar, Bora, additional

Published
2020
Full Text
View/download PDF

35. Multiplication tenseur–vecteur haute performance sur des machines à memoire partagée

Author

Pawłowski, Filip, Uçar, Bora, Yzelman, Albert-Jan, 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), Huawei Technologies France [Boulogne-Billancourt], Inria - Research Centre Grenoble – Rhône-Alpes, É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 Huawei Technologies France [Boulogne-Billancour]

Subjects
Shared-memory parallel machines, Multiplication tenseur-vecteur, Tenseur, Tensors, Tensor–vector multiplication, Machines parallèles à mémoire partagée, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

Tensor–vector multiplication is one of the core components in tensor computations. We have recently investigated high performance, single core implementation of this bandwidth-bound operation. In this work, we investigate efficient, shared memory algorithms to carry out this operation. Upon carefully analyzing the design space, we implement a number of alternatives using OpenMP and compare them experimentally. Experimental results on up to 8 socket systems show near peak performance for the proposed algorithms.; La multiplication tenseur–vecteur est l’un des composants essentiels des calculs de tenseurs. Nous avons récemment étudié cette opération, qui consomme la bande passante, sur une plateforme séquentielle. Dans ce travail, nous étudions des algorithmes efficaces pour effectuer cette opérationsur des machines à mémoire partagée. Après avoir soigneusement analysé les différentes alternatives, nous mettons en œuvre plusieurs d’entre elles en utilisant OpenMP, et nous les comparons expérimentalement. Les résultats expérimentaux sur un à huit systèmes de sockets montrent une performance quasi maximale pour les algorithmes proposés

Published
2019

36. Effective heuristics for matchings in hypergraphs

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 ), 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]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), 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), and Inria Grenoble Rhône-Alpes

Subjects
Tensor scaling, Karp- Sipser heuristic, Heuristique Karp–Sipser, Couplage, Matching in hypergraphs, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Hypergraphes, [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], d-dimensional matching
Abstract

The problem of finding a maximum cardinality matching in a d-partite d-uniform hypergraph is an important problem in combinatorial optimization and has beentheoretically analyzed by several researchers. In this work, we first devise heuristics for this problem by generalizing the existing cheap graph matching heuristics. Then, we propose a novel heuristic based on tensor scaling to extend the matching via judicious hyperedge selections. Experiments on random, synthetic and real-life hypergraphs show that this new heuristic is highly practical and superior to the others on finding a matching with largecardinality.; Le problème consistant à trouver un couplage maximal dans un hypergraphe uniforme ayant d parts est un problème important en optimisation combinatoire. Dans ce travail, nous concevons d’abord des heuristiques pour ce problème en généralisant les heuristiques de couplage dans des graphes. Ensuite, nous proposons une nouvelle heuristique basée sur des méthodes de mise à l’échelle de tenseur pour étendre le couplage via des sélections judicieuses d’hyperarêtes. Des expériences sur des hypergraphes aléatoires, synthétiques et réels montrent que cette nouvelle heuristique est simple à mettre en pratique et supérieure aux autres pour trouver des couplages de grande cardinalité.

Published
2018

37. A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning

Author

Özkaya, Yusuf, Benoit, Anne, Uçar, Bora, Herrmann, Julien, Çatalyürek, Ümit, Georgia Institute of Technology [Atlanta], 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), and Inria Grenoble Rhône-Alpes

Subjects
Directed acyclic graphs, List scheduling, Concurrency, Partitionnement, Localité des données, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Data locality, Concurrence, Graphes dirigés acycliques, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Clustering, Partitioning, Ordonnancement de liste
Abstract

When scheduling a directed acyclic graph (DAG) of tasks on computationalplatforms, a good trade-off between load balance and data locality isnecessary. List-based scheduling techniques are commonly used greedy approachesfor this problem. The downside of list-scheduling heuristicsis that they are incapable of making short-term sacrifices for the globalefficiency of the schedule. In this work, we describe newlist-based scheduling heuristics based on clustering for homogeneousplatforms, under the realistic duplex single-port communication model. Our approach uses an acyclic partitioner for DAGs for clustering.The clustering enhances the data locality of the scheduler with a global viewof the graph. Furthermore, since the partition is acyclic, we can scheduleeach part completely once its input tasks are ready to be executed. Wepresent an extensive experimental evaluation showing the trade-offs betweenthe granularity of clustering and the parallelism, and how this affects the scheduling.Furthermore, we compare our heuristics to the best state-of-the-art list-scheduling and clustering heuristics, and obtain more than three times better makespan in caseswith many communications.; Lors de l'ordonnancement d'un graphe dirigé acyclique (DAG) de tâches sur une plate-forme, un bon compromis entre équilibrage de charge et localité des données est nécessaire.Les techniques d'ordonnancement de liste sont des approches gloutonnescommunément utilisées pour ce problème. Les inconvénients de telles heuristiques de liste sont qu'ellessont incapables de faire des sacrifices à court terme pour que l'ordonnancementglobal soit plus efficace. Dans ces travaux, nous décrivons de nouvelles heuristiques d'ordonnancement de listepour des plates-formes homogènes, avec un modèle de communications duplexe un-port réaliste. Notre approche se base sur un partitionnement acycliquedu DAG, car les parties ainsi formées permettent d'avoir une bonne localité des donnéestout en conservant une vue générale du graphe. De plus, étant donné que la partition est acyclique,nous pouvons ordonnancer chaque partie entièrement une fois que ses tâches d'entrée sont prêtes à être exécutées. Nous présentons une évaluation expérimentale des algorithmes pour montrerles compromis entre la granularité des partitions et le parallélisme, et commentcela affecte l'ordonnancement. De plus, nous comparons nos heuristiques aux meilleurscompétiteurs de la littérature, et nous obtenons un temps d’exécution total plus de trois fois meilleur dans des cas avec de nombreuses communications.

Published
2018

38. 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 ), 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]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), 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), and Inria Grenoble Rhône-Alpes

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
Abstract

We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.

Published
2018

39. Normalisation de matrice et dénombrement des couplages parfaits dans les graphes

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 ), 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]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), 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), and Inria Grenoble Rhône-Alpes

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
Abstract

We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.

Published
2018

40. Acyclic partitioning of large directed acyclic graphs

Author

Herrmann, Julien, Yusuf Özkaya, M, Uçar, Bora, Kaya, Kamer, Çatalyürek, Ümit, School of Computational Science and Engineering, Georgia Institute of Technology [Atlanta], 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), Centre National de la Recherche Scientifique (CNRS), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], and Inria - Research Centre Grenoble – Rhône-Alpes

Subjects
acyclic partitioning, multilevel partitioning, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], directed graph, partitionnement acyclic, partitionnement multiniveau, graphes orientés
Abstract

We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met.Furthermore, the partition is required to be {\em acyclic}, i.e., the inter-part edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinementphases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multi-way partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening andrefinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i)~graphs coming from an application and (ii)~some others corresponding to matrices from a public collection. We report improvements, on average, around 59\% compared to the current state of the art.; Nous étudions le problème du partitionnement des sommets d’un graphe acyclique dirigé en un nombre donné de parties. La fonction objectiveest de minimiser le poids total des arêtes ayant des extrémités dans différentes parties, qui sont également nommées arêtes coupées. La contrainted’équilibrage de charge standard d’avoir une partition équitable des sommets entre les parties doit être respectée. En outre, la partition doit être acyclique, c’est-à-dire, les arêtes coupées doivent préserver une structure de dépendance acyclique entre les parties. Dans ce travail, nous adoptons une approche multiniveaux avec des étapes de contraction, partitionnement initial et raffinement pour le partitionnement acyclique des graphes acycliques dirigés. Nous nous concentrons sur la bissection, car ce schéma peut être utilisé d’une manière récursive pour le partitionnement multi-voies. Pour assurer l’acyclicité du partitionnement à tout moment, nous proposons des méthodes de contraction etde raffinement. La qualité des partitions acycliques calculées est évaluée en calculant la somme des poids des arêtes coupées. Nous proposons également des moyens efficaces afin d’utiliser des méthodes standard de partitionnement de graphes non orientés dans notre schéma multi-niveaux. Nous effectuons un grand nombre d’expériences sur un ensemble de données constitué de (i) graphes provenant d’une application, et (ii) d’autres graphes correspondant à des matrices d’une collection publique. Nous rapportons des améliorations par rapport aux méthodes existantes d’environ 59 % en moyenne.

Published
2018

45. Computing Dense Tensor Decompositions with Optimal Dimension Trees

Author

Kaya, Oguz, Robert, Yves, Uçar, Bora, 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), The University of Tennessee [Knoxville], Inria, É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
tensor decomposition, arbres de dimension, décomposition de tenseurs, dimension trees, Tucker decomposition, [INFO]Computer Science [cs], décomposition Tucker, décomposition CP, CP decomposition
Abstract

Dense tensor decompositions have been widely used in many signal processing problems including analyzing speech signals, identifying the localization of signal sources, and many other communication applications.Computing these decompositions poses major computational challenges for big datasets emerging in these domains.CANDECOMP/PARAFAC~(CP) and Tucker formulations are the prominent tensor decomposition schemes heavily used in these fields, and the algorithms for computing them involve applying two core operations, namely tensor-times-matrix~(TTM) and -vector~(TTV) multiplication, which are executed repetitively within an iterative framework.In the recent past, efficient computational schemes using a data structure called dimension tree are employed to significantly reduce the cost of these two operations through storing and reusing partial results that are commonly used across different iterations of these algorithms.This framework has been introduced for sparse CP and Tucker decompositions in the literature, and a recent work investigates using an optimal binary dimension tree structure in computing dense Tucker decompositions.In this paper, we investigate finding an optimal dimension tree for both CP and Tucker decompositions.We show that finding an optimal dimension tree is NP-hard for both decompositions, provide faster exact algorithms for finding an optimal dimension tree in $O(3^N)$ time using $O(2^N)$ space for the Tucker case, and extend the algorithm to the case of CP decomposition with the same time and space complexities.; Les décompositions de tenseurs sont largement utilisées dans plusieurs problèmes de traitement du signal, notamment l’analyse des signaux vocaux, l’identification de la localisation des sources des signaux et d’autres applications de communication. Le calcul de ces décompositions pose un énorme défi calculatoire, particulièrement pour les grands jeux de données apparaissant dans ces domaines. Les formulations du CANDECOMP/PARAFAC (CP) et Tucker sont les deux décompositions les plus intensivement utilisées. Les algorithmes pour calculer ces décompositions incluent deux operations principales, tenseur-fois-matrice (TTM) et -vector (TTV), qui se répètent dans une méthode iterative. Dans ce rapport, on introduit un nouveau schema de calcul pour éffectuer ces deux operations efficacement en calculant les decompositions CP et Tucker. Pour ce faire, on adopte une structure d’arbre qui permet de stocker et ré-utiliser les résultats partiels pour réduire le coût de calcul de manière significative. Ensuite, on fournit un algorithme glouton, s’exécutant en temps linéaire, pour trouver l’ordre optimal minimisant le coût de calcule d’une serie de TTMs. Finalement, on examine le problème de trouver un arbre optimal pour calculer les décompositions CP et Tucker avec le nouveau schema de calcul proposé, et on prouve que ce problème est NP-difficile dans les deux cas.

Published
2017

46. On matrix symmetrization and sparse direct solvers

Author

Portase, Raluca, Uçar, Bora, 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), Technical University of Cluj-Napoca, 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), Inria - Research Centre Grenoble – Rhône-Alpes, ANR-13-MONU-0007,SOLHAR,Solveurs pour architectures hétérogènes utilisant des supports d'exécution(2013), É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
LU decomposition, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], couplage biparti, décomposition LU, bipartite matching, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Sparse matrix, Matrice creuse, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract

We investigate algorithms for finding column permutations of sparse matrices in order to have large diagonal entriesand to have many entries symmetrically positioned around the diagonal. The aim is to improve the memory and running time requirements of a certain class of sparse direct solvers.We propose efficient algorithms for this purpose by combining two existing approaches and demonstratethe effect of our findings in practice using a direct solver. In particular, we show improvements in a number of components of the running time of a sparse direct solver with respect to the state of the art on a diverse set of matrices.; Nous étudions des algorithmes pour trouver des permutations de colonnes de matrices creuses afin d’avoir de grandes entrées sur la diagonaleet d’avoir de nombreuses entrées symétriquement positionnées autour de la diagonale. Notre but est d’améliorer la mémoire et le temps d’exécution d’unecertaine classe de solveurs directs creux. Nous proposons des algorithmes efficaces à cet effet en combinant deux approches existantes et exposons l’effet de nos résultats dans la pratique en utilisant un solveur direct. En particulier, nous montrons des améliorations dans de plusieurs components du temps d’exécution d’un solveur direct creux par rapport à l’état de l’art sur un ensemble divers de matrices

Published
2016

47. Scheduling Series-Parallel Task Graphs to Minimize Peak Memory

Author

Kayaaslan, Enver, Lambert, Thomas, Marchal, Loris, Uçar, Bora, 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), 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), Laboratoire de l'Informatique du Parallélisme (LIP), Reformulations based algorithms for Combinatorial Optimization (Realopt), 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)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-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, Université de Grenoble, ANR-13-MONU-0007,SOLHAR,Solveurs pour architectures hétérogènes utilisant des supports d'exécution(2013), É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), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

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], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We consider a variant of the well-known, NP-complete problem of minimum cut linear arrangement for directed acyclic graphs. In this variant, we are given a directed acyclic graph and asked to find a topological ordering such that the maximum number of cut edges at any point in this ordering is minimum.In our main variant the vertices and edges have weights, and the aim is to minimize the maximum weight of cut edges in addition to the weight of the last vertex before the cut.There is a known, polynomial time algorithm [Liu, SIAM J. Algebra. Discr., 1987] for the cases where the input graph is a rooted tree. We focus on the variant where the input graph is a directed series-parallel graph, and propose a polynomial time algorithm.Directed acyclic graphs are used to model scientific applications where the vertices correspond to the tasks of a given application and the edges represent the dependencies between the tasks. In such models, the problem we address reads as minimizing the peak memory requirement in an execution of the application.Our work, combined with Liu's work on rooted trees addresses this practical problem in two important classes of applications.

Published
2016

Catalog

Books, media, physical & digital resources
See catalog results