并行与分布式计算动态负载均衡策略综述

杨际祥

1,2

,谭国真1,王荣生

2

(1.大连理工大学计算机科学与技术学院,辽宁大连116024;2.燕山大学计算机科学与工程系,河北秦皇岛066004)

摘 要: 动态负载均衡(Dynamic Load Balancing,DLB)是提高动态和非规则问题计算效率与规模的一个挑战问题.阐述了DLB 的一般性问题,根据DLB 策略的主要特征给出了一个综合分类方法,按分类对近30年提出的各种主要DLB 策略做了细致的分析和深入的比较,并做了策略有效性分析.在总结现有研究成果基础上,分析了该领域的最新发展趋势,为下一步的研究提出了新的问题和思路.

关键词: 并行与分布式计算;动态负载均衡(DLB);多核计算

中图分类号: TP301 文献标识码: A 文章编号: 0372-2112(2010)05-1122-09

A Su rvey of Dynamic Load Balancing Stra tegies for Parallel and

Distribu ted Compu ting

YANG J-i xiang 1,2,TAN Guo -zhen 1,W ANG Rong -sheng 2

(1.Sc hool o f Computer Sc ienc e and Te chnology,Dalian U nive rsity o f Technology,Dalian,Liaoning 116024,China;2.De partment o f Computer Sc ienc e and Enginee ring ,Y anshan Unive rsity ,Qinhuangdao,Hebei 066004,China )

Abstract: Dynamic load balancing (DLB)is one of the most important and challenging problems when solving dynamic and

non -uniform problems with unpredictable load estimates.The general dynamic load balancing problems are formulated.Following that,a comprehensive taxonomic app roach to classifying DLB strategies is propo sed,based on which detailed analy ses and thorough comparisons for vario us DLB s trategies in recent 30years are made,and analyses are performed on the validity of these s trategies.Finally,research resul ts in this direction are su mmarized,and some new issues in DL B strateg ies conforming to the trends of emerg -ing parallel architectures and applications to be further studied are pointed out.

Key words: parallel and distribu ted computing;dynamic load balancing (DL B);mult-i core computi ng

1 引言

计算机软硬件的发展使得并行与分布式计算越来越流行.同时,计算机硬件成本的降低和快速网络的出现又使得基于网络的集群和网格计算流行起来.然而,这些系统潜在性能的实际利用率通常仅为1~10%[1],对于工作站网络(NOWs)而言1B 50的负载不均衡现象也时有发生,导致系统运行效率低下.负载均衡是提高系统资源利用率和并行计算性能的一个关键技术[2,3],可分为静态和动态两类.如果负载可以在运行之前确定并事先将负载划分,则属于静态负载均衡问题;若只能在运行时测量负载并动态确定负载划分,则属于动态负载均衡(DLB)问题.

由于集群、NOWs 和网格的计算节点和通讯网络的异构性或共享性,使得难以事先进行计算负载和通讯负载的估算.事实上,存在着许多应用问题,它们对计算的

需求很难事先预测,并且通讯模式无规律.近年来,像分子动力学、计算化学和材料等计算科学与工程领域问题

的模拟计算已成为并行与分布式计算的主题[4,5].在计算过程中,它们对计算和通讯的需求是动态变化和难于事先预测的,如何充分利用系统资源有效求解这些计算问题的一个关键技术就是DLB [3,5,6].

2 DLB 问题

对于给定的一个包含计算和通讯的任务集合,以及一组通过一定拓扑连接起来的计算机,求解任务到计算机的一个映射,使得求解该问题的时间最小,这就是负载均衡的目标.下面给出几个与负载均衡问题相关的基本定义[3,7].

定义1(处理器图) 多个计算机通过一个网络拓扑组织起来,其网络拓扑可用一个无向图G p =(V p ,E p )来表示,顶点数p =|V p |,V p 中的每个顶点表示一个计

收稿日期:2009-05-12;修回日期:2009-09-13

基金项目:国家自然科学基金(No.60873256);河北省科学研究计划(No.2007492)

第5期2010年5月电 子 学 报ACTA ELECTRONICA SINICA Vol.38 No.5

May 2010

p

中的每条边表示网络中的一条链路.

定义2(任务图)并行应用程序可表示为一个有

权无向图G

o

=(V o,E o).V o中的顶点表示并行对象(或

对象组),E

o

中的边表示并行对象(或对象组)之间的通讯.每个顶点v(v I V o)有一个权w,该权表示顶点v所

表示对象的计算量.同样,每条边e

ab

=(v a,v b)(e ab I E o)有一个权c ab,该权表示由v a和v b所表示并行对象之间的通讯量.边是无向的,即在算法中不考虑通讯的方向.

定义3(任务映射)用一个映射函数表示任务(对象或对象组)到计算机上的映射M:V o y V p.如果通

过任务图中的顶点o(o I V

o

)来表示的对象被放置到处

理器p(p I V

p

)上,那么M(o)=p.映射之后,每个顶点p具有一个权W p,它表示在处理器p上的总的计算量,即这个处理器上所有对象的计算量之和

W p=E o I O w o,O={o|M(o)=p}

对于处理器p,若考虑到通讯成本开销,且通讯成本可通过所有出边的权之和来表示,则有

W p=E o I O(w o+E

e o b I E o C M(b)!=p

c ob),O={o|M(o)=p}

定义4(DLB)给定向量W,集合w o,映射函数M,以及关系式W p=E

o I M-1(p)

w o,求解一个新的映射函数M^,通过它生成一个新的向量W^,使得W^1=W1以及W^]最小.

定义5(局部性约束条件下的DLB)定义向量m和m^,有m p=M(p)和m^p=M^(p),在m^-m为最小的约束条件下求解定义4中的DLB问题.

考虑到和划分问题的关系,定义4中的D LB是一个NPC问题[7].为了最小化通讯成本,不能仅考虑每个处理器应分配多少任务,还需考虑任务放置的位置,即空间局部性或数据依赖约束.定义5增加一个局部性约束条件,约束任务重映射的移动率.

DLB技术在近30年获得了广泛的研究,许多的研究假设系统的处理器和通讯能力是同构的,并且未考虑系统的共享性或非专用性特征.在实际的系统中,并行程序执行时间受到许多和应用、系统相关的参数影响.几个重要的参数如[8]:(1)任务之间的通讯拓扑图或依赖关系图G;(2)分配给处理器的计算负载l;(3)处理器的可用计算能力c;(4)处理器间的通讯成本w.因此,一个异构环境中的D LB策略通常受到四元组(G,l, c,w)因素的影响.研究者近30年来提出了许多近似或启发式的DLB策略.

3性能度量指标

3.1定义

DLB策略的性能需要通过评价指标来进行度量,常用的几种度量指标包括并行执行时间、加速比和并行效率,其定义如下.

定义6(并行执行时间)并行执行时间是指从并行计算开始时刻到最后的处理器完成计算所经过的时间,用T p来表示.

定义7(加速比)加速比是并行求解问题获得相应益处的一种度量,它被定义为在单个处理器上求解问题所花时间T1与用p个处理器并行求解同一问题所花时间T

p

之比,用S

p

来表示,即S

p

=T1/T p.

定义8(并行效率)并行效率E

p

=S p/p=T1/ (pT p).

3.2加速比和可扩展性分析

Amdahl于1967年提出固定问题规模的加速比定律,即著名的Amdahl定律[9].根据Amdahl定律,加速比S p的上限为1/A,其中A为串行分量百分比.Gustafson 等[10]于1987年指出经典Amdahl定律蕴含着问题规模不变的假定,提出了固定时间加速比的概念,即当机器规模增大时使问题规模也增大的方法来获得加速比的提高.Sun等[11]对Amdahl和Gustafson定律做了广义的概括,提出了受限于存储器的加速比模型,充分利用了系统规模按比例增大而增加的存储器资源,获得了较高的加速比、精度和资源利用率,其中加速比接近线性加速比.Grama等[12]用等效率来描述系统和算法的可扩展性特征,在系统规模增加的同时测量需要增加多少运算量才会保持效率不变,其效率可表示为任务负载和机器规模大小p的函数.Sun等[13]提出等速度的概念来描述可扩展性的特征,其基本概念类似于等效率. Hwang等[14]提出等利用率概念,并证明了等利用率具有两个性质:(1)能够预测相对于机器规模的增加而需要增加的任务负载量;(2)与执行时间一致,即好的可扩展性总有更短的执行时间.

可扩展性被广泛用于描述系统规模和问题规模将如何影响并行机和并行算法的性能,并能利用系统规模和问题规模已知的并行系统的性能来预测系统规模和问题规模增大后的并行系统的性能.因此,它是DLB 策略的一个重要的性能度量指标.

4DLB策略

4.1分类方法

研究者在近30年提出了许多的DLB策略,当在解决实际问题时,面对如此众多的策略,设计者往往难于选择最合适的策略.本文给出一个分类方法,以便于对现有的不同DLB策略进行有效的分类与描述,从而有助于选择恰当的DLB策略来解决实际问题.

Wang等[15]对负载均衡策略的分类方法进行了研

1123

第5期杨际祥:并行与分布式计算动态负载均衡策略综述究,他们的分类标准是策略的发起者是否为发送者或接收者,其分类方法考虑了策略的发起位置和信息依赖两个方面.Casavant等[16]的分类法并不具有唯一性,即两种策略的归类存在重叠. Baumgartne r等[17]给出了一种唯一互不重叠的分类法,Xu等[18]的分类法和该分类法本质上是一致的.通过研究

Baumgartne r分类法,可以发现存在几个

问题:(1)发起类只考虑了发送者发起和接收者发起的情况,但都属于事件驱动子类,未考虑周期性发起和由设计者指定发起的情况;(2)协作式类的协商式和非协商式两个子类是一个全局和局部的信息交换过程,这与全局和局部子类的划分方法在功能与语义的本质上是一致的.图1给出了本文的分类法,该方法和Baum-gartne r分类法大致相同,同时具有以下几个特点:(1)层次状的分类法;(2)对发起类进行了扩展,考虑了周期性和由设计者指定的发起策略;(3)将局部类和非协商式类归为一类,将全局类和协商式类归为一类,并将它们划为交换信息类的子类.

4.2DLB策略研究现状

本文按照D LB策略的控制位置特征将现有的DLB 策略分为分布式、集中式和混合/层次三种策略来进行组织与描述.

4.2.1分布式策略实现分布式的D LB可有多种策略,其中一个基本策略就是近邻法.在该策略中,每个处理器和相邻处理器交换负载,实现和相邻处理器间的负载均衡,并经过多次迭代达到全局负载均衡[19].它主要包括扩散法[20]、维交换法(DEM)[20]和梯度法(GM)[21].

Cybenko等[20]给出了同构系统中扩散算法的一般化形式.在该算法的每次迭代中,每个处理器将部分负载传递给具有较低负载的相邻处理器,同时从其它具有较高负载的相邻处理器接收负载,通过交换适当数量的负载来达到更加均衡的状态.假设该算法执行过程中没有新的负载产生,并且所有负载正在计算中,那么在同步假设下,对于任意的负载初始分布,扩散法被证明是多项式收敛的.Song[22]证明了异步扩散法的收敛性,Diekmann等[23]提出了具有相同计算能力和不同通讯参数的异构系统中的扩散法,Rotaru等[8]和Els¾sser 等[24]将这些方法扩展到具有不同相对速度的处理器和不同通讯参数的异构系统上,给出了扩散算法的一般化问题.并且,Rotaru从理论上证明所给出的一般扩散算法(GDA)的收敛速度快于水动力学法[25].

针对具有不同计算能力和相同通讯参数的异构系统,Hui等[25]提出了水动力学负载均衡法,用连通器中水的流动和水的位能在均衡时最低的原理来计算负载的移动.Watts等[26]给出了一个相似的异构系统中的扩散策略.Bahi等[27]讨论了异步的负载均衡迭代算法,并通过实验验证了算法的有效性,表明异步实现法的性能优于同步法.

Das等[28]提出了一个自适应的负载均衡策略SBN-based.该策略利用对称广播网络(SBN)作为基本的网络拓扑.因为负载不一定是从一个处理器迁移到与其相邻的处理器上,所以该策略不是一个纯粹的扩散策略.通过重叠计算处理和数据迁移操作,SBN-based策略获得了比PLUM[29]所提供策略更低的负载重分布开销.

在DEM策略[20]中,每个处理器与其相邻处理器逐一进行负载均衡,在超立方体结构中的每个处理器与其所有相邻处理器交换一次负载后整个系统达到一次负载均衡[6].Xu等[30]将该策略推广到n维网格(n-D mesh)和k-ary n-cubes结构中,并推导出该策略在两种结构下的最大收敛速率的最优参数.DEM假设负载可划分为任意大小,直接将DEM方法应用到负载仅可划分为固定大小的情况下将导致负载分布不均,处理器间的最大负载差额可达log n.Rim等[31]提出一个OEM 法,可将处理器间的最大负载差额减少到最多不超过7(log n)/2ô.和DEM、CWA[32]相比,OEM方法具有较好的可扩展性.

Wu等[32]给出了超立方体结构下的CWA策略.该策略从处理器收集全局负载信息,计算每个处理器的平均负载并在处理器间发起负载均衡前广播平均负载.处理器的负载高于(低于)平均负载时为超载(低载),均衡后处理器间的最大负载差额至多为1,通讯复杂度为O(n2).

在基于梯度思想的方法中,处理器间的负载差形成梯度状的等高线,超载处理器处于等高线的较高处,其负载根据梯度流向低处(低载处理器).典型的基于梯度的方法包括梯度模型法(GM)[21]和邻域契约策略(CWN)[33].其中,GM用梯度图来描述系统的负载差异情况,负载是向着梯度最陡方向的处理器移动的,用计算负载压力面来表示负载的移动.在CWN策略中,每

1124电子学报2010年

个处理器仅需要维护与其直接相邻处理器的负载指标,负载迁移到负载最少的相邻处理器上.当一个处理器的负载在所有相邻处理器中最少时接收负载,否则转发给具有最少负载的相邻处理器.该策略设置了两个参数,即负载传递的最小跳数以及为了降低传递开销而设置的最大传递跳数.当在运行过程中为了适应负载的变化而动态地改变这些参数时即变为自适应的邻域契约策略(ACWN)[33]

.

Willebeek -Le Mair 等[6]对SID 、RID 、HBM 、DEM 和G M 五种DLB 策略进行了比较研究.其中,在Intel iPSC/2超立方体机器上,DEM 在各种粒度情况下的性能优于其它几种策略;DEM 和HBM 的有效性在很大程度上取决于拓扑结构;在处理器数目较大时,DEM 的同步开销、陈旧的状态信息以及HBM 的非均匀开销分布降低了它们各自的性能;与DEM 及HBM 相比,RID 能够保持任务间的通讯局部性,更易于移植到更简单的拓扑上和扩展到更大的系统上,适合更广泛的系统和各种类型的应用,可扩展性高.

Blumofe [34]

给出一个随机work -stealing 调度算法,证明该算法的期望计算时间为T 1/n +O(T ]),空间复杂度为O(nS 1),期望的总通讯复杂度至多为O (n T ](1+n d )S ma x ).其中,T ]表示处理器数为无限大时的最小执行时间,S max 表示任何线程的最大记录大小,n d 表示任何线程与父线程同步的最大次数.

表1和表2对上述各种策略的主要性能和特点做了总结.其中,表1给出了各种策略性能的理论分析,表2补充了对这些策略应用现状的说明.此外,表3和表4

给出了各种策略性能的实验分析与比较结果.

4.2.2 集中式策略 在集中式策略中,每个处理器的计算负载和通讯发送到一个指定的处理器,该处理器负责收集、处理全局的负载信息,并做出全局的负载均衡决策.文献[3]给出了几种代表性的集中式策略.其中,RandCentLB 为每个负载随机选择一个处理器,完成随机的负载均衡.当任务数m 很大并且通讯开销较小时,该策略可获得一个合理的结果.GreedyLB 将未分配的最大负载分配给当前负载最小的处理器,不考虑通讯开销.GreedyComm 将通讯开销考虑进去,在分配最大负载时,它不仅考虑负载最轻的处理器,同时也考虑该处理器的通讯开销,以寻求一个有益的选择.

RefineLB 通过精细调整现有负载分布来改进负载的分布,在调整过程中设置一个超载阈值,任何处理器的负载超过该阈值后将被视为超载.由于只考虑超载的处理器,该算法的计算和通讯开销较低.如果动态负载重均衡过程中对大量的负载进行重新分配将会在处

理器间产生很大的通讯和数据迁移开销.Agar wal [37]

提出并实现了一个启发式的Re fineKLB 策略,考虑了计算机的背景负载,度量指标为负载最多的计算机上的总负载量,运行时间复杂度为O (m log m).m 为任务数量,于K 值(可迁移对象的最大值).Refine CommLB 类似于Refine LB,但它考虑了点到点和集合通讯产生的开销.

对上述策略的理论分析与比较、应用性的总结分析、性能实验分析与比较结果分别如表1、表2、表3和表4所示.

表1 各种DLB 策略性能的理论分析与比较

1125

第 5 期杨际祥:并行与分布式计算动态负载均衡策略综述

策略类别策略实现难度对使用者要求应用情况主要特点评述策略定位

分布式

SID/RID[6]中中好适用性广,可扩展性高通用策略

D EM[6,20]较低较高应用少拓扑相关,适用性变广,应用难度增大基本策略

G M[6,21]中较高应用少规模增大,应用难度增大通用策略

GDA[8]较高较高应用少异构系统中扩散法的一般化理论分析通用策略SBN-based[28]较高高应用少规模增大,应用难度明显增大通用策略CWA[32]中高应用少拓扑相关,规模增大,应用难度明显增大基本策略ACWN[33]较高较低较好适用性广,可扩展性和性能较高通用策略work-s tealing[34]中较低最好简单性和效率间的较好折中通用策略DASUD[35]较高中应用少可得到一个较好的均衡度,但速度可能较慢通用策略

集中式RandCent LB[3]低中应用少可能得到一个合理的结果,但不确定通用策略GreedyLB[3]低低好设计思路简单,易于理解和实现通用策略GreedyComm[3]中较高应用少可得到一个较好的均衡度,但速度较慢通用策略RefineK LB[3,37]中较高应用少规模增大,应用难度增大通用策略

混合/层次结构HybridLB[3]较高高应用少多种策略(集中式和分布式)的组合混合策略HBM[6]中较高应用少规模增大,应用难度增大基本策略

表3各种DLB策略之间的性能实验分析与比较

比较策略

实验环境与比较条件

机器拓扑求解问题或计算任务性能影响参数选择性能比较指标

比较结果

SID/RID/HBM/DEM/ GM[6]Intel iPSC/2超立方体(1)人工随机生成计算任务;(2)

分枝限界作业调度问题

(1)任务粒度;(2)处

理器与问题规模

(1)加速比见4.2.1节内容

Refi neKLB/GreedyLB/ GreedyComm[3]BigSim模拟器2-D mesh(1)lb-test程序生成计算任务对

象

(1)问题规模;(2)处

理器规模

(1)并行执行时间见表4序¹

HB M/HybridLB[3]BigSim模拟器2-D mesh(1)lb-test程序生成计算任务对

象

(1)问题规模(1)通讯开销见表4序º

CWA/DEM[32]超立方体(1)随机生成计算任务负载,任

务数均值为特定值(1)处理器规模;(2)

每处理器平均任务数

(1)负载均衡度;

(2)通讯开销

见表4序»

ACWN/G M[38]Intel iPSC/2超立方体(1)10-Queen;(2)Fibonacci;(3)15-

Puz zle/IDA*;(4)Romberg Integra-

tion (1)处理器规模(1)处理器空闲时

间;(2)并行执行时

间;(3)并行效率

见表4序¼

DASUD/SID[39]ring,torus,超立方体(仿

真)两种分布的任务负载:(1)相似

(likely)分布;(2)病理分布

(1)处理器规模;(2)

拓扑结构;(3)负载分

布

(1)负载均衡度;

(2)负载迁移时间;

(3)均衡迭代步

见表4序½

SBN-based/GM/ ACWN[40]SGI Ori gin-2000超立方

体

(1)按泊松分布仿真生成相互独

立的任务负载

(1)处理器规模;(2)

系统负载

(1)每处理器消息

量;(2)任务迁移总

量;(3)空闲时间最

大方差;(4)完成时

间

见表4序¾

DEM/扩散法[41]torus,mesh(1)仿真生成静态随机任务;(2)

仿真动态产生/消耗随机任务(1)单/全端口通讯模

式;(2)拓扑节点规

模;(3)均衡步;(4)同

/异步

(1)全局均衡通讯

步;(2)系统失衡因

子变化

见表4序¿

表4各种DLB策略的性能实验比较结果序号比较结果描述

¹(1)在规模为32K和K的模拟处理器上,计算不同规模(128K~1m)的任务对象,GreedyLB策略执行时间最快,可扩展性高;(2)不考虑通讯的策略通常远快于考虑通讯的策略(如GreedyComm);(3)在规模为K的模拟处理器上,当计算规模超过256K时(如512K、1m),RefineKLB策略存在计算瓶颈,可扩展性低.

º(1)在规模为K的模拟处理器上,计算不同大小规模(256K~1m)的任务对象,HybridLB策略在优化通讯(降低通讯开销)方面优于HBM策略.

»(1)CWA可获得比DEM更好的负载均衡度;(2)DEM会产生不必要的任务迁移,而CWA能够最大化局部性,其通讯和负载均衡开销低于DEM.

(转续表) 1126电子学报2010年(表4续)

序号比较结果描述

¼在不同规模(2~32)的处理器上求解给出的4个问题:(1)ACWN的并行执行时间与并行效率优于GM策略;(2)使用ACWN策略的处理器空闲时间远低于G M策略.

½对于各种拓扑和分布,在不同规模(8~128)的处理器上:(1)DASUD的最大负载差和标准差远小于SID,具有较好的均衡度;(2)D A-SUD的负载迁移时间开销大于SID,这是因为DASUD扩展自SID策略,为了提高均衡度,需要检测非均衡域并执行额外的负载迁移,从而引入了额外的时间开销;(3)与SID比较,DASUD提供了全局均衡度和达到该均衡度所需迭代步数两者之间的一个较好折中.

¾在不同规模(2~32)的处理器上:(1)GM产生的消息量大于其它策略.SBN-based在重载系统中产生的平均消息量小于ACWN,但在轻载系统中却大于ACWN;(2)在重载系统中,SNB-bas ed的平均任务迁移总量大于G M,小于ACWN,但在轻载系统中却大于其它两种策略,且ACWN最小;(3)在各种负载系统中,SBN-based的处理器空闲时间最大方差小于其它两种策略,ACWN具有最大方差;(4) ACWN的平均完成时间最慢,SBN-based在轻载系统中的平均完成时间最快,而在重载系统中稍慢于G M,但快于ACWN.

¿(1)在单端口通讯模式下,D EM优于扩散法;(2)扩散法的长处在于全端口通讯模式下的异步实现.

4.2.3混合/层次策略为了最小化负载均衡开销,一些负载均衡方法重在研究如何根据层次拓扑结构来构建一个层次树的问题.HBM[6]利用层次树进行多级负载均衡,根据层次化的网络结构将处理器划分为多个组(均衡域),由这些均衡域组织成一个层次结构.在层次结构中的每一层,相邻的域间进行负载均衡,并且从底层至上层,在每层执行相同的域间负载均衡过程,最后在根节点完成全局的负载均衡.

混合策略(HybridLB)[3]类似于传统的层次负载均衡策略,将处理器划分为多个的、自治的组,并将这些组按层次结构进行组织.每层中的每个子树的根节点与其所有子节点形成一个负载均衡组,根节点充当该均衡组的头节点,控制负载均衡组内的负载均衡过程,充当类似集中式策略节点的功能.第i层的根处理器参与由第i+1层(层的序号由底至上递增)的头节点控制的负载均衡过程,但第i层各节点的子节点不参与第i+1层的负载均衡过程.与HBM不同的是, HybridLB可在不同的层采用不同的策略,并最小化任务传输的距离和数量以优化负载均衡的通讯开销.

上述策略之间以及与其它策略之间的性能分析与比较,可参考表1~表4中的相关内容.

4.2.4DLB策略小结现有的各种DLB策略通常在拓扑结构、问题特征、性能比较指标和性能影响参数选择等方面做了不同的假设,对这些策略进行比较研究不是一个简单的问题,直接比较其性能优劣需要很好地实现各种算法.然而,开发有效的软件或很好地实现算法从并行机器中获得计算性能是一个挑战性的工作[3].

本节从理论、应用性和实验三方面对各种DLB策略进行小结:(1)对这些策略的理论分析重在策略算法本身以及拓扑结构上,且一般假设系统是同构的.表1给出了各种典型DLB策略性能的理论分析与比较;(2)策略本身的复杂度、实现难度和使用要求影响其应用性.表2对现有DLB策略的应用性作了分类总结与比较;(3)在实验中,大都简单地假设系统为同构的,且基于不同的问题和性能指标,难以真正比较出它们孰优孰劣.例如,表4序¼和序¾中,在不同条件下对ACWN 和GM的性能比较中就得出了不同的结论.

5DLB策略有效性分析

5.1信息陈旧性的影响

网络传输延迟和信息量影响信息的陈旧性和精确性.集中式策略的中心节点收集全局负载信息用于决策过程,信息在中心节点的积聚对同步的要求将产生开销与延迟,致使中心节点的处理与通讯速度变慢并成为瓶颈[3].当延迟增大至某点时,信息陈旧性增大,可能导致错误的决策[2].分布式策略仅使用局部(k个相邻处理器)的负载状态信息进行决策,其信息有效性受到k和更新因子u的影响[6].信息的不精确性使得均衡器很难做出一个最优的负载均衡决策,尤其是在快速变化的环境中甚至会做出错误的决策,导致某些任务在多个处理器间来回传递,增加了额外开销,降低了DLB策略的有效性[3].

5.2拓扑结构的影响

Loh等[42]通过实验说明,处理器间的平均距离$a vg 较大和平均节点度(

av g

较小时的负载均衡开销较大. Willebeek-LeMair等[6]研究了拓扑结构对DLB策略有效性的影响,其中GM的信息精确性受网络拓扑直径的影响,网络拓扑直径影响着信息的有效性[3,37].SID和RI D 的信息有效性受网络拓扑中每个节点的相邻处理器数k的影响,而HBM的信息有效性则受网络拓扑节点数N和信息更新频率u的影响.当网络直径或$av g以及k 相对较小时,应该减少负载状态更新的次数.拓扑结构已成为分析DLB策略有效性的一个重要因素[3,6,37]. 5.3负载分布的影响

Taylor等[43]考虑了计算问题和系统的特点,在3种系统上计算有限元问题,结果表明,一定的负载失衡能够降低并行执行时间,且当用于求解一个固定规模问题的处理器数越多时,较大的负载失衡是有益的.Huang

1127

第5期杨际祥:并行与分布式计算动态负载均衡策略综述

等[44]研究表明,为了获得异构环境下的最小并行执行时间,根据计算机的平均计算能力按比例地分配任务不能获得最优解,而综合考虑每个处理器可用计算能力和平均计算能力的标准偏差的负载分布可减少总执行时间.Z heng[3]通过实验研究说明,通讯延迟和负载失衡导致CPU利用率的不确定性,CPU的平均利用率低;考虑了计算节点的背景负载,在负载均衡阶段之后对部分负载进行精细化调整,可提高综合的CP U利用率和负载均衡的质量.

6总结与展望

尽管近30年对D LB技术的理论研究已取得了较大的进展,并获得了一定的应用,但不同策略的性能受硬件特征、处理器数目和问题规模变化的影响而有很大的差别[36].表1~表4对DLB策略性能的理论和实验分析以及比较结果也很好地说明了这点.体系结构或机器拓扑结构与应用驱动着DLB技术的研究与发展[5,36,37,42,43,45].

并行计算性能的增长在未来至少5年的发展时间里将肯定来自于使用多核处理器技术的发展[46],系统趋向于由多核组成,多核以层次方式构成集群[45,47].并且,具有数百或数千个核的众核(Many-Core)将为面向千万亿次的高性能/超级计算提供计算潜力[48,49],未来的高性能/超级计算、商用/企业计算(核数多达或80)最终将通过多核实现它们的目标.传统的DLB策略已不能充分利用多核多线程的高度的细粒度并行性、多核存储器和多核集群的层次结构特征[45,47,50],甚至需要重新设计应用程序、库以及算法[49].因此,客观地讲,一些非常有意义的问题还有待被探讨和解决.总结归类这些问题,包括两方面的研究:(1)体系结构驱动:算法只有考虑到体系结构特征时才能达到最优的性能[46,47],面向多/众核体系结构的新型算法将成为发挥高性能的主要方向.图2给出了典型多核集群的层次结构特征,其中节点内的片间通讯速度慢于片内通讯速度,但远快于节点间的通讯速度,在节点内需要考虑存储器层次结构的访问局部性和同步问题[50,51];(2)应用驱动:多核带来了硬件并行性的爆炸性增长[49],如何在一个高性能/超级计算机中有效利用整个系统中更多的并行性来计算一个更大规模的科学或工程应用问题[4,6]是并行计算面临的一个挑战问题;另一方面,需要研究可移植性高和支持更多应用计算(商用/企业/通用计算等)的高产能算法策略,提高整个系统的吞吐量和利用率.因此,如图3所示,可从三个层面来展开具体的研究:(1)系统;(2)节点组;(3)节点.表5详细地阐述了每个层面所含研究问题的意义所在.

本文对近30年的DLB策略相关研究进行了综述,希望起到抛砖引玉的作用.随着新兴的多/众核相关技术和应用的出现以及进一步发展,DLB技术的重要性也日益凸显,如何通过D LB技术来提高求解科学和工程领域问题的计算效率和计算规模仍将是今后并行计算研究中的一个挑战问题.

表5对未来DLB策略研究问题的分析层次研究问题研究意义

系统拓扑相关

的均衡策

略

互连拓扑(直径较大)成为影响优化应用性能的关键,通过考虑拓扑结构来优化通讯可提高D LB策略的性能[3,37,42,43,52].结合应用问题特征,研究如何将任务映射到互连拓扑上以确保:(1)节点(组)间的负载均衡;(2)相互通讯的任务,尤其是参与多播或集合操作等通讯密集的任务被划分到同一节点或节点组内.

节点组优化通讯

开销

Chai等[47]研究指出,多核集群中通过节点内通讯的消息平均约占50%,表明对节点内和节点间/组两种通讯的优化同等重要.考虑到节点内的通讯速度远快于节点间通讯的事实[52],研究如何将更多的节点间通讯密集的任务划分到同一节点内可进一步优化通讯性能.

节点细粒度划

分与数据

依赖性对

性能的影

响

任务粒度是影响多核多线程调度性能的一个关键因素[53],多核存储结构和众核[48,50]要求对数据或任务进行细粒度划分来获得并行性并最大化数据可重用性[54,55].然而,细粒度的划分同时可能会降低数据的局部性,同一数据集和数据依赖度高的数据或任务均衡分布到不同处理器核上相应地引入了较大的交互通讯和同步等待开销,且核间的负载动态调度将可能进一步增大这种开销.如何构造保持细粒度划分以增大并行性的同时保持数据的依赖性,以及研究两者对性能的影响变化关系,需要在实际应用中做进一步的深入研究.

可扩展/

可移植性

多核处理器体系结构正处于不断的发展与变化中[51],如能设计适应于统一多核计算模型和异构体系结构的负载均衡策略将有助于提高策略的计算性能、可扩展性和可移植性.

降低调度

开销

片内/片间的负载均衡调度常常会引入私有和共享资源的相互争用问题,为解决共享资源争用引入的同步等待是影响多核计算性能的一个重要因素[51].在解决实际问题中,如何在负载的均衡度和同步开销之间进行折中考虑以提高整体的计算性能尚需进一步研究.

保持数据

局部性和

依赖性

数据局部性或数据依赖性越来越被证明是影响多核并行计算性能的重要因素[50,51,54,55],节点内的片内/间的动态负载均衡调度往往会破坏数据局部性或依赖性,降低Cache访问局部性,增大了同步开销.因此,为最大化性能,须将数据局部性和依赖性信息整合到调度策略中.

有效的处

理器数

当为提高并行性引入的同步开销代价大于收益以及计算具有较大粒度并行性和依赖度的问题时,使用更多的核得不偿失,使用节点的多少个处理器核解此类问题是最有效的?

1128电子学报2010年参考文献:

[1]X J Yang,et al.Progress and challenges in high performance

computer techno logy[J].J Comput Sci&Techno l,2006,21

(5):674-681.

[2]蒋江,张民选,等.基于多种资源的负载均衡算法的研究

[J].电子学报,2002,30(8):1148-1152.

J Jiang,M X Zhang,et al.Study on load balancing algorithms based on multiple res o u rces[J].Acta Electronica Sinica,2002, 30(8):1148-1152.(in Chinese)

[3]G B Zheng.Achieving High Performance on Extremely Large

Parallel M achines:Performance Prediction and Load Balancing

[D].Urbana:UIU C,2005.

[4]O Yasar.Trends in parallel computing[J].Parallel Comput,

2007,33(2):81-82.

[5]K D Dev i ne,et al.New challenges in dynamic load balancing

[J].Appl Numer Math,2005,52(2-3):133-152.

[6]M H Willebeek-LeMair,et al.Strategies for dynamic load ba-l

ancing on highly parallel computers[J].IEEE T Parall Distrib, 1993,4(9):979-993.

[7]A Heirich.Analysis of Scalable Algorithms for Dynamic Load

Balanci ng and Mapping w ith Application to Photo-realistic Rendering[D].Pasadena:Caltech,1998.

[8]T Rotaru,et al.Dynamic load balancing by diffusion in hetero-

geneous systems[J].J Par Dis tr Comp,2004,(4):481-497.

[9]G M Amdahl.V alidity of the single processor approach to

achiev i ng large scale computer capabilities[A].In Proc.

AFIPS.67[C].New Jersey:AFIPS Press,1967.483-485. [10]J L Gus tafson,et al.Development of parallel methods for a

1024-pro cessor hypercu be[J].SIAM J Sci Stat Comp,1988,9

(4):609-638.

[11]X H Sun,et al.Scalable problems and memory-bounded

speedup[J].J Par Dis tr Comp,1993,19(1):27-37. [12]A Grama,et al.Isoefficiency function:a scalabili ty metric for

parallel algorithms and architectures[J].IEEE Par D ist T ech, 1993,1(3):12-21.

[13]X H Sun,et al.Scalability of parallel algorithm-machine com-

binations[J].IEEE T Parall Distrib,1994,5(6):599-613. [14]K Hwang,et al.Scalable Parallel Computing:Technology,Ar-

chitecture,Programming[M].Hights town,New Jersey:WCB/ M cGraw-Hill,1998.

[15]Y T Wang,et al.L oad sharing in distributed sy s tem[J].IEEE

Trans Comput,1985,34(3):204-217.

[16]T L Cas avant,et al.A taxonomy of scheduling in genera-l pur-

pose distributed computing systems[J].IEEE T Soft Eng, 1988,14(2):141-154.

[17]K M Baumgartner,et al.A global load balancing s trategy for a

dis tribu ted computer system[A].In Proc.Futu re Trends of Dis t Comp Syst[C].Los Alamito s:IEEE CS Press,1988.93-102.

[18]J Xu,et al.Heuris tic methods for dynamic load balancing in a

message-passing multicomputer[J].J Par Dis tr Comp,1993, 18(1):1-13.

[19]C Z X u,et al.Iterative dynamic load balancing in multicom-

puter s[J].J Oper Res,1994,45(7):786-796.

[20]G Cybenko.D ynamic load balancing for distributed memory

multiprocessors[J].J Par Dis tr Comp,19,7(2):279-301.

[21]F C H Lin,et al.The gradient model load balancing method

[J].IEEE T Soft Eng,1987,13(1):32-38.

[22]J Song.A partially asynchronous and iterative algorithm for

dis tributed load balancing[J].Parallel Compu t,1993,20(6):

358-362.

[23]R D iekmann,et al.Efficient schemes for neares t neighbor load

balancing[J].Parallel Comput,1999,25(7):7-812. [24]R Els¾sser,et al.D iffusion schemes for load balancing on het-

ero geneous netw orks[J].Theor C Sys,2002,35(3):305-

320.

[25]C C Hui,et al.Hydrodynamic load balanci ng[J].IEEE T Par-

all D istrib,1999,10(11):1118-1137.

[26]J Watts,et al.A practical approach to dynamic load balanci ng

[J].IEEE T Parall Distrib,1998,9(3):235-248.

[27]J M Bahi,et al.Dynamic load balancing and efficient load es-

timators for asynchronous iterative algorithms[J].IEEE T Par-all Dis trib,2005,16(4):2-299.

[28]S K Das,et al.Parallel pro cessing of adaptive meshes with

load balancing[J].IEEE T Parall D istrib,2001,12(12):1269 -1280.

1129

第5期杨际祥:并行与分布式计算动态负载均衡策略综述

[29]L Oliker,et al.PLUM:parallel load balanci ng for adaptive u n-

structured meshes[J].J Par D istr Comp,1998,52(2):150-

177.

[30]C Z X u,et al.T he generalized dimension exchange method for

load balancing in k-ary n-cubes and variants[J].J Par Distr Comp,1994,24(1):72-85.

[31]H Rim,et al.A simple reduction of non-uniformi ty in dynamic

load balancing of quantized loads on hypercube mult-i proces-sors and hiding balancing overheads[J].J Compu t Sy Sci, 2003,67(1):1-25.

[32]M Y Wu.On runtime parallel scheduling for pro cessor load

balancing[J].IEEE T Parall Distrib,1997,8(2):173-186.

[33]W W Shu,et al.A dynamic scheduling strategy for the Chare-

Kernel system[A].In Proc.ACM/IEEE Supercomputing.

[C].New York:ACM Press,19.3-398.

[34]R D Blu mofe,et al.Scheduling mult-i threaded computations

by work stealing[J].J ACM,1999,46(5):720-748. [35]A Cort s,et al.An asynchrono us and iterative load balancing

algorithm for discrete load model[J].J Par Distr Comp,2002, 62(12):1729-1746.

[36]V Kumar,et al.Scalable load balancing techniques for parallel

computers[J].J Par Distr Comp,1994,22(1):60-79. [37]T A garwal.Strategies for Topology-aware Task Mapping and

for Rebalancing with Bounded Migrations[D].Urbana: UIUC,2005.

[38]W Shu.Adaptive dynamic process scheduling on dis tributed

memory parallel computers[J].Sci Prog,1994,3(4):341-

352.

[39]A Cort s,et al.Performance comparis on of dynamic lo ad-ba-l

ancing strategies for dis tributed computing[A].In Proc.32nd IEEE HICSS[C].Washington:IEEE CS Press,1999.1-10.

[40]S K Das,et al.Adaptive load-balancing algori thms using sym-

metric broadcas t networks[J].J Par D istr Comp,2002,62

(6):1042-1068.

[41]C Z Xu,et al.An analytical comparison of nearest neighbor

algorithms for load balancing in parallel computers[A].In Proc.9th IEEE ISPP[C].Washington:IEEE CS Press,1995.

472-479.

[42]P K K Loh,et al.How network topology affects dynamic load

balancing[J].IEEE Par D ist Tech,1996,4(3):25-35. [43]V E Taylor,et al.Balancing load versus decreasing commun-i

cation:parameterizing the tradeoff[J].J Par Dis tr Comp, 2001,61(5):567-580.

[44]J Huang,et al.A heterogeneity-aware approach to load ba-l

ancing of computational tas ks:a theoretical and simulation s tudy[J].Cluster Computing,2008,11(2):133-149. [45]X F Wu,et al.Performance analysis and optimization of para-l

lel scientific applications on CMP clusters[J].Scalable Com-puting:Practice and Experience,2009,10(1):61-74.[46]J L Hennessy,D A Patterson.Computer Architectu re:A Quan-

titative Approach[M].San Francisco:Morgan Kaufmann, 2007.

[47]L Chai,et al.U nder s tanding the impact of mult-i core architec-

ture in cluster computing:a case study with Intel dua-l core system[A].In Proc.7th IEEE CCGRID[C].Washington: IEEE CS Press,2007.471-478.

[48]K Asanovic,et al.The Landscape of Parallel Computing Re-

search:A V iew from Berkeley[R].Berkeley:U CB,2006. [49]NERSC.2006NERSC Annual Report[R].Berkeley:NERSC,

2007.

[50]J E Savage,et al.A unified model for multicore architectures

[A].In Proc.1st ACM IFMT(AICPS.08)[C].New York:

ACM Press,2008.1-12.

[51]P TrÊger.The M ult-i Core Era-Trends and Challenges[R].

Karls krona,Sweden:Blekinge Institute of Techno logy,2008.

[52]A Bhatel ,et al.Dynamic topolo gy aware load balancing algo-

rithms for molecular dynamics applications[A].In Proc.23rd ACM ICS[C].New Y ork:ACM Press,2009.110-116. [53]S Chen,et al.Scheduling threads for cons tructive cache s har-

ing on CMPs[A].In Proc.19th ACM SPAA[C].New York: ACM Press,2007.105-115.

[54]G T an,et al.Impro ving performance of dynamic programming

via parallelis m and locality on multicore architectures[J].

IEEE T Parall Distrib,2009,20(2):261-274.

[55]A Buttari,et al.A class of parallel tiled linear algebra algo-

rithms for multicore architectures[J].Parallel Compu t,2009, 35(1):38-53.

作者简介:

杨际祥男,1975年生,博士研究生.研究

方向为集群计算与多核计算.

E-mail:jixiang-yang@126.com

谭国真男,1960年生,教授,博士生导师.

研究方向为集群计算、网络优化、智能交通系统

与无线传感器网络.

E-mail:gz tan@dlut.edu.cn

王荣生男,1960年生,副教授.研究方向为计算机网络及其应用.

1130电子学报2010年