An affine partitioning algorithm to maximize parallelism and minimize communication
An affine partitioning algorithm to maximize parallelism and minimize communication
复制标题
DOI：
10.1145/305138.305197
复制
发表时间：
1999-06
期刊：
影响因子：
--
通讯作者：
Amy W. Lim;Gerald I. Cheong;M. Lam
中科院分区：
文献类型：
--
作者：
Amy W. Lim;Gerald I. Cheong;M. Lam
仿射分区框架统一了许多有用的程序变换，例如单模态变换（交换、反转、倾斜）、循环融合、裂变、缩放、重索引和语句重排序。本文基于这一统一框架提出了一种算法，它能在具有任意循环嵌套和仿射数据访问的程序中最大限度地提高并行性，同时最小化通信量。我们的算法可以找到最优仿射分区，从而以最小的同步程度实现最大的并行度。此外，该算法还采用贪婪算法，通过调整不同循环的计算分区、权衡多余的并行度、选择流水线并行而非全并行（如果能显著减少通信量）等方法，启发式地最小化循环间的通信量。该算法在最大化以下并行度方面是最优的：(1) 不需要通信；(2) 近邻通信和一定数量的同步；(3) 近邻通信和 O(n) 同步，其中 n 是循环的迭代次数。
An affine partitioning Framework unifies many useful program transforms such as unimodular transformations (interchange, reversal, skewing), loop fusion, fission, scaling, reindexing, and statement reordering. This paper presents an algorithm, based on this unified framework, that maximizes parallelism while minimizing communication in programs with arbitrary loop nestings and affine data accesses. Our algorithm can find the optimal affine partition that maximizes the degree of parallelism with the minimum degree of synchronizations. In addition, it uses a greedy algorithm to minimize communication between loops heuristically by aligning the computation partitions for different loops, trading off excess degrees of parallelism, and choosing pipelined parallelism over doall paralleIism if it can significantly reduce the communication. The algorithm is optimal in maximizing the degrees of parallelism that require (1) no communication, (2) near-neighbor communication and a constant number of synchronizations, and (3) near-neighbor communication and O(n) synchronizations where n is the number of iterations in a loop.