Blogs (9) >>
Sun 30 October - Fri 4 November 2016 Amsterdam, Netherlands
Wed 2 Nov 2016 10:55 - 11:20 at Matterhorn 1 - Optimization and Performance Chair(s): Jan Vitek

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.