网格结构上具有最小启动时间的全局扩散算法

Algorithm for all-to-all personalized exchange with minimum start-up cost on mesh

全局扩散应用在矩阵转置、FFT等许多重要的并行算法中。提出了一种新的虫洞寻径2d×2d网格结构上无通信冲突的全局扩散算法。该算法采用了一种从下至上的迭代方式,通信路径规则,扩散数据有序可循。通过性能比较表明,该算法不仅达到了最小启动时间O(d)和最优消息传递时间O(23d),同时其系数取值更优于其它算法。对消息启动占通信主导地位的现代并行机来讲,在除大消息的全局扩散中它是更好的算法。

All-to-all personalized exchange occurs in many important parallel algorithms, such as matrix transpose, FFT etc. This paper presents a new algorithm for all-to-all personalized exchange for wormhole switched %2~d×2~d% mesh-connected multiprocessors, it is contention-free. It operates in a recursive, bottom-up fashion, due to the regularity of its communication route and exchanged data ,it can be realized easily. Since this algorithm not only arrives at lower bound on start-up cost of %O(d)% and message transmission of %O(2~{3d})%, but also its coefficient is better than that of existing algorithm, so for modern parallel architectures where the start-up cost of message transmissions still dominates, it is the better algorithm except for large block sizes.;