Autotuning of a Cut-Off for Task Parallel Programs
Autotuning of a Cut-Off for Task Parallel Programs
复制标题
自动调整任务并行程序的中断
DOI：
10.1109/mcsoc.2016.51
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kenjiro Taura
中科院分区：
文献类型：
--
作者：
Shintaro Iwasaki;Kenjiro Taura
任务并行程序设计模型被认为是具有动态负载平衡的并行程序设计模型之一。由于该模型支持层次并行，因此适用于并行分治算法。然而，大多数简单的分治任务并行程序都有很高的任务开销，因为它们往往会创建太细粒度的任务。有两个关键的想法，以提高这样的程序的性能：串行化的任务在截止条件下，这是减少并发和并行开销之间的权衡，并应用有效的转换的条件下的任务。两者都对算法特性敏感，在某些情况下仅使用编译器进行优化是无效的。为了解决这个问题，我们提出了一个自动调优框架分治任务并行程序。该方法自动搜索三种基本变换方法和切换条件的最佳组合，减少了程序员的工作量。我们将其实现为LLVM中的优化通道。测试结果表明，与原始的朴素任务并行程序相比，性能有了显著的提高（从1.5倍提高到228倍）。此外，它证明了我们的自动调优框架获得的绝对性能是可比的循环并行程序。
A task parallel programming model is regarded as one of the promising parallel programming models with dynamic load balancing. Since this model supports hierarchical parallelism, it is suitable for parallel divide-and-conquer algorithms. Most naive divide-and-conquer task parallel programs, however, suffer from a high tasking overhead because they tend to create too fine-grained tasks. There are two key idea to enhance the performance of such a program: serializing a task in a cut-off condition which is a tradeoff between decrease of concurrency and parallelization overheads, and applying effective transformations for the task in the condition. Both are sensitive to algorithm features, rendering optimization solely with a compiler ineffective in some cases. To address this problem, we proposed an autotuning framework for divide-and-conquer task parallel programs. It automatically searches for the optimal combination of three basic transformation methods and switching conditions with less programmers' efforts. We implemented it as an optimization pass in LLVM. The evaluation shows the significant performance improvement (from 1.5x to 228x) over the original naive task parallel programs. Moreover, it demonstrates the absolute performance obtained by our autotuning framework was comparable to that of loop parallel programs.