Speculative Separation for Privatization and Reductions [abstract] (ACM DL, PDF) Nick P. Johnson, Hanjun Kim, Prakash Prabhu, Ayal Zaks, and David I. August Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2012.
Automatic parallelization is a promising strategy to improve application
performance in the multicore era. However, common programming practices such as
the reuse of data structures introduce artificial constraints that obstruct
automatic parallelization. Privatization relieves these constraints by
replicating data structures, thus enabling scalable parallelization. Prior
privatization schemes are limited to arrays and scalar variables because they
are sensitive to the layout of dynamic data structures. This work presents
Privateer, the first fully automatic privatization system to handle dynamic
and recursive data structures, even in languages with unrestricted pointers. To
reduce sensitivity to memory layout, Privateer speculatively separates memory
objects. Privateer's lightweight runtime system validates speculative
separation and speculative privatization to ensure correct parallel execution.
Privateer enables automatic parallelization of general-purpose C/C++
applications, yielding a geomean whole-program speedup of 11.4 over best
sequential execution on 24 cores, while non-speculative parallelization yields
only 0.93.
