调度Fork-Join任务图的贪心算法

任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题.虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题.Fork-Join结构是一种并行处理的基本结构.因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少.     

一个调度Fork-Join任务图的最优算法

Fork-Join任务图是一种并行处理的基本结构.虽然许多算法在任务满足某些条件时能产生最优调度,但往往没有考虑节省处理器个数和减少任务集的总完成时间,从而降低算法的加速比和效率.因此,提出一种基于任务复制的平衡调度算法,其时间复杂度为O(vq+vlogv),v和q分别表示任务集中任务的个数和使用的处理器个数.通过分析已用处理器的负载和空闲时间段,把任务尽量分配到已用的处理器上以均衡负载,从而提高其利用率.实验结果表明,该算法的加速比和总体效率优于其他算法.因此,该算法对于高性能应用程序的调度是一个较好的选择.     

基于通信竞争的Fork-Join任务图的调度算法

Fork-Join任务图是一种并行处理的基本结构,目前已有的Fork-Join任务图的调度算法大多没有考虑实际应用中通信链路的竞争及延迟以及节省处理机的问题,导致算法在具体应用中效率较低.因此,针对Fork-Join任务图,提出一个基于通信竞争的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(vlogv),其中v表示任务集中任务的个数.实验结果表明,该算法相比其它算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性.     

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

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

一个调度Fork-Join任务图的新算法

对基于总线的机群系统,本文提出了一种基于任务复制的调度Fork-Join任务图的新算法。该算法通过任务集划分计算调度长度,并在不增加调度长度的同时将任务尽可能调度在已用处理器上,节省处理器数。新算法的时间复杂度高于现有算法,但其调度性能最优。     

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

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

基于任务复制的调度算法

任务调度是并行分布式计算系统中最具挑战性的NP完全问题之一.基于任务复制的调度是一种有效的调度方法.在通信开销较小的情况下,现已有许多算法能产生最优调度.但其最优条件要么比较苛刻,要么比较复杂.因此,针对这些算法存在的问题,提出一个新的基于任务复制的聚集调度(TDCS)算法,不仅其最优条件简单、宽松,而且该算法具有更小的时间复杂度O(dvlogd),其中,V和d分别表示任务集中任务的个数和最大入度.     

同构环境中Join任务图的一个调度算法

任务调度问题是一个NP完全问题。Join结构是一种并行处理的基本结构,虽然许多算法对Join任务图能产生最优调度,但大多都忽略了节省处理机个数和最小化程序总的完成时间等问题。因此,专门针对Join任务图,提出一个能产生最优调度的同构贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O（v2）,其中,v表示任务集中任务的个数。实验结果表明,相比其他算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少。     

一个调度Out-Tree任务图的启发式算法

任务调度问题是并行分布式计算中的挑战性问题之一。大多数实际的调度算法是启发式的因而常常具有改进的余地。针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的处理器最少。因而,该算法提高了系统的利用率,避免消耗过多的资源,实际应用性更好。     

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

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

异构集群下的任务调度算法研究

针对异构集群下高效节能的任务调度算法进行了研究, 提出了一种基于复制的任务调度算法, 在任务初始分配的基础上, 分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型, 并进行了大量的实验。实验结果表明, 与已有的BEATA算法相比, 该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现, 任务复制的方法在减少调度长度的同时会增加相应的能耗, 能同比优化调度长度和能耗的任务调度方法是今后的研究方向。     

异构系统中的综合性启发式任务调度算法

任务的单个属性常作为基于优先驱动的表调度算法的优先级,针对这种方法常出现优先级相同的情况,提出一个综合性启发式算法HCPFS。算法分三个优先级选择任务进行调度,从高到低依次为：关键路径上的任务、就绪任务到出口任务的路径长度和后继任务数。调度过程中,算法采用任务复制和空闲时间区段任务插入的方法。采用随机生成图法和任务图集进行了算法模拟和比较,实验数据表明HCPFS算法具有更好的调度性能。     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

一个调度Fork-Join任务图的新算法

任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,     

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

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