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

摘要

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.%虽然多层快速多极子算法在解决大尺度电磁散射问题中表现出了很好的效率,但是,当未知量达到千万时,由于复杂的结构和计算该算法很难再保持高效的计算能力.为了解决负载均衡引起的性能瓶颈问题,提出多层快速多极子算法基于八叉树的多层结构并行数据划分策略.该方法包括根据树结构中分布层和共享层不同特征的单独处理,也包括解决数据冲突的转移层的处理方法和为了减少分布存储系统中的通信时间而在分布层引入的冗余技术.实验结果表明多层快速多极子算法并行计算的开销明显减少,并且能够获得比较高的并行效率.