483 citations · 1.5k across the 115 of their papers we have counts for
9 papers · 1 filter
Maximum Flows in Parametric Graph Templates
Tal Ben-Nun, Lukas Gianinazzi, Torsten Hoefler +1
Execution graphs of parallel loop programs exhibit a nested, repeating structure. We show how such graphs that are the result of nested repetition can be represented by succinct pa…
The spatial computer: A model for energy-efficient parallel computation
Lukas Gianinazzi, Tal Ben-Nun, Maciej Besta +4
We present a new parallel model of computation suitable for spatial architectures, for which the energy used for communication heavily depends on the distance of the communicating…
Parallel Algorithms for Finding Large Cliques in Sparse Graphs
Lukas Gianinazzi, Maciej Besta, Yannick Schaffner +1
We present a parallel k-clique listing algorithm with improved work bounds (for the same depth) in sparse graphs with low degeneracy or arboricity. We achieve this by introducing a…
Parametric Graph Templates: Properties and Algorithms
Tal Ben-Nun, Lukas Gianinazzi, Torsten Hoefler +1
Hierarchical structure and repetition are prevalent in graphs originating from nature or engineering. These patterns can be represented by a class of parametric-structure graphs, w…
Log(Graph): A Near-Optimal High-Performance Graph Representation
Maciej Besta, Dimitri Stanojevic, Tijana Zivic +3
Today's graphs used in domains such as machine learning or social network analysis may contain hundreds of billions of edges. Yet, they are not necessarily stored efficiently, and…
High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality
Maciej Besta, Armon Carigiet, Zur Vonarburg-Shmaria +3
We develop the first parallel graph coloring heuristics with strong theoretical guarantees on work and depth and coloring quality. The key idea is to design a relaxation of the ver…