Three Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
A linear-algebra-first framework implements graph primitives (sparse matrix‑matrix, matrix‑vector, elementwise ops) using Combinatorial BLAS, exposing them to users via the knowledge Discovery Toolbox (KDT) and a Python front end. Semi‑rings let algorithms like Luby’s MIS run in O(log n) rounds; JIT translation of user filters and semi‑rings (via siegitz-style DSL) removes Python upcalls and recovers C/MPI speed (avoids reported ~80× slowdown), scales to 576 cores, and shows better strong scaling on 4k–8k vertex APSP by trading memory to cut communication.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:54Graph abstractions in Computer Science
- 1:30Large graphs are everywhere
- 2:09Types of graph computations
- 4:13Linear-algebraic primitives for graphs
- 5:55Some Combinatorial BLAS functions
- 6:34Parallel, randomized maximal independent set algorithm
- 8:29Luby's algorithm in KDT
- 11:34Graph algorithm comparison (LA: linear algebra)
- 12:55The case for sparse matrices
- 14:032D Parallel BFS algorithm (variants top Graph500)
- 16:16Parallel Graph Analysis Software
- 19:30Attributed semantic graphs and filters
- 21:09Edge filter illustration
- 21:39Problems with Customizing in KDT
- 23:17SEJITS for filter/semiring acceleration
- 23:35SEJITS+KDT multicore performance
- 24:16SEJITS+KDT cluster performance
- 24:55Parallel Graph Computations
- 25:22Communication crucial for graphs
- 27:46Communication-avoiding APSP on distributed memory
- 29:17Questions?
related talks
01h 05mGraph Algorithms in the MPC Model
31mSome Novel Computational Models to Think About
10mGraph Based Pipeline Parallelism
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
29mParallel Cluster-BFS and Applications to Shortest Paths
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
15mA General Framework for Communication-Efficient Distributed...
47mMultiscale Analysis on and of Graphs