一种基于实测的高维动态负载平衡方法

针对大规模科学计算中的强非规则结构负载问题，作者开发出一种基于实测的动态负载平衡方法．首先，将由规则结构化网格组成的模拟区域剖分成多块；其次，把块的高维坐标转换成一维Hilbert空间填充曲线（HSFC）索引；然后，基于实测信息采用多层均权法剖分按一维HSFC索引排列的块；最后根据剖分信息重分配块以平衡负载．它把仅适用于一维的多层均权法扩展到二维和三维，并引入更多的实测信息和块数据结构．与ISP方法相比，该方法在64个CPU上提高负载平衡效率10％，在某MPP的500个CPU上模拟强非规则结构负载问题时，获得了88％的负载平衡效率和84％的并行效率．

A Measurement-Based High-Dimensional Dynamic Load Balancing Scheme

This paper presents a measurement-based dynamic load balancing(DLB) scheme in order to solve load imbalance problem arising from highly irregular structured workload(HISW) problem in large-scale scientific simulations. Firstly, it splits computational domain consisting of regular structured grid into a large number of blocks. Secondly, it maps high-dimensional index of blocks into 1-D Hilbert space filling curve(HSFC) index. Thirdly, it adopts measurement-based multilevel averaging weight(MAW) method partitioning blocks sorted by HSFC index. Finally, it redistributes block based on partitioning information for load balancing. This method develop one-dimensional MAW method into high-dimensional DLB method by introducing HSFC, block data structure and even more measurement information. Against ISP, it has improved load balancing efficiency with 10% on 64 processors.Scalability is demonstrated with a load balancing efficiency larger than 88% and a parallel efficiency 84% on 500 processors of one MPP while simulating real HISW problem.