The goal of this tutorial is to teach attendees how to systematically and effectively parallelize irregular applications for modern multicore systems. Irregular applications use pointer-based data structures like graphs and trees - some important examples are finite-element mesh generators and partitioners, SAT solvers, maxflow algorithms, and event-driven simulation. Until recently, relatively little was known about how to parallelize irregular applications systematically, in spite of their central role in many problem domains.

In this tutorial, we will first present a concept called amorphous data-parallelism (ADP), which captures the patterns of parallelism in irregular applications, and which includes the data-parallelism found in regular algorithms. Second, we will introduce ParaMeter, a tool that automatically extracts and analyzes the available ADP in Java programs, and demonstrate how to use ParaMeter to investigate parallelism of irregular algorithms. This analysis will show that applications from a broad range of domains exhibit large amounts of ADP and therefore lots of potential for parallelization. Fourth, we will explain how this parallelism can be exploited in a general way on multicore machines using the Galois system. Fifth, we will present several optimization strategies to reduce the overhead of the general parallelization approach.

Schedule: The Galois system (and ParaMeter) can be downloaded from here. Attendees are encouraged to download Galois prior to the tutorial.