检索结果-南通市图书馆

异构分布式系统中基于负载均衡的容错调度算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2005年第11期28卷 1807-1816页

作者：郭辉王智广周敬利中国石油大学(北京)计算机科学技术系北京100220 华中科技大学计算机科学与技术学院武汉430074

提出了基于主/从版本的具有容错功能的进程调度算法HDALF和HDLDF,且分别给出两种算法的时间复杂度并对算法的负载均衡性和节点资源利用率作了讨论.与以往容错调度算法不同的是,此算法是在被动进程复制模式下、适合于异构分布式系统的容... 详细信息

提出了基于主/从版本的具有容错功能的进程调度算法HDALF和HDLDF,且分别给出两种算法的时间复杂度并对算法的负载均衡性和节点资源利用率作了讨论.与以往容错调度算法不同的是,此算法是在被动进程复制模式下、适合于异构分布式系统的容错调度算法.而以往的研究都是建立在主从版本进程有相等的负载或执行时间相同的模型基础上,或者仅适合于同构分布式系统.实验结果表明,HDALF算法和HDLDF算法的性能比基于同构分布式模型下的两阶段算法更加优越.并且得出了这样的结果:当系统发生故障前后的负载均衡性权值相等时,在负载均衡和处理机资源利用率方面,HDLDF算法都要优于HDALF算法.

关键词：容错系统异构分布式系统负载均衡容错调度算法进程分配

在线全文

学校读者我要写书评

暂无评论

异构分布式系统DAG可靠性模型与容错算法

计算机学报 2013年第10期36卷 2019-2032页

作者：谢国琪李仁发刘琳杨帆湖南大学嵌入式与网络计算湖南省重点实验室国家超级计算长沙中心长沙410082

异构分布式系统性能得到大幅度提升的同时,却造成故障率大增,以有向无环图(Directed Acyclic Graph,DAG)任务模型研究异构分布式系统的容错调度成为当前的研究热点.广泛采用的基于任务复制的容错算法存在以下问题:(1)DAG任务可靠性需求... 详细信息

异构分布式系统性能得到大幅度提升的同时,却造成故障率大增,以有向无环图(Directed Acyclic Graph,DAG)任务模型研究异构分布式系统的容错调度成为当前的研究热点.广泛采用的基于任务复制的容错算法存在以下问题:(1)DAG任务可靠性需求与DAG可靠性需求的约束存在缺陷且缺乏严谨的理论证明;(2)每个任务仅有一个副版任务,不足以应对任务潜在的多次发生的故障;(3)盲目地使每个任务拥有ε+1个副版来容忍可能的ε个故障,虽然提高了系统的可靠性但易造成系统冗余度过高,并付出昂贵的计算资源.文中首先分析DAG图中任务依赖关系,确定DAG任务的可靠性概率模型,并建立DAG可靠性模型;接着提出满足可靠性目标的任务复制下限值算法、经济的任务复制策略算法和贪婪的任务复制策略算法,精确量化各个任务需要复制的次数,最后在上述算法的基础上提出可选策略的DAG容错算法OPDFT(Optional Policy on DAG Fault-Tolerant).实验表明,OPDFT算法的经济复制策略和贪婪复制策略的可靠性代价分别是盲目策略算法可靠性代价的60%和70%左右.

关键词：异构分布式系统可靠性容错有向无环图任务复制

基于任务复制的高效异构分布式系统调度算法设计与实现

在线全文

学校读者我要写书评

暂无评论

基于任务复制的高效异构分布式系统调度算法设计与实现

作者：石昊华东师范大学

学位级别：硕士

异构分布式系统中计算应用的调度长度最优化问题备受关注。囿于通信网络的带宽及传输速度等限制,通信开销对调度长度的影响不容忽视,通过减少通信开销优化调度长度是研究的焦点之一。为尽量减少通信开销,基于任务复制的各类调度算法应... 详细信息

异构分布式系统中计算应用的调度长度最优化问题备受关注。囿于通信网络的带宽及传输速度等限制,通信开销对调度长度的影响不容忽视,通过减少通信开销优化调度长度是研究的焦点之一。为尽量减少通信开销,基于任务复制的各类调度算法应运而生,其可以通过额外的计算开销来减少通信开销,并取得了极好的效果。然而,任务复制的引入会使调度问题更加难以求解,如何在使用任务复制提供高质量调度方案的同时,减少求解时间是当前面临的一大挑战。针对上述挑战,本文将调度问题进行分解,按序求解分配子问题与排序子问题,并分别进行优化以提高求解效率。提出了一种两阶段的高效调度算法,能够给出允许任务复制下调度长度最短的方案。本文的主要贡献如下:1.分析并定义了基于任务复制的异构分布式系统调度长度最优化问题对任务复制所带来的解空间膨胀、链式反应及复制异常现象等调度算法设计难点进行了分析。并根据异构分布式系统及任务复制的特征进行系统及任务建模,形式化定义了基于任务复制的异构分布式系统调度长度最优化问题。2.设计了一种基于分支定界搜索的任务分配算法为避免链式反应,基于分支定界搜索设计了分配阶段算法,以调度长度上界为优化目标搜索任务的最优分配方案。基于拓扑序设计分支操作以避免搜索重复状态,并减少操作计算量,再在过程中根据已有目标值裁剪状态空间,提高算法的求解效率。3.设计了一种基于松弛区间的动态优先级任务排序算法根据任务的优先关系约束及分配方案,设计基于松弛区间的动态优先级对任务进行排序,以得到最终调度方案。为解决复制异常现象,该算法在任务排序过程中使各任务可以从任意处理单元上的前驱获得输入数据,进一步优化调度长度。4.开发了基于任务复制的异构分布式系统调度工具该工具提供友好的人机交互界面,实现了本文所建立模型及本文所提出调度算法。能够针对不同的系统配置及任务配置,给出基于任务复制的调度长度最优化调度方案。本文针对不同的系统配置与任务配置设计了分析实验,验证了本文所提出算法在不同情景下的有效性。并且在特定的系统配置下对比了先进的启发式调度算法与优化搜索调度算法,实验结果表明,本文所提出算法能够给出质量更高的调度方案,且求解时间较单阶段优化搜索调度算法显著减少。

关键词：异构分布式系统任务复制分支定界搜索动态优先级

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

异构分布式系统中一种新型主副版本调度算法

计算机工程与应用 2019年第21期55卷 93-98页

作者：朱永超周川郭健吴益飞崔玉伟南京理工大学自动化学院南京210094 中航工业西安飞行自动控制研究所西安710065

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法(HRPB)。任务模型以有向无环图(DAG)表示,该算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据... 详细信息

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法(HRPB)。任务模型以有向无环图(DAG)表示,该算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据任务执行时间及截止时限来制定新指标平均最晚开始时间(ALST)进行排序;在任务处理器分配阶段,采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试,实验结果表明,HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。

关键词：异构分布式系统优先级约束任务有向无环图主副版本任务调度

在线全文

学校读者我要写书评

暂无评论

异构分布式系统的可分任务调度算法

小型微型计算机系统 2015年第4期36卷 797-800页

作者：王晓萍孟坤西安文理学院软件学院西安710068 西安电子科技大学计算机学院西安710071

针对异构分布式系统下带数据结果收集的可分任务调度问题,通过设计一种新的遗传算法,包括编码与解码方案、交叉和变异操作,有效地解决了3个难点:(1)计算所需的处理机数目及最优的处理机选择;(2)给出最优的任务分配顺序;(3)计算每个处理... 详细信息

针对异构分布式系统下带数据结果收集的可分任务调度问题,通过设计一种新的遗传算法,包括编码与解码方案、交叉和变异操作,有效地解决了3个难点:(1)计算所需的处理机数目及最优的处理机选择;(2)给出最优的任务分配顺序;(3)计算每个处理机需要处理的任务大小.为了验证新算法的有效性,本文进行了一系列对比实验.结果表明任务分配序列对完成时间具有显著的影响,且新算法能够显著降低任务的完成时间.

关键词：可分任务分发顺序完成时间遗传算法异构分布式系统

在线全文

学校读者我要写书评

暂无评论

基于异构分布式系统的实时容错调度算法

计算机学报 2002年第1期25卷 49-56页

作者：秦啸韩宗芬庞丽萍华中科技大学计算机科学与技术学院武汉430074

目前文献中研究的实时容错调度算法都是基于同构分布式系统 ,系统中的所有处理机完全相同 .该文首先建立了一个基于异构分布式系统实时容错调度模型 ,异构分布式系统中的各个处理机均不相同 .基于该异构分布式系统模型 ,该文引入了可靠... 详细信息

目前文献中研究的实时容错调度算法都是基于同构分布式系统 ,系统中的所有处理机完全相同 .该文首先建立了一个基于异构分布式系统实时容错调度模型 ,异构分布式系统中的各个处理机均不相同 .基于该异构分布式系统模型 ,该文引入了可靠性代价 (reliability cost)概念 ,并提出两种静态实时容错调度算法 (RTFTNO和RTFTRC)用于调度周期性实时容错任务 .算法 RTFTRC在调度任务时 ,尽量使系统的可靠性代价最小 ;而算法RTFTNO在调度实时任务时 ,没有考虑系统的可靠性代价 .该文详细讨论了两种调度算法的性能 .性能模拟实验分别比较了两个算法的可靠性代价 ,超时比率和可调度性 ;并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系 .实验结果表明 ,算法 RTFTRC的性能优于算法 RTFTNO.

关键词：异构分布式系统模拟实验实时容错调度算法计算机

时间约束的异构分布式系统工作流能耗优化算法

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2016年第7期53卷 1503-1516页

作者：蒋军强林亚平谢国琪张世文湖南大学信息科学与工程学院长沙410082 可信系统与网络湖南省重点实验室湖南大学长沙410082

针对现有异构分布式可变电压/频率(dynamic voltage/frequency scaling,DVFS)计算系统下具有时间约束的工作流能耗优化算法易陷入局部最优的问题,提出了一种新的全局能耗优化算法:反向蛙跳全局能耗感知算法,该算法利用工作流下界完成时... 详细信息

针对现有异构分布式可变电压/频率(dynamic voltage/frequency scaling,DVFS)计算系统下具有时间约束的工作流能耗优化算法易陷入局部最优的问题,提出了一种新的全局能耗优化算法:反向蛙跳全局能耗感知算法,该算法利用工作流下界完成时间和约束时间之间存在的盈余,逐步从约束时间开始,以不同的跃度值向下界完成时间反向蛙跳,在此过程中基于局部最优解的判断不断调整跃度值直至蛙跳终点,同时保留该过程中工作流满足时间约束且任务运行能耗最小的调度序列.在此基础上利用处理器松弛时间回收技术,在保持任务间依赖关系和满足工作流时间约束的前提下,调整处理器运行电压/频率至更低的合适级别上,从而进一步降低工作流运行能耗.实验表明:该算法能显著降低工作流整体能耗,节能优势明显.

关键词：异构分布式系统能耗优化时间约束工作流松弛时间回收

在线全文

学校读者我要写书评

暂无评论

异构分布式系统中的负载均衡调度算法研究

异构分布式系统中的负载均衡调度算法研究

作者：杨锦湖南大学

学位级别：硕士

随着社会的发展,经济的突飞猛进,为了促进社会和谐,地震灾变的预测也就越来越重要了。现代计算机技术的迅猛发展,包括地震灾变预测等越来越多的工程计算问题都依靠于大型高性能超级计算机来解决。而工程计算从一定程度上又驱动了高性能... 详细信息

随着社会的发展,经济的突飞猛进,为了促进社会和谐,地震灾变的预测也就越来越重要了。现代计算机技术的迅猛发展,包括地震灾变预测等越来越多的工程计算问题都依靠于大型高性能超级计算机来解决。而工程计算从一定程度上又驱动了高性能计算机的发展。目前,并行系统,网格计算等分布式技术已经成为解决工程问题的重要方法,而在分布式系统中,为了提高分布式系统的性能,调度问题成为了现代分布式系统中的一个热点问题。各种调度算法被大批的研究人员所提出,它们的调度优化目标不尽相同,但是总的来说都是为了改进分布式系统的性能。为此本文以任务调度的负载均衡为目标,对任务调度问题进行了深入的研究。首先,针对现在异构分布式系统的负载均衡问题,本文设计了一个改进的动态遗传算法IDGA(Improved Dynamic Genetic Algorithm)应用于异构分布式系统的调度器中,以此来优化异构分布式系统的负载均衡性能。考虑到传统的遗传算法在任务调度的应用中存在着最大进化代数有限的缺点,本文涉及了IDGA算法,克服了最大进化代数受限的缺点,并且在找到符合负载均衡标准的解以后,IDGA算法会按照一定的策略重新设置系统的负载均衡标准来试图找到比当前最优调度更好的调度。其次,由于IDGA算法可以动态设置最大进化代数,那么有可能引起遗传算法时间复杂度的增加,为了提高IDGA算法的效率,通过引入MapReduce分布式系统模型,将IDGA算法在MapReduce模型下并行化。最后,在IDGA算法的并行化过程中,提出了一个用来表示遗传算法初始种群的数据结构——二叉选择树,在利用这个数据结构对遗传算法进行选择操作的时候,可以提高选择操作的时间效率。该二叉选择树是一个平衡的二叉树,所以搜索的平均复杂度是O(log n),其中n代表种群的规模。而传统的遗传算法中,只能通过线性时间复杂度O(n)才能成功选择出一个个体。该二叉树的每个节点上都记录了该节点左子树的所有节点的适应度之和与右子树的所有节点的适应度之和。所以在决定选择左子树、右子树还是当前节点时可以通过产生一个随机数,并根据各自的适应度函数值来进行选择,这样明显提高了选择操作的效率。

关键词：地震灾变模拟任务调度异构分布式系统遗传算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

异构分布式系统的可靠性任务调度策略研究

异构分布式系统的可靠性任务调度策略研究

作者：朱永超南京理工大学

学位级别：硕士

随着计算机和网络技术的飞速发展,分布式系统在飞行控制、自动驾驶、地震数据处理等关键领域被越来越广泛地运用,而异构分布式系统在提高计算性能和高可靠性方面具备着很大的发展前景。高效可靠的任务调度策略是异构分布式系统获取高性... 详细信息

随着计算机和网络技术的飞速发展,分布式系统在飞行控制、自动驾驶、地震数据处理等关键领域被越来越广泛地运用,而异构分布式系统在提高计算性能和高可靠性方面具备着很大的发展前景。高效可靠的任务调度策略是异构分布式系统获取高性能的关键。本文针对异构分布式系统的可靠性任务调度策略问题,主要研究工作如下:首先,针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法HRPB。任务模型以有向无环图(Directed acyclic graph,DAG)表示,算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据任务执行时间及截止时限来制定新指标平均最晚开始时间ALST进行排序;在任务处理器分配阶段,采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题。其次,针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主副版本调度策略SAPB。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果。再次,针对异构分布式系统中混合任务的调度问题,提出一种兼顾可靠性的调度算法MRHS。混合任务分为周期性任务与非周期性任务,周期性任务以DAG图模型表示;非周期性任务以四元组模型表示。离线阶段仅调度周期性任务,采取模拟退火算法搜索满足具有更高指标值的调度结果;在线阶段调度随机进入的非周期性任务,利用处理器空闲间隔选择具有更高指标值的调度结果,并引入延迟原则和任务再分配原则解决空闲间隔不满足随机任务调度需求的问题。最后,针对上述提出的可靠性任务调度策略,利用随机生成的任务模型进行仿真测试,验证所提可靠性任务调度策略的性能。

关键词：异构分布式系统有向无环图主副版本任务调度模拟退火算法