Discovering Optimistic Data-Structure Oriented Parallelism

The parallelization of algorithms depends in large part on the understanding of data-access patterns. Regular data-structures, such as dense arrays, make pattern analysis easier as data-dependence graphs can be built to clearly identify computations that can happen in parallel. However, an important class of algorithms, such as machine learning and search, rely on “irregular” data-structures which make heavy use of pointers (trees, sparse graphs for example). While regular data-structures have well-defined properties with regards to their layout in memory, pointers obfuscate this.

In this paper, we argue that structure can also be found for irregular data-structures but at a different level of abstraction: the symbolic one. For example, each step of abreadth-first traversal of a binary tree on a node ‘n’ will visit its ‘left’ child pointer, followed by its ‘right’ child pointer. While the relationships between the memory addresses of ‘n’ and those pointed to by ‘left’ and ‘right’ may not exhibit a pattern, there is a definite relationship between the symbolic names ‘n’, ‘n::left’ and ‘n::right’, where ‘::’ denotes a parent-child relationship. These relationships can be used to compute data-dependence graphs just in time and therefore be able to help in determining whether two operations can run in parallel.

We present a trace-driven approach capable of identifying such relationships and motivate how the information could be used, for example, to improve optimistic parallel execution (such as STMs) as demonstrated by Cledat et al. in [3].