Run-time array redistribution is necessary to enhance the performance of parallel programs on distributed memory supercomputers. In this paper, we present an efficient algorithm for array redistribution from cyclic(x) on P processors to cyclic(Kx) on Q processors. The algorithm reduces the overall time for communication by considering the data transfer, communication schedule, and index computation costs. The proposed algorithm is based on a generalized circulant matrix formalism . Our algorithm generates a schedule that minimizes the number of communication steps and eliminates node contention in each communication step. The network bandwidth is fully utilized by ensuring that equal-sized messages are transferred in each communication step. Furthermore, the procedure to compute the schedule and the index sets is extremely fast. It takes O(max(P, Q)) time. Therefore, our proposed algorithm is suitable for run-time array redistribution.To evaluate the performance of our scheme, we have implemented the algorithm using C and MPI. The experiments were conducted on the IBM SP2. The experimental results show that the proposed algorithm outperforms well-known algorithms when the total communication time including the data transfer and schedule and index computation times are considered.
展开▼
机译：运行时数组重新分发对于增强分布式内存超级计算机上并行程序的性能是必需的。在本文中，我们提出了一种有效的数组重分配算法，该算法可以将 P 处理器上的循环（ x ）分配给循环 （ Kx ）在 Q 处理器上。该算法通过考虑数据传输，通信调度和索引计算成本来减少通信的总时间。该算法基于广义循环矩阵形式主义。我们的算法生成了一个调度表，该调度表将通信步骤的数量减至最少，并消除了每个通信步骤中的节点争用。通过确保在每个通信步骤中传输相等大小的消息，可以充分利用网络带宽。此外，计算时间表和索引集的过程非常快。这需要 O （ max （ P，Q ））时间。因此，我们提出的算法适合于运行时数组的重新分配。为了评估我们的方案的性能，我们使用C和MPI实现了该算法。实验是在IBM SP2上进行的。实验结果表明，在考虑包括数据传输，调度和索引计算时间在内的总通信时间时，该算法优于著名算法。
展开▼
