动态负载平衡.ppt

* Dynamic load balancing for petascale quantum Monte Carlo applications:  The Aliasmethod 陈方 曾杨 江林刚 谢劲 内容提要 Introduction Related work 动态负载平衡的算法 算法的分析 结论 1.Introduction Quantum Monte Carlo(QMC): 一类基于量子力学的计算电子结构的算法。 通过直接处理量子力学的多体问题， 精确度比密度 泛函理论（ DFT）这些方法要高，但是计算量大很 多。 可用于并行机上，DFT不能用于并行机上。 Diffusion Monte Carlo (DMC)： 最流行的一种用来预测物质和0度条件下的化 学性质的ＱＭＣ方法。 计算过程不仅并行，且需要通信。 缺点： 需要频繁的负载平衡和大量的重新分配步骤。随着处理单元的增加，这将成为影响性能的一个重要因素。 包括一系列的随机游走（代表一种量子状态），不断地移动。一个随机游走根据它的能量和所有随机游走的能量的平均值的相对关系，终止或者重新创建。 权值可能和每个随机游走有关，权值会适当地增加会减少。由此导致了负载不平衡。 DMC并行地把这一系列的随机游走重新分配到可用的计算内核上。当每个计算内核上的随机游走的数目保持很大时，相对应的负载平衡代价能够最小化。目前已经用于成千上万个计算内核上的计算机上。 负载平衡： 同步，阻塞的过程，所有的计算单元之间要进行通信。 要求很高的时效性，通信网络的高利用率，消息个数和消息规模的最小化 新方法（alias）： 是动态负载平衡方法 适用于独立相同的任务 最大特点： 任何一个进程最多只接收一个任务(其他进 程) 在千亿万级的Cray XT5 超级计算机上用 ，比现有的负载 平衡方法提高30% 动态负载平衡步骤： 流计算阶段：决定每个进程需要发送给其他进程的任务数量。 任务鉴别阶段：鉴定每个进程需要发送的实际任务。 迁移阶段：发送任务到对应的进程。 假定现在P个进程和T个相同任务(每个任务所需时间相等而且独立运行)。 负载平衡后，每个进程最多有?T/P?个任务。 ：进程i要发送给进程j的任务数量。 为了减小发送消息的个数，应该让尽量多的 为0。新算法中，最多只有(P-1)个不为0。 非零的由步骤一决定，将在第3部分讲到 新算法决定非零的只要O(P)的时间。 迁移阶段只要一次循环就可以完成。 尽管一个进程可以向多个进程发送消息，但是每个进程做多只接收一个消息。 Related work 静态分割：NP问题 几何分割：任务带有坐标信息 还有频谱分割，多层次方法…… 3.动态负载平衡算法 流程图： 开始 初始化 S[ ]=0,W[ ]=0 s=1 l=min{ j | A[j] k} ls 结束 N S[s]=l W[s]=k-A[s] A[l]=A[l]-W[s] A[l]k l=l+1 s=s+1 Y N Y 4.理论分析 现在来分析算法迁移过程的性能，这里定义了一些性能度量标准，给出了本算法相对最佳解决方案的近似率。结果如下表： （1）符号含义回顾 i：发送处理机 j：接收处理机 tij：i号处理机发送到j号处理机的任务数 P:处理机总数（P≥2） T:任务总数（T=aP*P，a为常数） k=T/P:平衡时每个处理机应该运行的任务数 l：第一个大于k的处理机编号 数组A[i]：初始时i号处理机上的任务数 数组S[i]：发送任务给i号处理机的处理机编号 数组W[i]：某一处理机发送给i号处理机的任务数 消息的尺寸/大小：消息中带有的任务数 （2）ex.1 假设P=2n，T=2n*n，n足够大 A： 最优解决方案： ?n+1号处理机发送n-2个任务给n号处理机 ?n+2号处理机至2n号处理机各发送1个任务给1号至n-1号处理机 Alias： ?n+1号处理机分别发送1个任务给1号至n-1号处理机 ?n+2号处理机发送n-2个任务给n号处理机 ?n+3号处理机发送1个任务给n+1号处理机，再发送n-3个任务给n+2号处理机 以后，4≤x≤n，n+x号处理机发送n-(x-1)个任务给n+x-1号处理机，自己剩余x个任务。 （3）ex.2 假设P=n，T=n*n，n足够大 A: 最优解决方案： 2号处理机至n号处理机各发送1个任务给1号处理机 Alias： ?2号处理机发