The Taub Faculty of Computer Science Events and Talks

In the first part of the talk I will give a high-level introduction to Galois, a framework for designing and implementing parallel graph algorithms and related concepts. I will explain what are ordered/unordered graph algorithms and how optimistic parallelism is achieved using transactional boosting.

In the second part of the talk I will describe a new shape analysis, which is used for analyzing graph algorithms written with Galois. The shape analysis infers properties that can be used to optimize the graph algorithm by reducing two of the main overheads of the system --- synchronization overheads and rollback logging overheads, We implemented the analysis on top of TVLA and applied it to several graph algorithms. The optimized (parallel) graph algorithms run 2x to 12x faster than the unoptimized algorithms.

This talk is based on joint work with Dimitrios Prountzos, Keshav Pingali, and Kathryn McKinley, presented at POPL 2011.