• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >On the parallel execution time of tiled loops
【24h】

On the parallel execution time of tiled loops

机译：平铺循环的并行执行时间

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops that have a regular stencil of data dependences. Tiling is a well-known compiler optimization that improves performance on such loops, particularly for computers with a multilevel hierarchy of parallelism and memory. Most previous work on tiling is limited in at least one of the following ways: they only handle nested loops of depth two, orthogonal tiling, or rectangular tiles. In our work, we tile loop nests of arbitrary depth using polyhedral tiles. We derive a prediction formula for the execution time of such tiled loops, which can be used by a compiler to automatically determine the tiling parameters that minimizes the execution time. We also explain the notion of rise, a measure of the relationship between the shape of the tiles and the shape of the iteration space generated by the loop nest. The rise is a powerful tool in predicting the execution time of a tiled loop. It allows us to reason about how the tiling affects the length of the longest path of dependent tiles, which is a measure of the execution time of a tiling. We use a model of the tiled iteration space that allows us to determine the length of the longest path of dependent tiles using linear programming. Using the rise, we derive a simple formula for the length of the longest path of dependent tiles in rectilinear iteration spaces, a subclass of the convex iteration spaces, and show how to choose the optimal tile shape.
机译：许多计算密集型程序（例如用于微分方程，空间插值和动态编程的程序）将其大部分执行时间都花在具有规则数据依赖模板的多重嵌套循环中。切片是众所周知的编译器优化，可以提高此类循环的性能，特别是对于具有并行和内存的多层结构的计算机。以前大多数有关平铺的工作都受到以下至少一种限制：它们仅处理深度为2的嵌套循环，正交平铺或矩形图块。在我们的工作中，我们使用多面体图块对任意深度的循环嵌套进行图块化。我们推导了此类平铺循环执行时间的预测公式，编译器可使用该公式自动确定平铺参数，以最大程度地缩短执行时间。我们还解释了上升的概念，即瓦片形状与由循环嵌套生成的迭代空间形状之间关系的度量。上升是预测平铺循环执行时间的有力工具。它使我们能够推断拼贴如何影响从属磁贴的最长路径的长度，这是衡量拼贴执行时间的量度。我们使用平铺迭代空间的模型，该模型允许我们使用线性编程来确定相关图块的最长路径的长度。使用上升量，我们得出一个简单的公式，用于计算线性迭代空间中从属拼贴的最长路径的长度（凸迭代空间的子类），并展示如何选择最佳的拼贴形状。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号