基于并行计算熵的同构集群负载均衡算法_图文

1、第卷第期年月深圳大学学报理工版文章编号：（）一基于并行计算熵的同构集群负载均衡算法孙宏元”，谢维信，杨勋”，陆克中（西安电子科技大学电子工程学院，西安；深圳大学超级计算中心，深圳）摘要：提出并行计算熵的概念以及基于并行计算熵的同构集群负载均衡算法理论分析证明并行计算熵作为系统负载均衡程度度量的合理性算法以并行计算熵来衡量集群系统中节点之间负载均衡程度，以节点任务运算量来衡量节点的负载信息，并根据并行计算熵来进行负载迁移决策实验证明相对基于任务数阈值的负载均衡算法并行计算性能有一定提高关键词：同构集群；并行计算；并行计算熵；负载均衡；负载迁移中图分类号：文献标识码：讨等。提出了一个集群计算的动态

2、负载平衡库，然而该库是建立在异构集群之上的，无法在同构集群上保持高效基于上述问题，本文提出并行计算熵的概念，以及一种基于并行计算熵最大化准则的同构集群负载均衡算法负载均衡技术用于在多处理器、多计算机、多网络、多硬盘等资源之间分配负荷，使得各资源不过载计算负载均衡则是将计算任务分配到集群系统的各个不同节点上，使整个集群系统计算性能提高这种集群系统一般称作高性能集群机，并广泛应用于科学计算等领域负载均衡是高性能集群系统中资源分配追求的主要指标心刮之一等。研究了在负载迁移过程中合理并行计算熵及其最大化准则熵主要用来表述和研究自然界中广泛存在的运迁移量问题，并提出一个基于簇的动态负载均衡算法该算法将节

3、点问的负载差异映射到一个适当的簇上，由该簇的质心得到需要迁移的合适任务数，以调整节点问负载的不平衡然而，该算法只研究动形式转化方向的不可逆性针对所要研究的问题，结合并行计算的实际需求，本文提出并行计算熵的概念，并加以应用为便于分析，首先作几个名词约定：任务类型：一个总的计算任务中，按照计算性质不同而划分的类型，如在多分辨正摄影像数据生成过程中，压缩和分割分属不同的任务类型了动态负载均衡的一个方面迁移执行，而对另两个方面信息收集和迁移决策没做研究等。研究了如何利用动态负载平衡去解决并行搜索树问题，并提出了轮叫调度（）的动态负载均衡算法，该算法使集群中所有节点都能均等地以某种合理的顺序被选择到然而

4、，该算法并未考虑到集群中节点当前的负载情况等提出了计算集群的模型，并在此模型上提出基于竞争的负载均衡算法模型主要是建立在异构集群之上的，而本研究是基于同构集群上第种任务用代表任务当量：不同任务类型之间，以各自计算时间的比值来衡量任务大小第种类型任务的当量为足节点负载：某节点上任务集合，即等待完成等。研究了基于并行深度优先搜索算法来测量集群上动的各类计算任务之和厶。，其中，。为第座个节点上，任务类型的任务个数态负载均衡算法的性能，并对动态负载均衡算法的可扩展性以及执行时问、加速比和效率进行了探节点相对负载率：某节点负载与并行系统总收稿日期：基金项目：国家自然科学基金资助项目（）；深圳市科技计划项

5、目（）作者简介：孙宏元（一），男（汉族），安徽省合肥市人，西安电子科技大学在职博士研究生，深圳大学教授第期孙宏元，等：基于并行计算熵的同构集群负载均衡算法负载之比；节点计算时间：节点后完成赋予其上的负载任务所需要的时间，用咒表示严格来讲瓦是。，五，。三者的函数，即瓦丁（，以，）其中五为节点后的频率；，为通信时间为了简化，在这里取节点相对负载率作为并行计算熵的定义定义如果一个并行计算机系统共有几个计算基于并行计算熵的负载均衡算法负载均衡的目标归包括：提供最短的平均任务响应时间；能适于变化的负载；是可靠的负载均衡机制一般的负载均衡算法都包含信息收集、迁移决策和迁移执行部分节点，在时刻，第后个计算节

6、点的相对负载率为。，则分布式计算机在时刻的计算熵日（）可定义为信息收集本文所要研究的问题可从任务的规模推算出任务的运算量情况及各节点上的总任务运算量设节（）点上的总任务运算量为三，且集群上的所有节点是同构的，即各节点运算能力相等，则节点上所有任务完成的时间正比于负载均衡的目标就是使任务均衡分布在集群中各节点上，以便各节点能够基本同时完成任务，从而使整个程序的执行时间（或称程序响应时间）最短因此，在同构集群系统上，当任务量可推算时，节点上的总任务运算量厶能比任务数更好地衡量节点的负载状况，故我们选择节点的总任务运算量作为负载指标本文采用集中负载信息收集方式，即由一个主控节点收集全局负载信息，其他

7、节点仅将状态信息传送给主控节点，并由主控节点做出决策迁移决策负载迁移需占用一定的系统资源并消费一定时间，若任意进行负载迁移可能会得不偿失因此，决定何时进行负载迁移是关键负载均衡度是指集日（）。（）可以证明，并行计算熵与所提出的信息熵具有类似的对称性、非负性、扩展性、可加性、极值性、确定性和上凸性等数学特性因此，本文提出的并行计算熵在熵的意义上是合理的下面论证并行计算熵作为一个衡量负载均衡程度度量的合理性即若能证明计算过程中，每一步都取最大熵增的迁移，就能使程序执行时问最短，则并行计算熵是衡量负载均衡的一个很好的量度因此，有必要分析并行计算熵与程序执行时间的关系由于程序执行时间一般取决于集群系统

8、中负载最大节点上的总任务运算量，而节点上的总任务运行量又正比于相对负载率，故本文着重分析并行计算熵与最大相对负载率的关系下面给出已经经过严格证明的定理和引理限于篇幅，证明从略定理并行计算熵达到最大值时候，程序执行时间最小当各个节点的相对负载率相等时，并行计算熵达到最大值由于各个节点的相对负载率相等，因此，程序执行时间最小定理分配在负载最大节点的任务量随并行计算熵的递增而趋于递减定理说明了并行计算熵与负载最大节点上的群系统中节点的负载均衡情况本文提出以并行计算熵作为集群系统中的负载均衡度的一种度量，用并行计算熵来判断是否需要负载迁移当系统的并行计算熵低于某个阈值珥时，系统负载均衡度较差，各节点的

9、负载平衡情况不好此时需进行负载迁移，即将重负载节点上的任务迁移到轻负载节点上，以平衡系统各节点间的负载，实现负载均衡迁移后系统的并行计算熵得到提高而当日只总任务运算量（即程序执行时间）的关系当并行计算熵增大时，负载最大节点上的总任务运算量趋向于减少，其他节点负载相应更加平均，使得程序执行时问期望减小这是基于最大熵增原理负载均时，系统的负载均衡度较高，毋需进行负载迁移从上述显见，并行计算熵临界值只是影响系统性衡算法的基础所以算法中尽最大可能提高并行计算熵值，以减少程序执行时间据此，可推出负载迁移的几个细则：能从负载大的节点向负载小的节点迁移任务，不能反向迁移先选择从负载最大的节点向负载最小的节点

10、迁移任务能的关键因素若以过高，则会导致系统节点间任务频繁迁移，从而降低系统性能，增大任务响应时间；反之，若只过低，则可能导致系统节点问负载极度不平衡，负载较重的节点上的任务响应时间过长，降低整个并行系统的性能深圳大学学报理工版第卷迁移执行调度节点从收集到的信息，计算系统并行计算熵是否达到迁移的阈值，决定是否进行负载迁移及选择将哪些任务迁移到哪些节点上在迁移决策中，选择并行计算熵来衡量系统的负载均衡度同样，在迁移执行中，也选择并行计算熵来判断如何迁移任务设集群系统共有个节点，节点上的任务集合为厶，此处的放置策略是使得各节点上的任务迁移后，系统的并行计算熵最大由于这个问题是一个完全问题，为此，根据

11、上节提出的负载迁移准则给出一个近似算法：任务迁移只从重负载节点到轻负载节点上；运算量阈值过小有效减少矩阵相乘的执行时间在实验中，将所提出基于并行计算熵的负载均衡算法（，算法）与目前较流行的基于任务数阀值的负载均衡算法（算法）作了比较在实验中，我们运算两个。阶方阵相乘该任务先在集群中某个节点上开始当负载不均衡时，任务分解为多个小任务，转移到其他节点上执行，从而使集群系统负载达到均衡，而当负载均衡时，任务可不作分解直接执行负载均衡算法用只这个未知参数表示决定是否进行负载迁移的并行计算熵的阈值实验主要分析不同节点数下的程序执行时问、（既。）的任务不做迁移因为其迁移对系统的负载均衡度影响甚微，反而徒增

12、代价也就是说，算法只把具有一定运算量的任务从重负载节点迁移到轻负载节点上，使负载均衡情况改善明显的任务经以上限制后，由定理可知，任务迁移后，系统的并行计算熵将增加，负载最大节点任务量将减小算法主要描述如下加速比、速率以及程序运行期间内系统并行计算熵的变化先看不同节点数下的程序的运行时间，取矩阵大小为阶，让节点数在变化当节点数为时，程序为串行程序；节点数大于时，先计算集群系统的平均负载。；计算各节点需要迁移的负载为。一。，依照迁移负载的符号及大小保持两个队列。和其中，。是。为正的节点队列，即负载过重的节点的队列，按照。从大，的顺序排列；是。为负的节点的队列，即负载过轻的节点的队列，按照有一个节点

13、为调度节点，其他节点为计算节点，实验结果如图曼旨厦留靶删。从大到小的顺序排列按从头到尾的顺序依次扫描，上节点运算量大于阈值形。血。的任务假设在扫描过程中，当前节点为，当前任务为，节点的负载为。，任务的节点数图不同节点数下的程序执行时间运算量为，且。再决定这个任务迁移到哪个节点上显然，为使负载更均衡，应选择最接近于迁入负载为“的节点为此，扫描上的节点，找从图可见，随着集群系统中节点数的增加，程序运行时间减少当节点数为时，只有一个计算节点由于负载均衡算法的代价，此时程序运行时间比串行程序还略长随着节点数增加，任务迁出一。的具有最大。的节点若节点存在，则将任务迁移到节点上移增多，负载均衡代价随之提高

14、，节点数的增加对程序运行时间的影响并不大，甚至会不降反升算法在节点数为时，程序执行时间已达到最低点，此时程序执行时间为，而仿真实验在“深超”上运行大矩阵乘法来验证负载算法的最小程序执行时间为，均衡算法的有效性，并与其他负载均衡算法性能作比较一般来说，在矩阵阶数较大时，矩阵乘法需算法将最小程序执行时间减少约图显示了不同节点数下的算法和消耗大量资源，、利用集群系统进行大矩阵相乘，可算法的加速比可见，算法的最第期孙宏元，等：基于并行计算熵的同构集群负载均衡算法大加速比为，而算法的最大加速比为，算法将最大加速比提高约，因为这时只有一个节点上有任务，不会进行负载迁移这个任务经过分解后，会生成个子任务，并

15、在个节点上运行，系统的并行计算熵得到提高这个任务产生子任务后，再进行负载迁移，系统并行计算熵得到进一步提高，并接近于最大值：，随后，系统并行计算熵稳定在左右在程序即将结束时，由于节点陆续完成任务退出，并行计算熵急剧下降，但这时并不进行负载迁移，因为节点上的负载已经很小节点数图不同节点数下的加速比牡；口五口图显示了不同节点数下的算法和算法的效率可见，算法的最大效率为，而算法的最大效率为，算法将最大效率提高了大约本文提出了并行计算熵的概念以及基于并行计算熵的负载均衡算法在算法中，以并行计算熵来衡量集群系统中节点间负载均衡的程度，以节点任务运算量（而非任务数）来衡量节点的负载信息本文对并行计算熵作为

16、一个衡量负载均衡程度度量的合理性进行了理论分析通过仿真实验，将所提出的基于并行计算熵的负载均衡算法与目前较流行的基于任务数阈值的负载均衡算法进行了分析对比结果表明，对于矩阵乘法这类计算任务量可事节点数嘻图不周节点数下的效率先估计的问题，基于并行计算熵的负载均衡算法可娥有效减少程序执行时间，提高加速比和并行效率参考文献：婆琳士姑牧知识库负载均衡：（英文版），用于多媒体应用的基于站点集群的负载均衡并行与分布式系统学报，（）：一（英文版）（），多尺度网络中具有全延迟约时间图并行计算熵随时间的变化束的最佳分页负载均衡无线通信学报，（）：（英文版），等一种用再看程序运行期间系统并行计算熵的变化，取矩阵的大小为阶集群节点数为，其中于动态负载均衡的自适应集群方法年并行结构、算法和网络国际会议论文集新泽西：，（英文版）个节点为调度节点，其他个节点为计算节点运行中，在调度节点上记录系统并行计算熵的变化，每进行一次负载迁移时，便记录负载迁移前后工作站和计算机集群中的动态负载均衡性能第届并行处理，算法与结构国际会议论文集新泽西：，：（英文