Defining and Implementing Commutativity Conditions for Parallel Execution

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 paral- lelism called amorphous data-parallelism. Prior approaches to par- allelizing 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 struc- ture 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 paral- lelism. Prior work has shown that abstract locks can be used to cap- ture 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 condi- tions 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 quantita- tive study demonstrating the benefits of abstract locking and gate- keeping in amorphous data-parallel programs. We also present an efficient implementation of gatekeeping, which we evaluate on a real-world application.