一种高效的负载平衡算法研究与设计

发布时间：2018-04-03 22:46

  本文选题：分布式并行计算　切入点：任务调度　出处：《东北大学》2014年硕士论文

【摘要】：分布式并行计算可以提供相对廉价且强大的处理能力,在研究和应用领域都得到了广泛的关注。负载平衡是影响分布式并行计算性能的重要因素之一,负载平衡策略的效率直接关系到分布式并行系统的执行效果。负载平衡作为提高分布式并行计算性能的关键技术,是一个NP问题,因此分布式并行系统只能通过优化得到近似解而不能获得最优的负载平衡。分布式并行系统具有的特点也进一步增加了负载平衡难度：首先,分布式并行计算系统中节点的异构性和任务的异构性增加了负载平衡策略的难度；其次,网络的异构性也对负载平衡策略提出了挑战；再次,分布式并行系统的不断扩展要求负载平衡策略具有良好的可扩展性；最后,负载平衡策略需要适应分布式并行系统的动态性。这使得,目前对负载平衡的研究在任务调度模型、算法复杂程度、信息获取、数据传输代价、调整策略等方面存在一些问题。针对上述问题,本文在现有研究的基础上设计了任务调度模型,并基于此模型提出一种简单高效的负载平衡算法。(1)针对分布式并行环境的特点设计了任务调度模型。首先,抽象出包含处理数据的任务和纯计算任务的任务模型。其次,抽象出接近实际的系统结构；基于历史值的影响设计了考虑工作节点计算能力动态性和异构性的处理机模型；提出标准网络距离的概念,更好地处理网络的动态变化和计算通信开销,并基于此设计了包含局域网和广域网的通信模型。最后,根据设计的模型给出任务组织形式、迁移方式以及本文负载平衡算法要解决的问题。(2)基于设计的任务调度模型提出一种高效的负载平衡算法。算法将负载平衡分为Assignment和Redistribution两个过程,针对两个过程分别提出了简单且准确性较高的任务调度算法(SHAS:Simple and High Accuracy Scheduling Algorithm)和基于性能收益因子的动态负载调整算法(DLAPGF:Dynamic Load Adjustment Algorithm based on Performance Gains Factor)。SHAS结合了按需和周期性的信息收集方式,并采用捎带信息的方式进一步提高信息的准确性,在此基础上充分考虑通信开销和数据传输代价,提出任务最终完成时间较准确的计算方式,最后在提出的任务调度原则的指导下采用Min-Min算法对新任务进行调度。DLAPGF通过分析得出负载平衡目标,然后基于标准网络距离确定伙伴节点,并采用改进的交互信息反馈方式获取伙伴节点的信息,最后根据工作节点的最终完成时间提出性能收益因子的概念,并在此概念的基础上采用任务交换和任务迁移操作实现动态调整策略,降低了数据传输代价。同时SHAS和DLAPGF在一定程度对系统的动态性进行了处理。(3)基于系统完成时间、系统平衡性、数据传输代价和消息开销四个性能指标,分别对SHAS和DLAPGF的实验结果进行对比和分析,表明了提出算法的有效性。同时,验证了参数和系统动态性对算法效率的影响。
[Abstract]:Distributed parallel computing can provide relatively cheap and powerful processing power , and has gained wide attention in research and application fields . Load balancing is one of the most important factors affecting distributed parallel computing performance . Load balancing is a key technique that affects distributed parallel computing performance . The load balancing act as a key technology to improve the distributed parallel computing performance . The load balancing act as a key technology to improve distributed parallel computing performance . The load balancing act as a key technology to improve the distributed parallel computing performance . The distributed parallel system can only be optimized to get the optimal load balance . The distributed parallel system has the characteristics of increasing the load balancing difficulty . First , the heterogeneity of the nodes in the distributed parallel computing system and the heterogeneity of the tasks increase the difficulty of the load balancing strategy .
Secondly , the heterogeneity of the network also presents a challenge to the load balancing strategy .
Thirdly , the expansion of the distributed parallel system requires that the load balancing strategy has good scalability .
Finally , the load balancing strategy needs to adapt to the dynamic of the distributed parallel system . This makes the research on load balancing have some problems in task scheduling model , algorithm complexity , information acquisition , data transmission cost , adjustment strategy , etc . Aiming at the above problems , this paper designs a task scheduling model based on the existing research .
Based on the historical value , a processor model considering the dynamic and heterogeneous computing ability of the working nodes is designed .
In this paper , the concept of standard network distance is put forward to better deal with the dynamic change of network and calculate the communication cost . Finally , according to the design model , a kind of efficient load balancing algorithm is proposed . SHAS combines the information collecting mode with the demand and periodicity , and further improves the accuracy of the information by using the way of backing up the information . In the end , the method of calculating the performance benefit factor is proposed by using the Min - Min algorithm . At the same time , the dynamic performance of the system is determined by using the improved interactive information feedback method .

【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP338;TP301.6

【相似文献】

中国期刊全文数据库 前10条

1 杨颖;杨磊;乐嘉锦;;基于范围分割数据的负载平衡算法的研究[J];计算机应用研究;2006年04期

2 胡益红;蒋加伏;赵嘉;;一种基于生态捕食模型的网络负载平衡算法[J];计算机工程与应用;2010年19期

3 王广召，，马立勇;一个基于局部服务策略的最优静态负载平衡算法[J];哈尔滨电工学院学报;1994年03期

4 魏振华,洪炳熔,乔永强,蔡则苏,彭俊杰;基于偏差信息的星载计算机系统负载平衡算法的研究[J];宇航学报;2002年06期

5 董肖;;两种负载平衡算法的设计与比较[J];电脑与信息技术;2007年06期

6 王鹏;董渭清;王甜;;基于反馈的片上多处理器系统层次负载平衡算法[J];西安交通大学学报;2008年02期

7 谢红薇;谢显宇;;基于内容的网络集群负载平衡算法模型[J];计算机应用与软件;2010年01期

8 刘晓尼;祝永志;傅莹;;一种基于异构系统的动态负载平衡算法[J];计算机与信息技术;2010年10期

9 蒋江,张民选,廖湘科;一种基于多种资源的负载平衡算法的设计与模拟[J];计算机工程与科学;2002年06期

10 蒋江,张民选,廖湘科;基于多种资源的负载平衡算法的研究[J];电子学报;2002年08期

中国重要报纸全文数据库 前1条

1 本报记者 晓岚;Radware：锁定负载均衡[N];计算机世界;2002年

中国博士学位论文全文数据库 前1条

1 刘旭;基于图剖分和图排序的负载平衡算法研究[D];中国工程物理研究院;2008年

中国硕士学位论文全文数据库 前10条

1 曲全民;一种高效的负载平衡算法研究与设计[D];东北大学;2014年

2 胡茂伟;一种基于分级的负载平衡算法[D];暨南大学;2002年

3 黄珊;面向集群的负载平衡算法的研究与实现[D];南京农业大学;2009年

4 余玉连;基于Cayley图互连网络的负载平衡算法研究[D];华南理工大学;2010年

5 郭冰;异构Web Server集群负载平衡算法的研究[D];河北工业大学;2003年

6 郭建根;HP2P网络负载平衡算法的设计与仿真[D];西安电子科技大学;2014年

7 姚冲;并行系统互连网络负载平衡算法的设计与实现[D];大连理工大学;2009年

8 郑锦;实时分布式系统的容错设计与负载平衡算法的研究[D];辽宁工程技术大学;2004年

9 胡陈丽;GECISM中基于P2P的多机配置模型及负载平衡算法研究[D];河北大学;2006年

10 何毅权;基于sort first并行渲染系统的动态负载平衡研究[D];电子科技大学;2011年

本文编号：1707255