- Keshav Pingali, The University of Texas at Austin
- Milind Kulkarni, Purdue University
- Mario Mendez-Lojo, The University of Texas at Austin
- Donald Nguyen, 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 introduce ParaMeter, a tool that automatically extracts and analyzes the available ADP in Java programs. Third, we will 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. Fifth, 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 ParaMeter during the tutorial, and they will receive a free copy for their own use.