Autotuning multigrid with PetaBricks
Autotuning multigrid with PetaBricks
复制标题
使用 PetaBricks 自动调整多重网格
DOI：
10.1145/1654059.1654065
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Edelman
中科院分区：
文献类型：
--
作者：
Cy P. Chan;Jason Ansel;Y. Wong;Saman P. Amarasinghe;A. Edelman
在任何问题域中，算法选择对于实现最优计算性能都是必不可少的。多重网格就是一个很好的例子：不仅可以在最高的网格分辨率下进行选择，而且当问题在较粗的网格级别上被递归攻击时，程序可以切换技术，以利用具有不同缩放行为的算法。此外，具有不同收敛标准的用户必须试验参数，以产生满足其精度要求的优化算法。即使在找到优化的算法之后，用户在从一台机器迁移到另一台机器时也经常不得不从头开始。我们提出了一种算法和自动调整方法，以接近最佳和有效的方式解决这些问题。独立调整算法和每个递归级别的迭代次数的自由导致具有不同精度和性能的调整算法的指数搜索空间。为了有效地搜索这个空间，我们的自动调谐器使用了一种新的动态规划方法来自下而上地构建高效的调优算法。结果是定制的多重网格算法，投入目标计算能力以产生用户所需的精度。我们描述的技术允许用户自动生成针对用户问题、硬件和精度要求的特定组合的不同形状的调谐多重网格循环。这些循环形状决定了网格粗化和网格细化与迭代方法(如Jacobi或连续超松弛)以及直接方法交错的顺序，这些方法往往在小问题规模时具有更好的性能。在所有这些方法之间做出选择的需要将可变精度的问题推向了前台。自动调整框架不仅需要将不同可能的多重网格循环形状相互比较，而且还需要能够将调整后的循环与直接和(非多重网格)迭代方法进行比较。我们通过使用精度度量来衡量调整周期形状的有效性，并基于这一公共标准对所有算法类型进行比较来解决这个问题。在我们的结果中，我们发现，与多重网格的静态算法实现相比，在递归计算的所有级别上权衡性能和精度的灵活性使我们能够在各种平台上获得优异的性能。我们的实现使用了PetaBricks，这是一种隐式并行编程语言，其中算法选择在该语言中公开。PetaBricks编译器使用这些选项来分析、自动调整和验证PetaBricks程序。这些语言特性，尤其是自动调谐器，是使我们的实现清晰、正确和快速的关键。
Algorithmic choice is essential in any problem domain to realizing optimal computational performance. Multigrid is a prime example: not only is it possible to make choices at the highest grid resolution, but a program can switch techniques as the problem is recursively attacked on coarser grid levels to take advantage of algorithms with different scaling behaviors. Additionally, users with different convergence criteria must experiment with parameters to yield a tuned algorithm that meets their accuracy requirements. Even after a tuned algorithm has been found, users often have to start all over when migrating from one machine to another. We present an algorithm and autotuning methodology that address these issues in a near-optimal and efficient manner. The freedom of independently tuning both the algorithm and the number of iterations at each recursion level results in an exponential search space of tuned algorithms that have different accuracies and performances. To search this space efficiently, our autotuner utilizes a novel dynamic programming method to build efficient tuned algorithms from the bottom up. The results are customized multigrid algorithms that invest targeted computational power to yield the accuracy required by the user. The techniques we describe allow the user to automatically generate tuned multigrid cycles of different shapes targeted to the user's specific combination of problem, hardware, and accuracy requirements. These cycle shapes dictate the order in which grid coarsening and grid refinement are interleaved with both iterative methods, such as Jacobi or Successive Over-Relaxation, as well as direct methods, which tend to have superior performance for small problem sizes. The need to make choices between all of these methods brings the issue of variable accuracy to the forefront. Not only must the autotuning framework compare different possible multigrid cycle shapes against each other, but it also needs the ability to compare tuned cycles against both direct and (non-multigrid) iterative methods. We address this problem by using an accuracy metric for measuring the effectiveness of tuned cycle shapes and making comparisons over all algorithmic types based on this common yardstick. In our results, we find that the flexibility to trade performance versus accuracy at all levels of recursive computation enables us to achieve excellent performance on a variety of platforms compared to algorithmically static implementations of multigrid. Our implementation uses PetaBricks, an implicitly parallel programming language where algorithmic choices are exposed in the language. The PetaBricks compiler uses these choices to analyze, autotune, and verify the PetaBricks program. These language features, most notably the autotuner, were key in enabling our implementation to be clear, correct, and fast.