You are here
Discovering Optimistic Data-Structure Oriented Parallelism
Romain Cledat, Intel Labs; Santosh Pande, Georgia Institute of Technology
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-deﬁned 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-ﬁrst 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 deﬁnite 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 .
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.