动态负载平衡.ppt

Dynamic load balancing for petascale quantum Monte Carlo applications:  The Aliasmethod
陈方曾杨
江林刚谢劲
内容提要
Introduction
Related work
动态负载平衡的算法
算法的分析
结论

Quantum Monte Carlo(QMC):
一类基于量子力学的计算电子结构的算法。
通过直接处理量子力学的多体问题, 精确度比密度
泛函理论( DFT)这些方法要高,但是计算量大很
多。
可用于并行机上,DFT不能用于并行机上。
Diffusion Monte Carlo (DMC):
最流行的一种用来预测物质和0度条件下的化学性质的QMC方法。
计算过程不仅并行,且需要通信。
缺点:
需要频繁的负载平衡和大量的重新分配步骤。随着处理单元的增加,这将成为影响性能的一个重要因素。
包括一系列的随机游走(代表一种量子状态),不断地移动。一个随机游走根据它的能量和所有随机游走的能量的平均值的相对关系,终止或者重新创建。
权值可能和每个随机游走有关,权值会适当地增加会减少。由此导致了负载不平衡。
DMC并行地把这一系列的随机游走重新分配到可用的计算内核上。当每个计算内核上的随机游走的数目保持很大时,相对应的负载平衡代价能够最小化。目前已经用于成千上万个计算内核上的计算机上。
负载平衡:
同步,阻塞的过程,所有的计算单元之间要进行通信。
要求很高的时效性,通信网络的高利用率,消息个数和消息规模的最小化
新方法(alias):
是动态负载平衡方法
适用于独立相同的任务
最大特点:
任何一个进程最多只接收一个任务(其他进
程)
在千亿万级的Cray XT5 超级计算机上用
,比现有的负载
平衡方法提高30%
动态负载平衡步骤:
流计算阶段:决定每个进程需要发送给其他进程的任务数量。
任务鉴别阶段:鉴定每个进程需要发送的实际任务。
迁移阶段:发送任务到对应的进程。
假定现在P个进程和T个相同任务(每个任务所需时间相等而且独立运行)。
负载平衡后,每个进程最多有⌈T/P⌉个任务。
:进程i要发送给进程j的任务数量。
为了减小发送消息的个数,应该让尽量多的
为0。新算法中,最多只有(P-1)个不为0。
非零的由步骤一决定,将在第3部分讲到
新算法决定非零的只要O(P)的时间。
迁移阶段只要一次循环就可以完成。
尽管一个进程可以向多个进程发送消息,但是每个进程做多只接收一个消息。