Search

Your search keyword '"Uçar, Bora"' showing total 297 results
Start Over Author "Uçar, Bora"

Refine your results

297 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. 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

7. 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

8. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Author

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

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.

Published
2024
Full Text
View/download PDF

9. 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. GPU accelerated maximum cardinality matching algorithms for bipartite graphs

Author

Deveci, Mehmet, Kaya, Kamer, Ucar, Bora, and Catalyurek, Umit V.

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

We design, implement, and evaluate GPU-based algorithms for the maximum cardinality matching problem in bipartite graphs. Such algorithms have a variety of applications in computer science, scientific computing, bioinformatics, and other areas. To the best of our knowledge, ours is the first study which focuses on GPU implementation of the maximum cardinality matching algorithms. We compare the proposed algorithms with serial and multicore implementations from the literature on a large set of real-life problems where in majority of the cases one of our GPU-accelerated algorithms is demonstrated to be faster than both the sequential and multicore implementations., Comment: 14 pages, 5 figures

Published
2013

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

19. 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

22. Engineering Fast Algorithms for the Bottleneck Matching Problem

Author

Ioannis Panagiotas and Grégoire Pichon and Somesh Singh and Bora Uçar, Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, Uçar, Bora, Ioannis Panagiotas and Grégoire Pichon and Somesh Singh and Bora Uçar, Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, and Uçar, Bora

Abstract

We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to find 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
Full Text
View/download PDF

23. Analysis of Partitioning Models and Metrics in Parallel Sparse Matrix-Vector Multiplication

Author

Kaya, Kamer, Uçar, Bora, Çatalyürek, Ümit V., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Wyrzykowski, Roman, editor, Dongarra, Jack, editor, Karczewski, Konrad, editor, and Waśniewski, Jerzy, editor

Published
2014
Full Text
View/download PDF

24. On Partitioning Problems with Complex Objectives

Author

Kaya, Kamer, Rouet, François-Henry, Uçar, Bora, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Alexander, Michael, editor, D’Ambra, Pasqua, editor, Belloum, Adam, editor, Bosilca, George, editor, Cannataro, Mario, editor, Danelutto, Marco, editor, Di Martino, Beniamino, editor, Gerndt, Michael, editor, Jeannot, Emmanuel, editor, Namyst, Raymond, editor, Roman, Jean, editor, Scott, Stephen L., editor, Traff, Jesper Larsson, editor, Vallée, Geoffroy, editor, and Weidendorfer, Josef, editor

Published
2012
Full Text
View/download PDF

26. Mumps

Author

Amestoy, Patrick, Buttari, Alfredo, Duff, Iain, Guermouche, Abdou, L’Excellent, Jean-Yves, Uçar, Bora, and Padua, David, editor

Published
2011
Full Text
View/download PDF

27. Multifrontal Method

Author

Amestoy, Patrick, Buttari, Alfredo, Duff, Iain, Guermouche, Abdou, L’Excellent, Jean-Yves, Uçar, Bora, and Padua, David, editor

Published
2011
Full Text
View/download PDF

28. On the Use of Cluster-Based Partial Message Logging to Improve Fault Tolerance for MPI HPC Applications

Author

Ropars, Thomas, Guermouche, Amina, Uçar, Bora, Meneses, Esteban, Kalé, Laxmikant V., Cappello, Franck, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Jeannot, Emmanuel, editor, Namyst, Raymond, editor, and Roman, Jean, editor

Published
2011
Full Text
View/download PDF

32. Heuristics for a Matrix Symmetrization Problem

Author

Uçar, Bora, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Wyrzykowski, Roman, editor, Dongarra, Jack, editor, Karczewski, Konrad, editor, and Wasniewski, Jerzy, editor

Published
2008
Full Text
View/download PDF

33. A Parallel Matrix Scaling Algorithm

Author

Amestoy, Patrick R., Duff, Iain S., Ruiz, Daniel, Uçar, Bora, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Palma, José M. Laginha M., editor, Amestoy, Patrick R., editor, Daydé, Michel, editor, Mattoso, Marta, editor, and Lopes, João Correia, editor

Published
2008
Full Text
View/download PDF

34. A Message Ordering Problem in Parallel Programs

Author

Uçar, Bora, Aykanat, Cevdet, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kranzlmüller, Dieter, editor, Kacsuk, Péter, editor, and Dongarra, Jack, editor

Published
2004
Full Text
View/download PDF

42. 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

43. 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

44. 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

45. 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
Full Text
View/download PDF

47. 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

48. 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

49. 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

50. 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

Catalog

Books, media, physical & digital resources
See catalog results