On Optimizing a Class of Multi-Dimensional Loops with Reductions for Parallel Execution
On Optimizing a Class of Multi-Dimensional Loops with Reductions for Parallel Execution
复制标题
关于优化一类并行执行约简多维循环
DOI：
10.1142/s0129626497000176
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
R. Wenger
中科院分区：
文献类型：
--
作者：
Chi;P. Sadayappan;R. Wenger
本文讨论了一种形式的嵌套循环计算，是由计算物理应用程序的动机编译时优化。计算涉及多维的表面和体积积分，其中被积函数是一个产品的一些数组项。除了在处理器之间的阵列的最佳分布的问题，也有范围的操作使用加法和乘法的交换性和结合性属性的重新排序，以及分配律的应用，以显着减少执行的操作的数量。给出了运算最小化问题的形式化描述及其NP完全性证明。提出了一种确定最优形式的剪枝搜索策略。分析的通信要求和多项式时间的算法，用于确定阵列的最佳分布。
This paper addresses the compile-time optimization of a form of nested-loop computation that is motivated by a computational physics application. The computations involve multi-dimensional surface and volume integrals where the integrand is a product of a number of array terms. Besides the issue of optimal distribution of the arrays among the processors, there is also scope for reordering of the operations using the commutativity and associativity properties of addition and multiplication, and the application of the distributive law to significantly reduce the number of operations executed. A formalization of the operation minimization problem and proof of its NP-completeness is provided. A pruning search strategy for determination of an optimal form is developed. An analysis of the communication requirements and a polynomial-time algorithm for determination of optimal distribution of the arrays are also provided.