Automatic parallelization of pure method calls via conditional future synthesis
Automatic parallelization of pure method calls via conditional future synthesis
复制标题
通过条件未来合成自动并行化纯方法调用
DOI：
10.1145/2983990.2984035
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Vivek Sarkar
中科院分区：
文献类型：
--
作者：
R. Surendran;Vivek Sarkar
我们介绍了一种新颖的方法，用于使用期货自动使纯方法调用的执行并行。我们的方法建立在三种新技术基础上，以通过未来的综合来应对自动并行化的挑战：候选未来综合，并行性益处分析和阈值表达综合。在候选未来合成期间，我们的系统注释纯方法称为异步表达式，并将并行程序与未来对象及其类型声明合成。接下来，该系统执行并行益处分析，以确定根据从多个测试输入收集的执行配置文件信息，由于间接费用的原因，可能需要顺序执行哪些异步表达式。最后，阈值表达式合成使用并行性益处分析的输出来综合谓词表达式，该表达式可以在运行时确定是否应顺序或并行执行特定的纯方法调用。我们已经实施了我们的方法，并且从一系列顺序的Java基准测试的完整系统的实验评估中获得的结果非常令人鼓舞。我们的评估表明，我们的方法可以提供相对于顺序程序时使用8个处理器内核时相对于顺序程序提供高达7.4倍（几何平均值）的显着速度，除了提供顺序程序和测试案例以进行并行性分析的测试案例外，程序员的努力为零。 。
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 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 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, 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.4x (geometric mean of 3.69x) 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.