Perspective: A Sensible Approach to Speculative Automatic Parallelization [abstract] (ACM DL, PDF)
Sotiris Apostolakis, Ziyang Xu, Greg Chan, Simone Campanoni, and David I. August
Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), March 2020.
Accept Rate: 18% (86/476).
Awarded all top ACM Reproducibility Badges offered by the Artifact Evaluation Committee.
The promise of automatic parallelization, freeing programmers from the
error-prone and time-consuming process of making efficient use of
parallel processing resources, remains unrealized. For decades, the
imprecision of memory analysis limited the applicability of
non-speculative automatic parallelization. The introduction of
speculative automatic parallelization overcame these applicability
limitations, but, even in the case of no misspeculation, these
speculative techniques exhibit high communication and bookkeeping
costs for validation and commit. This paper presents
Perspective, a speculative-DOALL parallelization framework that
maintains the applicability of speculative techniques while
approaching the efficiency of non-speculative ones. Unlike current
approaches which subsequently apply speculative techniques to overcome
the imprecision of memory analysis, Perspective combines a
novel speculation-aware memory analyzer, new efficient speculative
privatization methods, and a planning phase to select a minimal-cost
set of parallelization-enabling transforms. By reducing speculative
parallelization overheads in ways not possible with prior
parallelization systems, Perspective obtains higher overall
program speedup (23.0x for 12 general-purpose C/C++ programs
running on a 28-core shared-memory commodity machine) than Privateer
(11.5x), the prior automatic DOALL parallelization system with
the highest applicability.