Programs admitting a polyhedral representation can be transformed in many ways for locality and parallelism, notably loop tiling. Data flow analysis can then compute dependence relations between iterations and between tiles. When tiling is applied, certain iteration-wise dependences cross tile boundaries, creating the need for inter-tile data communication. Previous work computes it as the flow-in and flow-out sets of iteration tiles. In this paper, we propose a partitioning of the flow-out of a tile into the maximal sets of iterations that are entirely consumed and incur no redundant storage or transfer. The computation is described as an algorithm and performed on a selection of polyhedral programs. We then suggest possible applications of this decomposition in compression and memory allocation.
翻译:允许多角度代表的程式可以以多种方式改变地点和平行方式, 特别是环形砖块。 数据流分析可以随后计算迭代之间和砖块之间的依赖关系。 在使用平铺时, 某些迭代偏重跨砖块边界, 从而产生对跨砖块数据通信的需要 。 先前的计算工作将它作为迭代砖块的流进和流出组合 。 在本文中, 我们提议将一个瓷砖流出分解为最大迭代体, 这些迭代体完全消耗, 并且不产生多余的存储或转移。 计算被描述为算法, 并按选择的多面体程序进行 。 然后我们提出这种分解在压缩和记忆分配中的可能应用 。