CATS-Dec-5-2014
Title[edit]
Large-Scale Parallel Graph Algorithms
Speaker[edit]
Julian Shun
Abstract[edit]
In the first part of the talk, we 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 a 40-core machine and are sometimes significantly more efficient than previously reported results using graph frameworks on machines with many more cores.
In the second part of the talk, we discuss Ligra+, which integrates graph compression techniques into Ligra. On average, Ligra+ is able to represent graphs using about half of the space used by Ligra (which stores the graphs uncompressed). On a 40-core machine, the performance of Ligra+ is usually competitive with or faster than Ligra due to its smaller memory footprint. Our extensive experimental study shows that Ligra+ is able to support graphs using less memory, or much larger graphs using the same amount of memory, while performing as well as or faster than Ligra. As far as we know, Ligra+ is the first graph processing system to support a reasonably broad set of parallel graph algorithms on compressed graphs.
