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 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