并行多层快速多极子算法最细层数据的建立

上海大学学报(自然科学版) ›› 2009, Vol. 15 ›› Issue (4): 421-425.

并行多层快速多极子算法最细层数据的建立

郭海林胡悦童维勤支小莉

上海大学计算机工程与科学学院，上海 200072

出版日期:2009-08-30 发布日期:2009-08-30
通讯作者: 童维勤(1964~),男,教授,博士,研究方向为高性能计算. E-mail:wqtong@shu.edu.cn
基金资助:
总装预研项目

Finest Level Data Building for Parallel Multi-level Fast Multi-pole Algorithm

School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China

Online:2009-08-30 Published:2009-08-30

摘要/Abstract

摘要：

分布树最细层数据的建立是并行多层快速多极子算法(MLFMA)的基础.最细层数据分布均匀与否，会影响到后续整个算法的负载平衡及其并行效率.研究了最细层数据的建立方法，提出采用并行正则采样排序算法来代替众多文献所推荐的并行桶排序算法, 以此来建立分布树的最细层数据.针对多种常见的散射体在不同处理器数下的实验结果表明, 在大多数情况下，改进后的算法较原算法性能有较为明显的提高.

关键词: 多层快速多极子算法；分布树；并行正则采样排序；并行桶排序；消息传递接口

Abstract:

The finest level data building of a distributed tree is a foundation of parallel multi-level fast multi-pole algorithm (MLFMA). Whether the finest level data is distributed equally or not will affect load balancing of the whole algorithm and its parallel efficiency. This paper studies building methods of the finest level data for the parallel MLFMA. Instead of parallel bucket sort recommended by some authors, a scheme using parallel regular sampling sort algorithm to construct the finest level data of the distributed tree is presented. Experimental results on some common scattering objects with different numbers of processors show that, in most cases, the improved algorithm can achieve better performance than the original one.

Key words: multi-level fast multi-pole algorithm (MLFMA); distributed tree; parallel regular sampling sort; parallel bucket sort; message passing interface (MPI)

中图分类号:

TP301
TN95

郭海林胡悦童维勤支小莉. 并行多层快速多极子算法最细层数据的建立[J]. 上海大学学报(自然科学版), 2009, 15(4): 421-425.

GUO Hai-Lin, HU Yue, TONG Wei-Qi, ZHI Xiao-Li. Finest Level Data Building for Parallel Multi-level Fast Multi-pole Algorithm[J]. Journal of Shanghai University（Natural Science Edition）, 2009, 15(4): 421-425.