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

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 explain how this parallelism can be exploited in a general way on multicore machines using the Galois system. Third, we will present several optimization strategies to reduce the overhead of the general parallelization approach, including data partitioning, fast conflict detection, and locality improvement. Attendees will be encouraged to experiment with the Galois system during the tutorial, and they will receive a free copy for their own use.

Tentative schedule:

• 1:30pm–2:30pm Amorphous data parallelism
• 2:30pm–3:00pm Extended example: breadth-first search
• 3:00pm–3:30pm Break
• 3:30pm–4:00pm Other applications
• 4:00pm–5:00pm Optimizations

The Galois system can be downloaded from here. Attendees are encouraged to download the system prior to the tutorial.