数据不规则问题并行计算的负载平衡策略的研究

讨论以边缘通信为特征的数据不规则问题并行计算的静态负载平衡策略。从图论的角度讨论了静态负载平衡问题，给出三个优化目标，即点集等分，最短通路和通信量最小。对于以边缘通信为特征的一般数值计算问题，论述了二维问题正方形划分总通信量最小、并行效率最高，三维问题立方体划分总通信量最小、并行效率最高的结论。基于以上结论和实际课题特点，提出一种一维优先的规则分块算法和基于自动重分块的不规则分块算法相结合的方法。实验证明，该方法实现简单，能够处理不同规模的数据不规则问题，达到较优的负载平衡和较高的通信效率，提高并行程序的整体效率．

Research on static load balancing strategy of paralell computing of the data-irregular problems

The static load balancing strategy of parallel computing of the data-irregular problems with characteristic of boundary communication was discussed. The three goals of static load balancing were given from the viewpoint of graph theory:the equivalent graph partition,the shortest path and the least communication cost. Then according to the numerical problems with characteristic of boundary communication,the issue was discussed that cube partition could get the least communication cost and highest parallel efficiency for three-dimension problems and so could square partition for two-dimension problems. Based on these conclusions and the characteristics of the application problem,a new method of combining the 1D-first regular partition algorithm with the irregular partition algorithm based on auto-repartition was offered. These algorithms perform well in load balancing of parallel computing of the data-irregular problem. Experiment results show that the algorithms can be easily implemented and get load balancing and high communication efficiency.