（计算机软件与理论专业论文）异构系统负载平衡扩散算法的度优先加速法.pdf

巾1 1 1 人学硕士论文芹构系统负载平衡扩敞算法的度优先加速法 异构系统负载平衡扩散算法的度优先加速法 计算机软件与理论 硕士生：方智 指导教师：张治国副教授 摘要 机群是由许多独立自治的处理机连接在一起组成的高并发分布式系统i l 2 i 。随着 分布式计算技术的普及，机群上开展的科学计算越来越多。负载均衡是提高机群性 能的一个重要问题。金之雁提出了基于水连通器势能最低原理的异构系统扩散算法， 该方法用连通器中水的流动来类比负载的移动，还应用水的位能在平衡时最低的原 理来计算负载的移动。在负载均衡执行过程中，系统各节点间进行的负载交换次数 的多少代表着负载均衡算法执行的效率，即算法收敛速度的大小。 本文研究了异构系统中负载均衡的扩散算法，并重点研究了系统中速度不同的 处理机的位置与连接图节点的性质之间的关系对算法收敛速度的影响。提出了加速 扩散算法的收敛速度的度优先速度分配加速法。该算法根据连通图中节点的图的性 质来调节系统中不同速度的机器在连接图中的位置，以达到加快扩散算法收敛速度 的目的。 初步实验证明，度优先加速法能够合理安排处理机位置，从而加快扩散算法的 收敛，提高负载均衡的效率。该方法比较穷举遍历法和依次插入法，计算量小，求 解速度快。同时，它是一种直观的方法，在实际的工程中，能够依据该算法的优先 准则方便的安排处理机位置。 关键词：并行计算，异构系统，动态负载均衡，扩散算法，收敛速度，处理机安 排，度优先 巾l | 1 人学硕士论文 异构系统负牧平衡扩敞算法的度优先加速法 a d e g r e ep r e f e r e n t i a lo p t i m a lm e t h o do fd i f f u s i o n a l g o r i t h mf o rh e t e r o g e n e o u ss y s t e m c o m p u t e rs o f l w a 鹏a n dt h e o r y n a m e ：f a n gz h i s u p e r v i s o r ：z h a n gz h i - g u o ( a s s o c i a t ep r o f e s s o r ) a b s t r a c t m u l t i c o m p u t e r s a r e h i g h l y c o n c u r r e n t s y s t e m st h a t a r ec o m p o s e do f m a n y a u t o n o m o u sp r o c e s s o r sc o n n e c t e db yac o m m u n i c a t i o nn e t w o r k 睇l d y n a m i cl o a d b a l a n c i n gi nm u l t i c o m p u t e r sc a ni m p m v et h eu t i l i z a t i o no fp r o c e s s o r sa n dt h ee f f i c i e n c y o f p a r a l l e lc o m p u t a t i o n st h r o u g hm i g r a t i n gw o r k l o a da c r o s sp r o c e s s o r sa tr u n t i m e d i f f u s i o na l g o r i t h mi sa d y n a m i cl o a db a l a n c i n gm e t h o df o rh o m o g e n e o u ss y s t e m i n t h i sa p p r o a c h 。e a c hp r o c e s s o ri sv i e w e d 酏al i q u i dc y l i n d e rw h e r et h ec r o s s s e c t i o n a la r e a c o r r e s p o n d st ot h ec a p a c i t yo ft h ep r o c e s s o r , t h ec o m m u n i c a t i o nl i n k sa l em o d e l e da s l i q u i dc h a n n e l sb e t w e e nt h ec y l i n d e r s ，t h ew o r k l o a di sr e p r e s e n t e db yl i q u i d ，a n dt h el o a d b a l a n c i n ga l g o r i t h mm a n a g e st h ef l o wo ft h el i q u i d a n dt h ea l g o r i t h mi m p l e m e n t a t i o n e f f i c i e n c y , v i z t h es p e e do ft h ea l g o r i t h mc o n v e r g e n c er a t e ，c a nb ee v a l u a t e db ya m o u n t s o fw o r k l o a de x c h a n g i n ga m o n g p r o c e s s o r s i nt h i st h e s i s ，d i f f u s i o na l g o r i t h ma n de s p e c i a l l yt h ei n f l u e n c eo ft h ea r r a n g e m e n to f d i f f e r e n tp r o c e s s o r si nt h es y s t e mo nt h ec o n v e r g e n c er a t eo ft h ea l g o r i t h mi ss t u d i e d ，a n d ad e g r e ep r e f e r e n t i a lo p t i m a lm e t h o di sp r o p o s e dt oi m p r o v et h ec o n v e r g e n c er a t e i nt h i s a p p r o a c h ，p r o c e s s o r si nar e a ln e t w o r ka r er e a r r a n g e da c c o r d i n gt of o u rr u l e sa s s o c i a t e d w i t ht h ec o n n e c t i v ec h a r a c t e ro fn o d e si na na n a l o g i cg e o m e t r i c a l g r a p h p r i m a r yr e s u l ts h o w st h a tt h ed e g r e ep r e f e r e n t i a lo p t i m a lm e t h o dc a nf i n dab e t t e r a r r a n g e m e n to ft h ep r o c e s s o r st oa c c e l e r a t et h ed i f f u s i o na l g o r i t h m a n di nc o m p a r i s o n w i t ho t h e ro p t i m a lm e t h o d s ，i tc a l c u l a t e sf e w e ra n dt a k e sf e w e rt i m e ，m o r e o v e ri ti sa v i s u a lm e t h o ds ot h a ti tc a nb eu s e di na na c t u a lc o n s t r u c t i o nc o n v e n i e n t l y i i 巾i | j 人学硕十论文 芹构系统负载平衡扩敞算法的度优先加速法 k e yw o r d s ：p a r a l l e lc o m p u t i n g ，h e t e r o g e n e o u ss y s t e m ，d y n a m i cl o a db a l a n c i n g ， d i f f u s i o na l g o r i t h m ，c o n v e r g e n c er a t e ，a r r a n g e m e n to fp r o c e s s o r s ，d e g r e ep r e f e r e n t i a l i i i 巾1 1 1 人学硕十论文异构系统负城平衡扩敞算法的度优先加速法 第1 章综述 1 1 引言 机群是由许多独立自治的处理机连接在起组成的高并发分布式系统【1 , 2 1 。随着 分布式计算技术的普及，机群上开展的科学计算越来越多。如果并行系统的所有节 点完全相同，这种系统称为同构的，反之称为异构的。异构并行系统在工作站网络 环境中是很常见的。 目前，还没有非常有效的予段和机制左克服系统中由于分布而引起的种种问题。 比如：某一时刻，一些节点的负载极重，而另一些节点的负载却很轻，各个工作站 的负载极不平衡。因此，对各个异构工作站进行负载均衡也就成为任务分配与调度 的一个主要目标，它能够提高整个系统的性能，在不影响工作站的情况下，减少并 行计算时间。如何采取有效的调度策略来平衡各节点的负载从而提高整个系统资 源的利用率，也就成为人们研究的热点。已有研究表明，在机群系统中采用负载均 衡系统可以显著地提高机群系统的性能l ”。 1 1 1 动态负载均衡策略 负载均衡是机群系统中的重要技术，它通过在由高速网络迮接起来的各个节点 问平衡系统负载来提高集群系统的性能。负载均衡可以分为动态与静态两种h i ，如 果在运行之前可以预知系统的计算负载分布情况，负载的划分是静态负载均衡问题。 反之，需要在运行时监测负载情况并根据监测信息动态调整负载的划分，是动态负 载均衡问题。 实现动态负载均衡的方法很多，一类方法是采用一个节点监视整个系统的负载 状况，并控制整个系统的负载分配，这种方法称为直接方法。它的优点是简单、直 叶1 1 1 1 人学硕十论文异构系统负载平衡扩敞算法的度优先加速法 观，适用于采用广播机制或者集中监控的系统1 5 - 8 1 。另一类方法是迭代方法( i t e r a t i v e a p p r o a c h ) p l 。在这种方法中，每个节点只能与其直接连接的节点通信，计算负载只 能通过这些节点问的连接移动。在负载均衡过程中，每个节点只能与其周围的节点 进行负载交换，通过多次循环迭代实现系统的负载均衡。采用这种模式的负载均衡 算法有：扩散方法( d i f f i l s i o nm e t h o d ) i ”i 、维交换法( d i m e n s i o ne x c h a n g em e t h o d ) i 1 1 l 和 基于梯度的方法( g r a d i e n tb a s e dm e t h o d ) 等。在维交换法中，每个节点在一个时间内 只与它的一个相邻的节点进行负载平衡。基于梯度的方法有多种，其共同特点是用 负载梯度图来描述整个系统得负载情况，负载是向着梯度最陡方向的节点移动的。 其中，梯度模式方法( g m d i e n tm o d e lm e t h o d ) 1 1 2 j 用计算负载压力面来表示负载的移 动。在扩散算法中，每一次迭代中，每个节点向它周围计算负载较低的节点送出计 算负载，同时从计算负载高的节点接受计算负载。c h i c h u n gh u i i ”1 提出了针对异构 系统的流体负载平衡( h y d r o d y n a m i cl o a db a l a n c i n g ) 方法。该方法用连通器中水的流 动来类比负载的移动，还应用水的位能在平衡时最低的原理来计算负载的移动。j i n z h i - y a n 在流体负载平衡的基础上，提出了基于流体负载均衡( h y d r o d y n a m i cl o a d b a l a 眦i n g ) 的负载均衡扩散算法1 1 4 1 ( 以下简称扩散算法) 。 动态负载均衡 迭代法 直接法 随机迭代 l 扩散法维交换法梯度模型法随机分配法模拟退火法 图1 - 1 动态负载均衡策略的分类 2 巾1 1 1 人学硕十论文异构系统负载平衡扩散算法的度优先加速法 1 1 2扩散法的收敛速度 1 ) 收敛速度 当采用迭代法进行负载均衡时，如果在若干步迭代之后，能够达到负载均衡， 称负载均衡过程收敛。反之，如果在无数步迭代之后，不能够使得负载均衡，称负 载均衡过程不收敛。负载均衡的收敛速度是衡量负载均衡效率的一个重要标识。 在迭代法进行负载均衡过程中，总共进行的迭代次数代表着负载均衡速度。迭 代次数越多，最终达到负载均衡的时问越长；迭代次数越少，最终达到负载均衡的 时间越短，负载均衡速度越快。因此，研究减少迭代次数的方法，对提高负载均衡 的效率有着重要意义。 2 ) 扩散算法的收敛速度 针对异构系统，j i nz h i y a h 提出了基于流体负载均衡1 1 3 l ( h y d r o d y n a m i cl o a d b a l 卸c i n g ) 的负载均衡扩散算法【1 4 i ( 以下简称扩散算法) 。该方法用连通器中水的流动 来计算负载的移动，还应用水的位能在平衡时最低的原理计算负载的移动。其扩散 算法公式为： l f k + = 舰嘶= 舻+ i l t o ) ( 1 ) 其中，k 表示迭代次数：p 表示节点数：l ( k = ( ，l ，2 。，i p k ) 表示第k 次迭代 后，系统中各节点的计算时间；m 是扩散矩阵。 m = ，- f z 4 7 ， ( 2 ) 其中，为单位矩阵，r 为系数矩阵，s 。为速度矩阵，a 为邻接矩阵。 公式( 1 ) 的收敛性由扩散矩阵m 决定。由公式( 2 ) 可知，扩散矩阵m 丰要由系统 中的节点速度分布和节点连接方式即连接圈共同决定。因此该扩散法的收敛速度与 连接图的拓扑结构以及节点的速度排列紧密相关。 本文对异构系统中扩散算法进行分析，针对连接图已经确定的情况，研究系统 中节点速度的分布不同对扩散算法收敛速度的影响，以找出一种加快扩散算法的速 度的方法。 叶1 1 1 1 人学硕十论文异构系统负载平衡扩敞算法的度优先加速法 1 2 本文的解决方案 根据公式( 1 ) ，加快扩散算法收敛速度的方法是要找到符合条件的扩散矩阵。即 网络拓扑结构和速度分布情况。这一过程实际上是特征值问题的反问题，要求特征 值满足一定的要求，求矩阵的问题，这类问题一般来讲是比较困难的【”i 。事实上， 我们没有必要求出收敛达到晟快时的最佳安排，只需找出一种比较接近的情况，能 够加快扩散的收敛速度即可。 根据扩散算法负载均衡公式，扩散算法的收敛速度由扩散矩阵m 直接决定，而 m 是由节点速度排列和网络拓扑结构决定的。本文研究了系统中各节点的度与速度 的关系对扩散算法收敛速度的影响，结合数值试验分析，提出一种按度优先来调整 节点位置以加快算法收敛的方法。最后，经过数值实验验证，该方法能够减少迭代 的次数，提高收敛速度。 1 3 相关研究和比较 ， 影响扩散算法的收敛速度的因素有两个，即连接图拓扑结构和速度分布。目前， 还没有对连接图拓扑结构方面的研究工作。调整速度分配加快收敛的方法丰要有两 种，即穷举遍历法和依次插入法1 1 ”。 穷举法即穷举所有可能的速度排列情况，从而找出最佳分布。这种方法只能在 节点数量比较少( n p ，式( 2 3 ) 的解不唯一，存在多个满足该式的解。 2 2 异构扩散算法模型 如图2 1 所示，用一组相- 可连接的水桶来建立异构扩散算法的模型。设有p 个 圆柱形容器其水平截面积各不相同，在容器底部有一些管道将容器连接起来，水 可以通过管道从一个容器中流到另一个容器，称为连通器。所有容器的底面都处在 同一个水平面上。如果水平面有高有低，水就会在容器问流动，直至所有容器的水 平面高度相同为止。假定该系统是连通的。在此模型中，水的体积与计算量相对应， 巾l | l 火学硕十论文 异构系统负载平衡扩散算法的度优先加速法 水桶的水位与节点的计算时间相对应，容器的横截面积与节点的处理速度相对应， 水桶之间的连接镎与节点之间的通信线路对应。如果计算时间( 水位) 不相同，一 些计算负载( 水) 会从通过处理节点间的通信连接( 能道) 从一个节点转移到另一 个节点。如果计算时间相等，整个系统达到负载均衡，计算负载不再移动。显然在 此模型中，铃道的粗细对实现整个系统的最终平衡没有影响。 图2 - 1 连通器模型 设节点“相邻，一个时间步内通过到达f 的流量正比于它们的水位差，设在 第t 次迭代时，节点i 的运算时间是，扩散算法的公式是： p ；n 考荟删l 其中， r 是非负的常量。此式表示每一步，节点i , j 之间交换的计算负载为： t 。i 啦! 一t n 引起的计算时间的变化为： 一舶 如果此量为正，表示计算量由j 转移到i ，如果为负，表示转移方向相反。由于 在扩散模型中，通信线路是双向的，因此r i j = r j i 。扩散公式可以改写为： l i t + 1 ) = ( 1 一妻洲。+ 丢驴 8 叶1 1 1 1 人学硕十论文异构系统负载平衡扩敞算法的度优先加述法 如果与节点i 相邻的节点在初始时刻的计算时间为零，在一个迭代步内，节点i 上的计算时间不能为负，所以对于常数r 。存在以下两个约束条件： h ，0 渺= 。 。q 若令l 似= ( t j ，f 2 ，”) 7 ，则扩散公式可以写成矩阵形式： l o + n = m l o ( 2 - 5 ) 其中，m = r 小口，为i v i 阶非对称方阵，其元素为： m ) 。 立，如果i 艰u 相邻 s i 0 ，其它 ( 2 - 6 ) l _ i s j 高r m 如果i = j 显然，对于其中的每一行元素都有m = 1 ，容易验证肼= ，s a z 4 7 ，其中i 为单位矩阵，r = d i a g ( t ht jb “：t l e i ) ，、a 为图g 的邻接矩阵，s = d i a g ( s _ f , s 6s b 。； 昂) 。则： 工“+ 封：m l ( 0 曲d t l = q s l a r a 。) l m ： d + n d 1 1 = s l ，蛆a 1l t t l = d n l lo ) = 譬l a 豇t ll i o ) = | 心“i p = s l a t a t u 0 1 + l u 、+ + d t 。1 1 l = b = 工m l 仰=s t a r 三上m( 若垲代过氍收敛，l m 是最终平衡计算时间) 因为b = s - t a x 令y “= 一t a t l m ，则方程( 2 - 3 ) 的解x = y 。以下证明该算法的收敛性。 2 3 扩散法的可收敛性 由扩散公式( 2 5 ) 可知，迭代的收敛性由扩散矩阵m 决定，即取决于m 的特征 值情况。如果存在绝对值大于i 的特征值，迭代过程( 2 - 5 ) 不收敛。可以证明m 9 巾j i i 大学硕十论文舁构系统负我平衡扩散算法的度优先加速法 的特征值绝对值均小于1 1 1 4 l 。 定理1 在式( 2 5 ) 中的迭代循环中。计算总量- = s ，”不变，即，= 彻， 黟 t = 五2 ，”： 证明：在该算法模型中，两点巧问从j 到i 的负载转移为r f ( f f - f f ) ，从i 到j 的 负载转移为r 以呦。因为7 = r j ，所以j ，j 两节点上的负载总量不变。同理，系 统内任意两节点问的负载转出与接收量相等。因此，系统内计算总量不变，负载只 是在系统内进行了重新分配。 定理2 在式( 2 6 ) 中的定义的扩散矩阵m 的特征值全为实数。 证明：设j 】l f = 沏) ，其中 m “= h如果i 和j 相邻 0 ， 其它 驴三h 如果i ；j 因为7 2r ，显然掣为实对称织吁，且m = s a m 。设m 的特征值为丸，对 应的特征向量为x ，则有： 丽f 。两矿 ：，而：i 万 ； x 7 $ 。m ) 7= x 7 ：) x r m t s - 1 ；2 x 7 ： x 7 m s 一1 m t x ：a x 7 m x ； x 1 m 膨y = a x l 肘x = 一= 皇 x 。m 九y 盎a x 。m j ； 九x t m x = 丸x t m x 因为x 7 肘x - 0 ，所以a = a ，即a 为实数。 定理3 在式( 2 6 ) 中的定义的扩散矩阵m ，其特征值的模小于等于1 。 证明：设m 的特征值九，对应的特征向量为x ，因为m x = 2 x ，对于其中的第i l o 巾l l l 大学硕士论文 异构系统负找平衡扩敞算法的度优先加速法 行有m ；x j 。杠，记特征向量是x 中的最大分量为 。埘m a 圳x i 工i ，所以； 县 ；- 争i 学h 凳m 。詈，s 黔睁i 釉= 由上式可知膨的特征值在闭区间 _ 1 ，1 内。当且仅当坼风= 1 ，且m k j o 时 等号才成立。即 一l 时，如x 2“= 而= c 特征向量为( c ，c c ) t 。表示任一节点 与其邻接节点间的负载转移进出量相等，即负载不再变化，已达到负载平衡。 定理4 在式( 2 田中的定义的图g 的扩散矩阵m ，且满足条件( 2 4 ) ，一1 不是m 特征值的充要条件是： ( i ) m 的主对角元素不全为o ； ( i i ) g 不是二部图。 定理5 在式( 2 6 ) 中的定义的图g 的扩散矩阵m ，且满足条件( 2 - 4 ) ，且m 的丰 对角元素不全为0 ，g 不是二部图则迭代过程( 2 - s ) 收敛于均匀解。 定理4 ，5 的证明过程请参见0 i 文 1 4 1 。 2 4 扩散算法的并行程序设计 2 4 1 前提条件 在开始设计算法之前，我们首先明确三个前提条件。 一、在本文中，我们假定计算负载是无限可分的，但是在实际应用中这是不可 能的，计算负载有最小的可划分单位，负载不可能达到绝对平衡。从这个 意义上讲，只能将负载平衡维持在适当的限度之内。所以，当负载平衡函 数值下降到某个事先规定的阈值时即可终止循环过程。 二、在水连通器中，通过两个容器间管道的水的速率与容器的高度差相关，是 一个即时变化量。理论上，它的取值范围从0 至无穷大。类似的在扩散 算法实施中，某一个时间片断，两节点间网络连接的负载传输速琦莲与两节 点的计算时间差相关。即公式( f 一矿) 。理论上，的取值范围也可从 1 1 巾1 1 1 人学硕十论文异构系统负故平衡扩敞算法的度优先加速法 0 至无穷大。事实上，由于实际网络传输带宽的限制，b 在使得m 满足式( 2 - 4 ) j _ = 警， 斗剥 ( 2 7 ) 在具体实旌中，可设置各小区域负载均衡阀值相等。这样，整个系统中， 巾l lj 人学硕士论文并构系统负载平衡扩敞算法的度优先加述法 只要有一个小区域存在着负载不均衡，势必弓i 起其邻近区域内的负载均衡过程。 最终达到整个系统的负载均衡。 2 ) 权重系数 h 的选取要满足以下条件： h ，0 ( 1 _ 号矽卸 在异构系统负载均衡扩散算法一文中，作者提出如下扩散矩阵构造和权 重系数。 m 。 ， 如果i 平u j 相邻 o ，其它 ( 2 8 ) 1 一荟矗 如果= j 一 r ；= r a i n 删n ( 赤，志) ( 2 9 ) 其中函是节点上各次迭代时的计算时间求和即d ? 2 薹f 。 以下证明以上的定义在异构系统巾小适用，并提出新的定义法e 证明：对比由上述定义( 2 8 ) 和定义( 2 - 6 ) 中的m ： 立， 如果i 和j 相邻 s i 0 ， 其它 ( 2 - 6 ) ，一妻荟h 如躲j 可知= 互s i ：同理有r j 专；又由的定义( 2 - 9 ) 可钒一：坝帕詈2 詈。 根据前文h 的意义，有勺一7 a ，得到暑= 5 ，。即所有节点速度均相等a 而在异构 系统中，各节点的计算速度是不同的。节点速度相同是同构系统的特征。因此， 巾1 1 1 人学碗十论文 异构系统负城平衡扩敞算法的度优先加速法 上文e er ：的定义不适合于异构系统。 或者由上述定义( 2 - 8 ) 可知，m 为对称矩阵。在定理2 中我们已知胜f 。 。 其中m 、和f 。均为对称矩阵。若m 为对称矩阵，即m = m t ，则有f 。m 、= ( s i m 、) = r 1 心0 t _ m 苫1 ，竹= s m w 。= s - i m - s 。因为s 为对角阵，所以仅当s 的对角元 素全相等时才成立。因此，上文中的定义不适合于异构系统。 吒阴新足义。 本文提出z 0 的定义如下： b = m i n ( s , , 飞s _ ) x 可厂一 则t r ：为： = 妻m i n ( s , , s 雨) x 万一 显然，它满足条件 m o 。 ，如果i 和j 相邻 0 ， 其它 1 一荟r ： 如果= j 心，o 卜驴加且 2 4 2 并行计算步骤 荟卅m - 1 计算步骤分为初始化、迭代求节点最终计算、求各边负载转移量三个部分。具 体算法如下： 1 4 中i ij 大学硕士论文异构系统负坡平衡扩散算法的度优先加述法 步骤a ：初始他 d o ，对槭于奉节点邻居的j 衙环 向节点j 非阻塞发送木节点的计算时删，p 从节点j 阻摩接受该节点的计算时刚f f ： e n d d o h - 算m q = 和 = 1 - 步骤b ：迭代求节纛聚铎计算聪两 d o ，开始这代 d o 对瞄于奉节点邻居的j 衙环， i l j o ) kj 非阻塞发送木节点的计算时u j ，p 从节点j 阻塞接受该节点的汁算时u j f r ： ，= w + m f r ： e n d d o 计算负找平衡函数如( 见式( 2 - 7 ) ) ： 计算d r “= d j + 矿： 1 i f ( i m 大予给定阀值) t h e n 计算掣“”= m 玎”+ ，： e l s e 转步骤c e n d i f e n d d o 步骤c ：隶各条边上负载转穆盈 d o 对槭丁小节点邻居的j 衔环 向节点j 非阻塞发送本节点的计算时f “jd p ： 从节点j 阻塞接受後节点的汁算时问d 寸： g t 算边( i ，j ) 上的负找转移孕：w f f = r q ( d f d ) ： 0 ，表示节点， g i i 移动汁算负载；否则，节点i 向，移动负垅。 e n d d o 巾1 1 1 人学硕十论文 芹构系统负载平衡扩敞算法的度优先加速法 2 4 3 数值实验与性能分析 在本节中，我们将设计实验，验证经过改进的扩散算法。 实验选用大规模数据计算常用的二维格栅网。模拟考察一个3 x 3 二维格栅网的 收敛情况a 实验中，设置节点的处理速度为4 1 6 之间的随机数，节点的，f o 初值为 5 2 5 问的随机数，令负载均衡函数的阀值为0 1 5 。 图2 2 负载甲衡前的运算时问和计算负投移动方向及转移量 图2 - 3 计算负载移动方向及转移罱是算法执行前的负载分稚情况。其中，每个方框 表示一个节点，框内第一行数字为该节点的负载处理时间，第二行为该节点的处理 速度。 算法执行过程如下： 送代参l l 1 2l | 1 4 l s1 6l tl l 。 l ( 1 ) ：2 1 7 5 2 0 6 9 1 3 8 4 8 9 3 1 2 1 61 5 6 81 1 3 61 1 i o1 9 2 4 l ( 2 ) ：2 0 2 21 9 2 61 4 4 51 0 2 51 2 1 91 5 3 2l o 8 91 1 9 71 7 9 9 l ( 3 ) ：1 9 0 21 8 1 51 4 8 41 1 0 81 2 4 61 5 0 4l o 9 51 2 艄1 7 0 6 l ( 4 ) ：1 8 0 61 7 3 11 5 0 61 1 6 61 2 7 41 4 8 5 1 1 2 11 2 7 41 6 3 5 l ( 5 ) ：1 7 2 8 1 6 6 7 1 5 1 71 2 ，l o1 2 9 71 4 7 21 1 5 31 2 9 51 5 8 0 l ( 6 ) ：1 6 6 51 6 1 8cj 5 ，2 21 2 4 41 3 1 61 4 6 31 1 8 51 3 i o1 5 3 7 l ( 7 ) ：1 6 1 41 5 8 01 5 2 21 2 7 11 3 3 1m 5 6 1 2 1 61 3 2 31 5 0 5 1 6 l t l i l l 人学硕十论文 异构系统负披平衡扩敞算法的度优先加速法 l ( 8 ) ：1 5 7 31 5 5 11 5 1 81 2 9 31 3 4 31 4 5 i1 2 4 21 3 3 31 4 7 9 l ( 9 ) ：1 5 4 01 5 2 7 1 5 1 3 1 3 1 1 1 3 5 31 4 4 61 2 6 61 3 4 l1 4 6 0 l ( 1 0 ) ：1 5 1 3 1 5 0 81 5 0 61 3 2 51 3 6 11 4 4 21 2 8 61 3 4 81 4 4 5 l ( 1 1 ) ：1 4 9 11 4 9 31 5 0 01 3 3 71 3 6 81 4 3 8 1 3 0 21 3 5 51 4 3 3 l ( t 2 ) ：1 4 7 31 4 8 01 4 9 31 3 4 71 3 7 3 1 4 3 81 3 1 71 3 6 01 4 2 4 l ( 1 3 ) ：1 4 5 91 4 7 01 4 8 61 3 5 51 3 7 81 4 3 51 3 2 91 3 6 51 4 t 8 l ( 1 4 ) ：1 4 4 81 4 6 11 4 8 01 3 6 21 3 8 21 4 3 51 3 3 91 3 6 91 4 1 3 l ( i s ) ：1 4 3 9 1 4 5 41 4 7 41 3 6 71 3 8 51 4 3 11 3 4 81 3 7 31 4 1 0 l ( 1 6 ) ：1 4 3 l 1 4 4 81 4 6 81 3 7 21 3 8 51 4 3 11 3 5 51 3 7 31 4 1 0 l ( 1 7 ) ：1 4 2 5 1 4 4 31 4 6 31 3 7 61 3 8 51 4 3 11 36 11 3 7 31 4 1 0 l 0 8 ) ：1 4 2 1 1 4 3 81 4 5 81 3 7 61 3 8 51 4 2 71 3 6 l1 3 7 71 4 1 0 l ( 1 9 ) ：1 4 1 61 4 3 31 4 5 31 3 7 61 3 8 j1 4 2 7 1 3 6 61 3 7 71 4 1 0 l ( 2 0 ) ：1 4 1 31 4 2 91 4 4 91 3 7 61 3 8 5 1 4 2 71 3 6 61 3 7 7 1 4 1 0 l ( 2 1 ) ：1 4 0 91 4 2 61 4 4 61 3 7 61 3 8 51 4 2 21 3 6 61 3 7 71 4 1 0 l ( 2 2 ) ：1 4 0 f1 4 2 31 4 4 21 3 7 61 3 8 51 4 2 21 3 6 61 3 7 7 1 4 1 0 l ( 2 3 ) ：1 4 o l1 4 2 01 4 3 91 3 7 61 3 8 51 4 2 21 3 6 61 3 7 71 4 1 0 l ( 2 4 ) ：1 4 0 41 4 2 01 4 3 61 3 7 61 3 8 51 4 2 21 3 6 61 3 7 71 4 i o l ( 2 5 ) ：1 4 0 41 4 2 01 4 3 61 3 7 61 3 8 j1 4 1 81 3 6 61 3 7 71 4 1 0 l ( 2 6 ) ：1 4 0 41 4 2 01 4 3 31 37 61 3 8 5 1 4 1 81 3 6 61 3 7 71 4 1 0 l ( 2 7 ) ：1 4 0 4 1 4 1 71 4 3 31 3 7 61 3 8 51 4 1 81 3 6 61 3 7 71 4 1 0 l ( 2 8 ) ：1 4 0 41 4 1 71 4 3 01 3 7 61 3 8 51 4 1 8 1 3 6 61 3 7 71 4 1 0 图2 - 3 计算负载移动方向及转移鼙中，方框之间的连线代表节点之问的通信线路 箭头表示负载转移的方向，箭头上的数字表示该线路上的负载转移量。 1 7 巾l | 1 人学硕十论文芹构系统负载平衡扩敞算法的度优先加速法 图2 - 3 讣算负找移动方向及转移量 图2 - 4 实现负找甲衡以肝的汁算负放情况 图2 - 4 实现负载、i t 衡以后的计算负载情况中所示是经过2 8 次迭代之后的负载分布 情况。此时，系统中节点的最大运算时间为1 4 ：j 0 ，最小为1 3 6 6 。负载基本上达到 均衡状态。 经过数值实验初步验证，改进后的扩散算法能够平衡负载。 巾1 1 1 人学硕士论文芹构系统负载平衡扩敞算法的度优先加速法 第3 章扩散算法的加速研究 采用迭代法进行负载均衡，若在若干步迭代之后，能够达到负绒均衡，则负载 均衡过程收敛。反之，若在无数步迭代之后，仍不能够使得负载均衡，称负载均衡 过程不收敛。 采用迭代法进行负载均衡过程中，迭代次数越多，最终达到负载均衡的时间越 长：迭代次数越少，最终达到负载均衡的时间越短，负载均衡速度越快。负载均衡 的收敛速度是衡量负载均衡效率的一个重要标识。因此研究加快负载均衡的收敛 速度的方法，对提高负载均衡的效率有着重要意义。 本章将从扩散算法的扩散公式入于，分析其算法收敛速度的加速问题偿考引文 【1 5 1 ) 。并介绍日前的相关研究成果。 3 1 扩散算法的收敛因素 基于水连通原理的扩散法的扩散公式为： i = 腻u “1 可得l = z 一1 ) ：肘m d “) 一一m l ( o 由上式可知，扩散公式的收敛由扩散矩阵m 决定。 m i j2 t i j ，如果i 释u 卡目邻 s i 0 ， 其它 ，一荟如肌j r m = i f 么7 。其中s 为速度矩阵讹g o 。，s ：，s ，) ，a 为邻接矩阵，t = d i a g ( t bt 占t j “；蚓) 。因此，影响扩散收敛的因素有三个，分别为速度在系统中的 分配、连接图的拓扑结构和权重系数tr 的选取。 r f li | j 人学硕十论文异构系统负载平衡扩散算法的度优先加速法 本文假定系统连接拓扑图已定，权重系数t i = t 。分析速度分布对扩散的收敛影 响。 如果权重系数t i = t ，扩散矩阵肘可以写成肘= j t s 乞4 ，4 7 。 令m i i a a t ，赋m = 1 t s l m t ， 设的m 特征值为叩，s m 饷特征值为z ，则有q = 1 t 2 。 因为一k 口1 ，所以- 1 令速度取值依次为1 ，2 ，9 ： 3 计算图中各个节点的度： 4 用穷举法遍历每个连通图，求出p 值最小和最大时的速度分布情况。 5 对一百个连通图的求解结果，统计各个速度依次在度最小到最大的节点上分 布的次数。 硕十学位论文异构系统负找平衡扩敞算法的度优先加速法 c 实验数据统计： 表4 1 速度在度不同的节点上的分布情况 速度度 d ld 2d 3d 4d 5d 6d 7d 8d 9 v 9 = 9oooll4 4 2 07 0 v 8 = 8oo00381 75 12 1 v 7 = 7o00251 75 21 86 v 6 = 6 0 l o4 1 25 6 2 0 5 2 v 5 = 5o2 4 1 26 5953 o v 4 = 40 3 1 76 11 032 3 l v 3 = 3027 31 843ooo v 2 = 2o9 2620o00o v l ：l1 0 00ooooo0o 图4 - 2 速度在度不同的节点上的分布情况 d 实验数据分析： 从实验数据可知，在这一百个连接图中，当p 取最小值时。速度为l 的机器1 0 0 分布在度最小的位置；速度为2 的机器9 2 分布在度第- - d 的位置；速度为3 的机 器7 3 分布在度第三的位置，1 8 分布在度第四的位置：速度为4 、5 、6 、7 、8 的机 器基本上依次分布在度第四、五、六、七、八的位置左右：速度为9 的机器7 0 分 布在度第九的位置，2 0 分布在度第八的位置。速度大小与度大小基本上成正比关系。 图4 2 速度在度不同的节点上的分布情况为速度在度不同的节点上的分布直 硕十学位论文异构系统负载平衡扩敞算法的度优先加速法 方图。它更直观的显示出，节点的速度排序和度大小的排序基本上是一致的。计算 速度高的机器分布在连通图中度高的位置。 4 2 节点速度与数据交换量的关系 从上一节的试验中，我们发现了当收敛速度最快时，节点速度与节点的度基本 成正比这一现象。这一现象是有理可依的。 一方面，在并行计算系统中，如果节点的数据量交换越大，则相应的要求该节 点的数据处理能力越强。数据处理能力包括数据交换( 即传输) 能力和数据运算能 力。而在数据交换( 即传输) 能力相同的情况下，则要求数据运算能力越强。即节 点的数据交换量应与该节点的数据运算能力成正比。 另一方面，如果节点的运算能力越强，相比运算能力小的节点，它在单位时间 内可以处理更多的数据。为了系统尽快平衡，应该分配给更多的负载。即它应该安 排在数据交换量较大的位置。 在实际系统中，影响节点数据交换量大小的因素有两个。 1 节点的网络连接数： 2 节点是否为将系统分为较均等规模了系统的瓶颈点。 2 如上图所示网络中，位于中央的4 号服务器，通过五条线与周边其它服务器连 接，同时它又是左边1 、2 、5 号服务器与右边3 、6 、7 号服务器数据传输的中间点。 2 8 碗十学位论文_ 异构系统负载平衡扩敞算法的度优先加速法 因此，4 号服务器上数据交换量最大。 上述两个因素对应到连接图中的性质，即： 1 节点的度： 2 是否为将连接图分为较均等了图的割点。 因此，找出连接图中符合上述条件l 或2 的节点位置，并在上安排速度较快的 节点，能有助予加快整个系统任务完成的速度。 4 3 度优先速度分配加速法 根据上一节的结论，我们制定了根据数据交换量来安排速度分配的加速算法， 称之为度优先速度分配加速法