一种基于多处理器任务复制的分簇调度算法

任务调度的优劣是决定并行分布式计算机系统性能好坏的重要因素之一。为优化任务调度,基于一些典型算法(如LG、PPA算法等),提出了一种新的任务调度算法。该算法一方面复制满足条件的前驱任务来缩短调度长度;另一方面合理地复制其他前驱任务和合并冗余簇来减少所需处理器的数目。实验表明,该算法在调度长度和所需处理器的数目上优于以上典型算法,并具有更小的时间复杂度,对并行计算机系统性能的提升具有一定的意义。     

基于任务复制的静态调度算法研究

任务调度是分布实时系统中的一个关键问题。基于任务复制的静态调度算法是任务调度问题中的研究热点。通过概括任务复制静态调度算法的算法模型以及基本术语后，详细分析比较了几种典型算法。还考虑了优化条件、调度长度、处理器数目以及时间复杂度等研究方向。最后，结合国内外研究现状，提出以减少处理器数目为研究目标。     

一种基于调度簇树的周期性分布实时任务调度算法

本文针对现有的基于任务复制的静态调度算法在调度周期性分布实时任务时存在的缺点，提出了一种称之为调度簇树（SCT）的新的结构并研究了其特性，在此基础上给出了一种基于SCT树的周期性分布实时任务调度算法（SAS）。通过与OSA算法进行比较的实验结果表明，SAS算法可实现调度长度向上最接近分布实时任务周期，最大程度减少所需顸留处理器数目，大大提高分布实时系统的处理器利用率，同时并不增加调度算法的复杂度。     

一种改进的基于任务复制的多核调度算法

在多核系统中,任务调度是决定系统性能的关键因素之一。为优化任务调度,基于一些典型的任务调度算法（如PPA,徐成提出的算法等）,提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序,而且进行两个阶段的复制,从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间;另一方面,通过去除不影响任务系统调度长度的冗余簇,然后进行簇之间的合并,以减少处理机的数目和调度长度。实验表明,改进后的算法在任务调度的性能上优于典型算法。     

一种面向同构集群系统的并行任务节能调度优化方法

节能调度算法设计是高性能计算领域中的一个研究热点.复制调度算法能够减少后继任务等待延时,缩短任务总体调度时间,但是耗费了更多的能量.为此,作者提出一种启发式处理器合并优化方法 PRO.该方法按照任务最早开始时间和最早结束时间查找处理器时间空隙,将轻负载处理器上的任务重新分配到其它处理器上,从而减少使用的处理器数目,降低系统总体能耗.实验结果表明,和已有的复制任务调度算法TDS、EAD和PEBD相比,优化后的调度算法在不增加调度时间的条件下,能够明显减少使用的处理器数和系统总体能耗,从而更好地实现性能和能耗之间的平衡.     

TSA—OT：一个调度Out—Tree任务科的算法

对于把一个任务群调度到多个处理器的问题,人们往往只注重找到一个调度路径最短的算法,却忽略了要节省处理器。收于Out-Tree任务图代表分治算法的一大类问题,因此,文中专门针对该任务图,给出了一个基于任务复制的算法TSA－OT。它首先分配关键路径上的任务结点,然后在不改变调度长度的情况下,把非关键路径上的结点尽可能分配到已用的处理器上。并且,该算法将Out-Tree任务图中的所有通信都化为零。TSA－OT算法与近几年所提出的TDS,CPFD,DCP算法之间的比较表明,TSA－OT算法不仅调度长度最短,而且采用了更少或相当个数的处理器。     

基于禁忌搜索的多处理器任务调度算法

为合理利用多处理器资源,对任务调度算法进行研究,针对现有任务调度算法在任务规模较大的情况下全局寻优能力方面的不足,提出基于禁忌搜索的多处理器任务调度算法。对任务图不设任何约束条件,利用基于任务复制的TDS算法产生高质量的初始调度以降低算法复杂度,利用禁忌搜索算法全局寻优得到最优调度。实验结果表明,该算法可以有效降低任务调度长度,减少所需处理器数目。     

一种基于任务全局迁移的静态调度算法

任务调度是分布实时系统中的一个关键问题.TDS等典型算法在优化条件下可得到该问题调度长度上的最优解.但是TDS等算法在节点分配时存在节点选择范围和节点执行时间范围的局限,无法最小化算法所需处理器数目.任务全局迁移调度算法GTT（global task-transferring）在保证调度长度最优的前提下,从全局范围内选择并调度任务节点,有效利用了处理器,可最小化调度所需处理器数目.优化条件下对各种算法的调度实验表明,GTT算法在加速比和效率上比TDS等同类算法有显著提高.GTT算法的时间复杂度是O（d ｜ V｜^ 2）.这里｜V｜是DAG图中的节点数,d是图中各节点入度或出度的最大值.     

一个基于复制的相关任务调度算法

基于任务复制的调度是一种新的调度方法，现已有许多基于任务复制的调度算法在任务满足某些条件时能产生最优调度，但也存在一些不足．因此，针对一些算法存在的问题，提出一种新调度算法，该算法既考虑合并其它父任务以减少通讯时间，同时尽可能少的合并祖先任务，从而尽量减小任务的启动时间，因而能产生更短的调度．大量实验数据表明，该算法的性能明显优于其它算法。     

基于任务复制的网格任务调度算法

网格中资源之间存在着通信延迟，通过任务复制的冗余，可以减少任务之间的通信开销，缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的；而基于任务复制调度算法往往会产生过多的复制任务，增大系统开销，甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题，因此本文提出了一种基于任务复制的网格资源调度算法，以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。     

基于动态关键任务的多处理器任务分配算法

多处理器调度问题是影响系统性能的关键问题,基于任务复制的调度算法是解决多处理器调度问题较为有效的方法.文中分析了几个典型的基于任务复制算法,提出了基于动态关键任务(DCT)的多处理器任务分配算法.DCT算法以克服贪心算法不足为要点,调度过程中动态计算任务时间参数,准确确定处理器的关键任务,以关键任务为核心优化调度,逐步改善调度结果,最终取得最优的调度结果.分析和实验证明,DCT算法优于现有其它同类算法.     

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

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

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

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

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

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

Contention-aware scheduling with task duplication

Finding an efficient schedule for a task graph on several processors is a trade-off between maximising concurrency and minimising interprocessor communication. Task duplication is a technique that has been employed to reduce or avoid interprocessor communication. Certain tasks are duplicated on several processors to produce the data locally and avoid the communication among processors. Most of the algorithms using task duplication have been proposed for the classic scheduling model, which allows concurrent communication and ignores contention for communication resources. It is increasingly recognised that this classic model is unrealistic and does not permit creating accurate and efficient schedules. The recently proposed contention model introduces contention awareness into task scheduling by assigning the edges of the task graph to the links of the communication network. It is intuitive that scheduling under such a model benefits even more from task duplication, yet no such algorithm has been proposed as it is not trivial to duplicate tasks under the contention model. This paper proposes a contention-aware task duplication scheduling algorithm. We investigate the fundamentals for task duplication in the contention model and propose an algorithm that is based on state-of-the-art techniques found in task duplication and contention-aware algorithms. An extensive experimental evaluation demonstrates the significant improvements to the speedup of the produced schedules.     

改进的异构多处理器的实时任务调度算法研究*

现有的很多调度算法存在时间复杂度过高或调度成功率低的问题。提出一种新的调度算法(HRTSA),提高实时任务的调度成功率。HRTSA首先通过METC策略初始化分簇,降低算法的时间复杂度;再在放置任务时根据处理器的负载均衡进行处理器负载的有效控制;最后通过任务复制调度以提高任务调度成功率。对比实验分析表明提出的HRTSA算法时间复杂度与RTSDA相比较低,调度成功率较高。