基于超立方体的静态任务调度

该文给出一个基于超立方体的静态任务调度算法.在算法的设计中,首先建立了任务优先级表和处理机优先级表,任务在调度时总是顺次调度高优先级任务,然后再从处理机优先级表中选择能使该任务最早开始执行的处理机.最后,分别给出了基于LU分解的任务图与随机生成的任务图的调度结果.     

一种适于异构环境的任务调度算法

针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.     

端到端时间约束的实时任务动态调度算法

在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率.     

异构机群系统上带返回信息的可分负载多轮调度算法

针对处理机具有不同的计算速度、通信能力的异构机群计算环境,以及实际应用中许多问题的求解在处理完任务后向中心处理机节点返回处理结果信息的情形,通过允许计算和通信操作重叠执行,采取FIFO调度策略和多次并行分配计算任务的方法,提出一种带返回结果信息的调度轮数可变的可分负载多轮调度算法.实验结果表明,该算法对于处理具有返回结果信息的应用的调度性能优于UMR可分负载多轮调度算法,并且可以获得近似最优的调度轮数.     

一个有效的Join任务图的调度算法

已有的Join任务图的调度算法大多不是基于通信竞争的环境而开发,且未考虑节省处理机的问题,使算法的应用效果不佳.因此,针对Join任务图,提出一个通信竞争环境的调度算法,该算法因串行通信边而改善其调度效率,时间复杂度为O(vlogv),其中,v为图中任务的个数.实验结果表明,与其他算法相比,该算法的调度长度较短且使用的...     

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

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

基于优先级和优化完成时间的网格调度算法

网格由大量的异构资源组成,具有复杂性、动态性和自治性特点。高效的网格调度算法可以充分利用网格系统资源,提高网格处理应用程序的能力。Min min算法是一个简单、快速、有效的调度算法,但由于总是先分配小任务而不能确保负载平衡。文中首先对网格系统中任务的数据传输和执行进行分析,计算并优化Min min算法的任务完成时间,再根据任务需求赋予任务优先级,通过优先级安排任务调度,提高算法负载平衡能力,最后在上述分析基础上提出POTE Min min(Priority and Overlap Transmission and Execution Min min)调度算法。     

通信竞争环境中Join任务图的一个调度算法

Join任务图是一种并行处理的基本结构。目前已有的Join任务图的调度算法大多忽略了通信链路的竞争、延迟以及节省处理机的问题,导致算法在实际应用中效率较低。针对这一问题,提出一个基于通信竞争的Join任务图的调度算法,该算法通过对各通信边的串行化而在任务调度中集成通信竞争,其时间复杂度为O(vlogv),其中v表示图中的任务数。实验结果表明,相比其他算法,该算法就调度长度、使用的处理机数、加速比和效率而言为优,具有更强的实用性。     

异构环境中Fork-Join任务图的调度算法

目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低.因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为O(v~2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性.     

基于选择性复制前驱任务的DAG调度算法

针对异构环境下相关任务的静态调度问题,以最小化调度长度为主要目标,结合表调度与基于复制的调度思想提出了选择性任务复制调度算法.在任务调度过程中,利用处理器的空闲时间,通过有选择地复制能提前当前任务开始执行时间的父任务来减少任务之间信息传递的通信延迟,有利于后续任务的及时调度,从而缩短整个任务图的并行完成时间.实验结果表明,文中算法在通信量比较大的情况下在时间上优于复杂度相同的HEFT,HNDP及DDS算法,且随着任务图中通信时间/计算时间比值的增加,其优越性也越来越明显.     

一种基于模糊聚类的网格DAG任务图调度算法

针对网格环境中,任务调度的目标系统具有规模庞大、分布异构和动态性等特点,提出一种基于模糊聚类的网格异构任务调度算法.以往的很多调度算法需要在调度的每一步遍历整个目标系统,虽然能够获得较小的makespan,但是无疑增加了整个调度的Runtime.定义了一组刻画处理单元综合性能的特征,利用模糊聚类方法对目标系统(处理单元网络)进行预处理,实现了对处理单元网络的合理划分,使得在任务调度时能够较准确地优先选择综合性能较好的处理单元聚类,从而缩小搜索空间,大量减少任务调度时选择处理单元的时间耗费.此外,就绪任务优先级的构造既隐含考虑了关键路径上节点的执行情况对整个程序执行的影响,又考虑了异构资源对任务执行的影响.实验及性能分析比较的结果表明,定义的处理器特征能够实现对处理器网络的合理划分,而且随着目标系统规模的增大,所提出的算法优越性越来越明显.     

云环境下两阶段安全驱动的容错调度算法

为解决云环境下安全调度和可靠性问题,综合考虑云计算共享性、动态性等特点,以具有依赖关系的并行任务为基础,提出一种两阶段安全驱动的容错调度算法(TSDFT).建立安全模型计算任务调度风险率,根据风险率选择处理机,使用自适应备份策略对任务进行备份预处理;在上一阶段基础上,通过被动副本方式实现任务容错调度,每个处理机维护主/副本2个局部队列,支持一个以上处理机同时失效.仿真结果表明,该算法能有效降低异构系统中任务调度风险率,提高调度的安全性和可靠性.     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

基于异构环境的Out-Tree任务图的调度算法

分布式应用程序的有效调度是异构计算系统中的一个关键问题。目前已有的Out-Tree任务图的调度算法大多基于同构环境而开发,未考虑处理机的异构性,导致调度的效率较低。针对异构计算环境,提出一个基于列表和任务复制的Out-Tree任务图的静态启发式贪心调度算法,其时间复杂度为O(hv^2p),其中h、v和p分别表示任务图的高度、任务个数和调度使用的处理机个数。实验结果表明,相比其他算法,该算法能提供调度长度较短、处理机使用较少的有效调度,其应用性更强。     

一种全局较优的静态任务调度算法

针对现有任务调度算法优先级选取过于单一所产生局部较优调度结果的问题,从全局较优出发,提出一种先分层后分支决定优先级的静态任务调度算法—HGCOTS算法。该算法考虑了任务间较大的通信开销和冗余任务对异构CMP任务调度效率的影响,通过综合区间插入和任务复制技术最大限度地降低了任务间的通信开销,对冗余任务进行删除,明显提高了任务调度效率。使用随机生成图进行模拟实验,与其他算法相比,新算法具有更小的调度长度。     

异构系统中一种基于可用性的抢占式任务调度算法*

针对大多数现有的异构系统调度算法没有考虑由多类任务特别是抢占式任务所引起的可用性需求的不足,在现有基于可用性的非抢占式任务调度算法的基础上,通过计算任务的平均等待时间来确定优先级等级,对异构系统中多类抢占式任务的可用性约束的调度问题进行了探索,提出了一种基于可用性的抢占式优先调度算法P-SSAC。该算法在不增加硬件代价的前提条件下通过调度增加了系统的可用性,缩短了任务的平均等待时间,同时该算法可对抢占式的任务进行有效调度。仿真实验结果表明,该算法有效实现了异构系统可用性和任务等待时间之间的折中。     

异构分布系统的实时任务轮转式容错调度算法

建立了一个异构分布式系统实时调度模型,对异构分布式系统中的任务及不同处理机资源进行了形式化描述.结合基版本/副版本技术,给出了用于异构分布式系统的实时任务轮转式容错调度算法.实例分析表明,该算法有效提高了异构处理机环境下的资源利用率以及整体计算性能.     

一种基于负载均衡性的网格任务调度算法

针对二分图匹配算法在任务之间存在时序关系时无法进行有效调度以及EFT算法没有充分考虑各处理机性能及网络通信状况的问题,提出基于二分图匹配的改进ETF算法。该算法综合考虑任务之间的时序关系、处理机的性能、处理机之间的通信情况及已处理任务的调度情况,利用二分图最佳匹配思想对局部任务进行调度。实验表明该算法具有较小的调度长度和较好的负载均衡性。     

资源不均衡Spark环境任务调度优化算法研究

由于硬件资源的更新换代,集群中各个节点的计算能力会变得不一致。集群异构的出现导致集群计算资源不均衡。目前Spark大数据平台在任务调度时未考虑集群的异构性以及节点资源的利用情况,影响了系统性能的发挥。构建了集群节点的评价指标体系,提出利用节点的优先级来表示其计算能力。提出的节点优先级调整算法能够根据任务执行过程中节点的状态动态调整各个节点的优先级。基于节点优先级的Spark动态自适应调度算法(SDASA)则根据实时的节点优先级值完成任务的分配。实验表明,SDASA能够缩短任务在集群中的执行时间,从而提升集群整体计算性能。     

一种用于异构环境中并行任务调度的弹性节能算法

节能调度算法设计是高性能计算领域中的一个研究热点。本文通过软件方法设计异构多核计算机的调度算法,实现系统的弹性节能,达到降低能耗并提升系统性能的目的。本文的调度策略建立在基于处理器异构的并行任务调度的环境中,构建了节能模型,提出了EAPS（Energy-aware parallel scheduling）算法模型,该算法在每一任务完成之后重新计算优先级以使优先级符合任务的实时情况,并对复制的前驱任务是否冗余任务进行判断从而避免资源的浪费,并通过调节节点电压选择能耗最少的节点进行调度,在节能与期望完成时间之间取得平衡。