通过基于传递闭包的重叠迭代空间提取方法，实现周期性模板循环嵌套的菱形铺砌

《ACM Transactions on Architecture and Code Optimization》：Diamond Tiling for Periodic Stencil Loop Nests by Means of Transitive Closure-based Extraction of Overlapping Iteration Spaces

周期边界条件下的嵌套循环优化研究提出基于迭代空间切片和依赖图传递闭包的瓷砖方案，解决周期和非周期边界条件下的并行负载均衡问题，实验显示二维周期域性能提升3倍优于Pluto工具。

　　

摘要AI 摘要

摘要

摘要

模板计算是一类常见的循环嵌套结构，是众多科学应用中的基础组成部分。这些循环中蕴含的巨大并行潜力激发了人们对其高效提取的广泛研究，从而发展出了多种平铺方案，使得它们能够并行且负载均衡地执行，从而最大化利用多个处理单元。然而，大多数这些技术都是基于仿射变换框架的，这限制了优化范围，仅适用于具有均匀依赖关系的循环。因此，只有少数研究关注了周期性域上模板计算的局部性增强和并行化问题，在这类问题中，相对边上的边界网格点被视为邻居。

在本文中，我们展示了如何基于迭代空间切片框架推导出一种有效且负载均衡的平铺方案，并具备并行启动特性。首先将原始的超矩形平铺单元扩展以包含所有依赖源，然后通过数据依赖图的传递闭包迭代地提取冗余计算区域。这种方法结合了之前介绍的平铺单元修正技术（用于空间维度），将优化的适用范围扩展到了具有周期性边界条件和非均匀依赖关系的模板计算。我们的实验评估表明，当应用于均匀循环嵌套时，所提出的算法能够达到与现有技术相当的结果；而对于周期性域上的模板计算，其性能有显著提升，相比相关技术可提速高达3倍。

AI 摘要

AI 生成摘要（实验结果）

本摘要是由自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助读者发现研究价值、评估文章相关性，并辅助来自相关研究领域的读者理解本文内容。它是对作者提供的摘要的补充，作者提供的摘要仍是文章的官方总结。完整文章才是权威版本。点击此处了解更多。

点击此处对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的版本。

AI 生成的摘要

该摘要由基于已发表文章文本的自动化系统生成。

生成日期：2026年1月30日。

模板计算在科学和工程应用中至关重要，它涉及基于相邻点对空间网格的迭代更新，通常表现为具有时间和空间维度的嵌套循环。虽然实现起来较为简单，但传统的模板计算存在高内存消耗和同步问题，由于数据局部性差和并行化效率低下而限制了性能。为了解决这些问题，平铺技术将迭代过程重新组织为较小的块或平铺单元，从而提高缓存利用率并实现并行执行，同时保持数据依赖关系的正确性。传统的平铺方法主要处理均匀依赖关系和非周期性边界条件，其中网格边界是固定且分离的。

周期性边界条件将网格的相对边视为邻居，用于模拟环形或环面等封闭表面，这引入了非均匀的、环绕式的依赖关系，使得平铺变得复杂。大多数已知的平铺算法难以处理周期性问题，常常导致性能不佳或调度无效。本文提出了一种新颖的方法，结合了多面体编译和迭代空间切片技术，为具有周期性和非周期性边界的模板循环生成有效且负载均衡的平铺方案。该方法利用数据依赖图的传递闭包来识别所有直接和间接依赖关系，扩展初始的超矩形平铺单元以覆盖这些依赖关系，然后提取重叠区域以形成独立、原子化的平铺单元。这种迭代过程确保了正确性和并行启动特性，即平铺单元可以同时开始并行执行而无需同步开销。

该方法可推广到多维空间网格，在一个空间维度上使用菱形平铺实现并行性，在其他维度上使用超矩形平铺来优化数据局部性。这种混合方式比在所有方向上使用菱形平铺的方案更简单，后者可能会降低性能。该算法通过利用传递闭包框架，能够处理均匀和非均匀依赖关系，包括来自周期性边界的依赖关系。实验表明，结合这些转换的优化编译器在性能和可扩展性方面与现有技术（如Pluto）相当或更优，尤其是在处理具有周期性域的一维和二维模板代码时。

总之，本文提出的方法通过提供一种统一的平铺方案来改进模板循环优化，该方案能够正确处理包括周期性边界在内的复杂依赖关系模式，改善并行工作负载平衡，并提高缓存利用率。利用传递闭包进行依赖关系分析，可以精确识别迭代依赖关系，从而构建出在利用并行性和数据局部性的同时保持正确性的平铺单元。该方法在多面体框架中的实现以及实验结果验证了其性能竞争力和高效的并行扩展性，适用于各种模板基准测试。

此内容由 AI 生成。了解更多