一种基于代表元的划分算法

An Affine Partition Algorithm Based on Representative Element

划分是把程序中不同的计算和数据分配到并行处理系统的不同处理机来充分利用并行系统的计算资源、提高程序处理速度的一种优化技术.划分的效果对程序在并行系统上的执行效率将产生至关重要的影响,因此划分问题一直是并行领域研究的一个热点.但是应用程序的一些特性,如非紧密嵌套循环、一条语句对非只读数组的多次引用间存在重叠、不同语句对同一数组不同步长的引用,给有效解决划分问题设置了极大的障碍.已有的划分算法无法对具有这些特征的程序进行自动划分.虽然在对具有这些特征的程序进行手工优化过程中,存在一些直观上的划分策略,但这些策略无法应用到编译器中来指导编译器完成对程序的自动划分.文中根据这类程序的特点,提出了一种基于代表元的划分算法.该算法通过使用程序中对划分计算产生实际影响的数组引用作为代表元素构造各种划分的限制条件,完成程序的划分.同时通过寻找最大一致性数据划分方向有效减少了程序划分过程中的数据重组织通信.该算法已经在AFT2004中实现,并对应用程序获得了很好的效果.

Partition is an optimization technique that distributes computations and data onto the different processors of parallel systems to get the maximizing parallelism and minimizing communication. The effect of partition algorithm can directly affect the performance of parallel systems. But there are many obstacles to effective partition in practical programs, such as imperfect loop nests and different array access scope. Previous partition algorithms can only finish the partition of sequences of perfect loop nests or cannot solve data partition consistent problem for different array access scope. This paper presents an affine partition algorithm based on representative element. When constructing the constraint relation for partition, it only remains the array references, which have contributes to partition constraint relation indeed and remove the trivial partition conflicts through discarding redundant array references to same array. This paper also presents a consistent partition algorithm to solve the data partition consistent problem, The algorithms can not only solve more practical partition problems, but also effectively reduce data reorganization communication in data partition. This technique has been implemented in AFT2004 parallel compiling system and can get better results for some practical programs.