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

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

作　　者：郭海林[1] 胡悦[1] 童维勤[1] 支小莉[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072

出　　处：《上海大学学报（自然科学版）》2009年第4期421-425,共5页Journal of Shanghai University:Natural Science Edition

基　　金：总装预研项目

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TN95[自动化与计算机技术—计算机科学与技术]