CATS-Dec-5-2014
Title
Large-Scale Parallel Graph Algorithms
Speaker
Julian Shun
Abstract
In the first part of the talk, we will discuss our recent work on developing a practical linear-work parallel algorithm for graph connectivity. Sequentially, connectivity can be done in linear work easily using breadth-first search or depth-first search. There have been many parallel algorithms for connectivity, however the simpler parallel algorithms require super-linear work, and the linear-work polylogarithmic-depth parallel algorithms are very complicated and not amenable to implementation. We address this gap by describing a simple and practical expected linear-work, polylogarithmic-depth parallel algorithm for graph connectivity. Our algorithm is based on a recent parallel algorithm for generating low-diameter graph decompositions by Miller et al., which uses parallel breadth-first searches. We experimentally compare our implementation of the algorithm against the fastest existing parallel connectivity implementations (which are not theoretically linear-work and polylogarithmic-depth) and show that our implementation is competitive for various inputs, and achieves good speedup relative to sequential algorithms. Our algorithm is the first parallel connectivity algorithm that is both theoretically and practically efficient.
In the second part of the talk, we will discuss Ligra, a shared-memory graph processing system that we recently developed. The framework has two very simple routines, one for mapping over edges and one for mapping over vertices. The routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), the routines automatically adapt to the density of vertex sets. We implement several algorithms in this framework, including BFS, betweenness centrality, graph radii estimation, graph connectivity, PageRank and single-source shortest paths. Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly-optimized code. Furthermore, they get good speedups on multicore machines and are sometimes significantly more efficient than previously reported results using graph frameworks on machines with many more cores.
Bio
Julian Shun is currently a Ph.D. student in Computer Science at Carnegie Mellon University, and is advised by Guy Blelloch. He is interested in developing large-scale parallel algorithms for graph and text processing. He is also interested in designing techniques and tools for writing efficient parallel programs. Julian obtained his undergraduate degree in Computer Science from UC Berkeley.