Automatic Parallelization of Pure Method Calls via Conditional Future Synthesis
We introduce a novel approach for using futures to automatically parallelize the execution of pure method calls.
Our approach is built on three new techniques to address the challenge of automatic parallelization via future synthesis: candidate future synthesis, parallelism benefit analysis, and threshold expression synthesis. During {\em candidate future synthesis}, our system annotates pure method calls as async expressions and synthesizes a parallel program with future objects and their type declarations.
Next, the system performs a {\em parallel benefit analysis} to determine which async expressions may need to be executed sequentially due to overhead reasons, based on execution profile information collected from multiple test inputs. Finally, {\em threshold expression
synthesis} uses the output from parallelism benefit analysis to synthesize predicate expressions that can be used to determine at runtime if a specific pure method call should be executed sequentially or in parallel.
We have implemented our approach, and the results obtained from an experimental evaluation of the complete system on a range of sequential Java benchmarks are very encouraging. Our evaluation shows that our approach can provide significant parallel speedups of up to 7.4$\times$ (geometric mean of 3.69$\times$) relative to the sequential programs when using 8 processor cores, with
zero programmer effort beyond providing the sequential program and test cases for parallelism benefit analysis.
Wed 2 NovDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
10:30 - 12:10 | |||
10:30 25mTalk | A Compiler for Throughput Optimization of Graph Algorithms on GPUs OOPSLA DOI Pre-print | ||
10:55 25mTalk | Automatic Parallelization of Pure Method Calls via Conditional Future Synthesis OOPSLA DOI | ||
11:20 25mTalk | Portable Inter-workgroup Barrier Synchronisation for GPUs OOPSLA Tyler Sorensen Imperial College London, Alastair F. Donaldson Imperial College London, Mark Batty University of Kent, Ganesh Gopalakrishnan University of Utah, Zvonimir Rakamaric University of Utah DOI Pre-print | ||
11:45 25mTalk | Parallel Incremental Whole-Program Optimizations for Scala.js OOPSLA DOI Pre-print |