数据并行程序中的动态负载平衡模型

A Model for Data-parallel Dynamic Load Balancing

在研究分析已有的负载平衡策略算法的基础上．应用Ｄｅｍｐｓｔｅｒ－Ｓｈａｆｅｒ的信任函数理论，提出了一种基于信度网络的负载平衡策略算法，此算法较适应动态负载平衡，而且优于负载平衡的随机算法，若忽略系统的通信花费则可达到系统的完全负载平衡，综合各种费用，提出的算法通过状态管理器，在不完全信息的状态下可使系统达到较满意的平衡．此外，基于信度网络的负载平衡策略算法不仅适应于虚拟非规则网络，也适应于虚拟规则网．

This paper analyzes the exist algorithms of data-parallel load balancing strategy. Based on the Dempster-Shafer theory (Belief function theory), a new. load distribution data-parallel algorithm for dynamic data-parallel programming is proposed. The new algorithm improves the random algorithm. Neglecting the communication cost, it can insure the system's load balance. In the case that communication cost and other cost are considered and the system information is not complete. with an analytical method, we show that the scheme converses towards the satisfactory optimum. Besides, the new algorithm allows the use or regular and/or irregular communication patterns to exchange the words between processors