How Much Parallelism is There in Irregular Applications?

Milind Kulkarni, Martin Burtscher, Rajasekhar Inkulu, Keshav Pingali, and Calin Cascaval

PPoPP 2009 · Principles and Practices of Parallel Programming · February 2009 · pp. 3-14

Acceptance rate 24%

Abstract

Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs?

In this paper, we describe the design and implementation of a tool called ParaMeter that produces parallelism profiles for irregular programs. Parallelism profiles are an abstract measure of the amount of amorphous data-parallelism at different points in the execution of an algorithm, independent of implementation-dependent details such as the number of cores, cache sizes, load-balancing, etc. ParaMeter can also generate constrained parallelism profiles for a fixed number of cores. We show parallelism profiles for seven irregular applications, and explain how these profiles provide insight into the behavior of these applications.

BibTeX

@inproceedings{kulkarni09ppopp,
  author    = {Milind Kulkarni and Martin Burtscher and Rajasekhar Inkulu and Keshav Pingali and Calin Cascaval},
  title     = {How Much Parallelism is There in Irregular Applications?},
  booktitle = {Proceedings of the Principles and Practices of Parallel Programming (PPoPP)},
  pages     = {3--14},
  publisher = {ACM},
  address   = {Raleigh, NC, USA},
  year      = {2009},
  month     = feb,
  doi       = {10.1145/1504176.1504181}
}