Defining and Implementing Commutativity Conditions for Parallel Execution

Milind Kulkarni, Dimitrios Prountzos, Donald Nguyen, and Keshav Pingali

Purdue University, School of Electrical and Computer Engineering, TR-ECE-09-11, 2009 · August 2009

Partly superseded by PLDI 2011(a)

Abstract

Irregular applications, which manipulate complex, pointer-based data structures, are a promising target for parallelization. Recent studies have shown that these programs exhibit a kind of parallelism called amorphous data-parallelism. Prior approaches to parallelizing these applications, such as thread-level speculation and transactional memory, often obscure parallelism because they do not distinguish between the concrete representation of a data structure and its semantic state; they conflate metadata and data.

Exploiting the semantic commutativity of methods in complex data structures is a promising approach to exposing more parallelism. Prior work has shown that abstract locks can be used to capture a subset of commutativity properties, however, abstract locks cannot uncover the parallelism in some complex data structures, such as kd-trees and union-find structures. In this paper, we propose a more flexible implementation of commutativity properties, called gatekeepers, which capture more complex commutativity conditions and thus expose more parallelism.

We provide a formal definition of semantic commutativity and define conditions under which abstract locking can be applied and those under which gatekeeping is necessary.We present a quantitative study demonstrating the benefits of abstract locking and gatekeeping in amorphous data-parallel programs. We also present an efficient implementation of gatekeeping, which we evaluate on a real-world application.

BibTeX

@techreport{kulkarni09tr,
  author      = {Milind Kulkarni and Dimitrios Prountzos and Donald Nguyen and Keshav Pingali},
  title       = {Defining and Implementing Commutativity Conditions for Parallel Execution},
  number      = {TR-ECE-09-11},
  institution = {Purdue University, School of Electrical and Computer Engineering},
  year        = {2009},
  month       = aug
}