A static cut-off for task parallel programs
A static cut-off for task parallel programs
复制标题
任务并行程序的静态中断
DOI：
10.1145/2967938.2967968
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kenjiro Taura
中科院分区：
文献类型：
--
作者：
Shintaro Iwasaki;Kenjiro Taura
支持动态和分层并行的任务并行模型被认为是实现更高性能和可编程性的一个有前途的方向。分而治之是任务并行模型中最常用的习语，它将问题实例分解成较小的实例，直到它们变得“微不足道”才能解决。然而，如果为每个子问题创建一个任务，则会产生很高的任务开销。为了减少这一开销，通常使用“截断”，这消除了不太可能有益的任务创建。手动截断通常通过当子问题小于阈值时停止任务创建来扩大叶任务，并可能将扩大的叶任务转换为专门用于解决小实例的版本(例如，使用循环而不是递归调用)；它重复了编码工作并阻碍了生产率。粗略地说，它达到了手动切断的效果，但自动。编译器尝试识别递归在恒定步数内停止的条件，如果是这样，则在编译时消除任务创建，这允许进一步的编译器优化。在终止条件分析的基础上，除了用函数调用替换叶任务外，还提出了另外两种优化方法：一是在不增加指数性代码的情况下消除那些函数调用；二是将叶任务转化为循环，从而进一步减少开销，甚至促进向量化。评估结果表明，与原算法相比，我们提出的截断优化算法获得了8.0x的几何平均加速比。
Task parallel models supporting dynamic and hierarchical parallelism are believed to offer a promising direction to achieving higher performance and programmability. Divide-and-conquer is the most frequently used idiom in task parallel models, which decomposes the problem instance into smaller ones until they become "trivial" to solve. However, it incurs a high tasking overhead if a task is created for each subproblem. In order to reduce this overhead, a "cut-off" is commonly used, which eliminates task creations where they are unlikely to be beneficial. The manual cut-off typically enlarges leaf tasks by stopping task creations when a subproblem becomes smaller than a threshold, and possibly transforms the enlarged leaf tasks into specialized versions for solving small instances (e.g., use loops instead of recursive calls); it duplicates the coding work and hinders productivity.In this paper, we describe a compiler performing an effective cut-off method, called a static cut-off. Roughly speaking, it achieves the effect of manual cut-off, but automatically. The compiler tries to identify a condition in which the recursion stops within a constant number of steps and, when it is the case, eliminates task creations at compile time, which allows further compiler optimizations. Based on the termination condition analysis, two more optimization methods are developed to optimize the resulting leaf tasks in addition to replacing them with function calls; the first is to eliminate those function calls without exponential code growth; the second transforms the resulting leaf task into a loop, which further reduces the overhead and even promotes vectorization. The evaluation shows that our proposed cut-off optimization obtained significant speedups of a geometric mean of 8.0x compared to the original ones.