• Keshav Pingali, The University of Texas at Austin
• Andrew Lenharth, The University of Texas at Austin
• Donald Nguyen, The University of Texas at Austin

High-performance graph computations are central to the disciplines of social network analysis and machine learning that constitute the technological foundation of multi-billion dollar companies like Google, Amazon, and Yahoo.

Unfortunately, most of what we know about parallel programming was developed for computational science applications, and very little of it is useful for writing high-performance parallel graph applications.

The goal of this tutorial is (i) to teach attendees the right abstractions for reasoning about parallelism and locality in graph applications, and (ii) to show them how to use these abstractions to build high-performance graph applications with the Galois system. This system permits programmers to code in sequential C++, leaving it to the libraries and runtime system to find and exploit parallelism and locality.

The tutorial concludes with a discussion of other graph frameworks including GraphLab, PowerGraph and the Combinatorial BLAS. We present experimental results from our industry partners that show that on social network graphs, Galois programs are often much faster than programs written in other frameworks, and they can be orders of magnitude faster for other kinds of graphs such as road network graphs.

Attendees will be encouraged to experiment with the Galois system during the tutorial.

Tentative schedule:

• 45 min: Amorphous data parallelism
• 15 min: break
• 30 min: Extended example: single-source shortest paths (part 1)
• 15 min: break
• 30 min: Extended example: single-source shortest paths (part 2)
• 15 min: break
• 30 min: Brief study: stochastic gradient descent

The slides are now available.