Space-Time Loop Tiling for Dynamic Programming Codes

doi:10.3390/electronics10182233

Space-Time Loop Tiling for Dynamic Programming Codes

2021-09-12

0

OA

AI

DOI：10.3390/electronics10182233

原文链接

原文求助

摘要

En 中文

我们提出了一种新的时空循环平铺方法，并展示了其应用于生成具有增强局部性的三种动态规划算法的并行平铺代码。该技术设想，对于每个循环嵌套语句，首先生成子空间，使得它们的交集形成空间平铺。空间平铺可以按字典序或使用波前技术并行枚举。然后，在每个空间平铺内形成时间切片，这些切片按字典序枚举。目标平铺在每个空间平铺内由多个时间切片表示。我们解释了时空循环平铺的基本思想，并通过示例进行说明。接着，我们提出了一个形式化算法并证明其正确性。该算法已实现在公开可用的TRACO编译器中。实验结果表明，通过所提出方法生成的并行代码优于密切相关的手动生成的代码或使用仿射变换生成的代码。通过所提出方法生成的代码的主要优势在于其增强的局部性，这是由于将每个较大的空间平铺拆分为由时间切片表示的多个较小的平铺。

Space-Time Loop Tiling for Dynamic Programming Codes

摘要

期刊

机构

引用论文