基于最大负载偏移率的并行负载平衡性能分析  

Parallel Load-Balancing Performance Analysis Based on Maximal Ratio of Load Offset

作　　者：张理论[1] 叶红[2] 吴建平[1] 宋君强[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]北京工商大学计算机与信息工程学院,北京100037

出　　处：《计算机研究与发展》2010年第6期1125-1131,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(40505023;40775064)

摘　　要：大规模并行应用的负载平衡能力对性能的影响很大,但难以度量.针对基于局部离散格式的(有限差分、有限元等)并行应用,通过分析并行计算通信比、并行规模、问题规模、格式复杂度与并行效率之间的数量关系,提出一个"最大负载偏移率"概念,即并行任务的最大负载相对平均负载的偏移量与平均负载之比,作为衡量负载平衡能力的性能指标,并导出了一个负载平衡性能量化模型.将POP全球海洋模式Benchmark程序作为计算实例,验证了负载平衡性能模型的有效性.该模型揭示出整体并行计算性能对负载平衡的依赖程度,特别是对大规模并行计算的情形,负载平衡程度对整体性能的影响随着并行规模的增大而愈加敏感.It is well known that the measurement of load-balancing and its effect on the whole performance of massively parallel applications is a tough job. In this work, an evaluation model of load-balancing is put forward for numerical parallel computing based on local discretization schemes （finite difference, finite element, etc.）. By introducing the maximal ratio of load offset （MRLO） as the index of load-balance, the quantitative relationships between the parallel efficiency and the ratio of computing to communication, parallel scale, problem size, and complexity of numerical schemes are analysed. MRLO is a basal parameter of the evaluation model. A famous global ocean circulation model named POP benchmark is used for verification of the evaluation model. Since the ratio of walltime cutdown is equal to that of efficiency improvement, the parallel efficiency increase of POP can be predicted from both walltime and the evaluation model. The evaluation model reveals that to what extent the whole performance depends upon load-balancing. Especially for large-scale parallel computing, load-balancing is more and more sensitive to parallel efficiency with the increase of problem size and parallel scale. The result shows that load-balancing is an important bottleneck of parallel computing up to tens of thousands tasks, and researchers of parallel optimization for all kinds of applications should put more emphases on load-balancing.

关 键 词：大规模数值并行计算 负载平衡 最大负载偏移率 评估模型 性能分析 

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