多层快速多极子算法并行实现的数据划分策略  

DATA PARTITIONING STRATEGY FOR PARALLEL IMPLEMENTATION OF MLFMA

作　　者：胡悦[1] 童维勤[1] 龚治勋[1] 

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

出　　处：《计算机应用与软件》2012年第2期118-121,共4页Computer Applications and Software

基　　金：上海市重点学科建设项目(J50103);上海大学研究生创新基金(SHUCX101062)

摘　　要：虽然多层快速多极子算法在解决大尺度电磁散射问题中表现出了很好的效率,但是,当未知量达到千万时,由于复杂的结构和计算该算法很难再保持高效的计算能力。为了解决负载均衡引起的性能瓶颈问题,提出多层快速多极子算法基于八叉树的多层结构并行数据划分策略。该方法包括根据树结构中分布层和共享层不同特征的单独处理,也包括解决数据冲突的转移层的处理方法和为了减少分布存储系统中的通信时间而在分布层引入的冗余技术。实验结果表明多层快速多极子算法并行计算的开销明显减少,并且能够获得比较高的并行效率。Although the multilevel fast multipole algorithm（MLFMA） has shown great efficiency in calculating large scale electromagnetic scattering problems,when the unknowns grown up to tens of millions,it is not trivial to keep its high parallel performance because of the complicated structure and computing of MLFMA.To deal with the bottleneck caused by load balancing,a hierarchical parallel data partitioning strategy of MLFMA based on an oct-tree is proposed.The partitioning strategy consists of separate processing of different properties the distributed layer and the shared layer possess respectively,and also contains a handling approach for transition layer set up to solve the coexisting data collision,and a redundant technique applied in distributed layer to minimise communication time in distributed memory system.Experiment results demonstrate that the computing cost is conspicuously cut down in parallelisation of MLFMA,and a high parallel efficiency has been obtained.

关 键 词：多层快速多极子算法 负载均衡 并行数据划分 数据冲突 冗余技术 

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