基于任务复制与冗余消除的多核调度算法

在分布式计算中常把任务之间的协同和通信关系转换为任务图模型,而任务调度是决定分布式计算性能的关键因素之一。为解决OSA、TDCS、RECS等传统经典算法处理器个数消耗多且存在大量冗余任务等问题,提出一种改进的任务图调度算法。该算法基于贪心策略复制任务的前驱以及前驱的前驱,减少调度长度和处理器空闲时间,并在不增加调度长度的前提下,通过合并簇及减少冗余任务降低处理器个数和处理器的负载。实验结果表明,该算法在处理器个数、加速比以及冗余任务比率上都有一定程度的优化,能提升分布式计算性能。     

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

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

基于任务复制的处理器预分配算法

基于任务复制的调度算法比无任务复制的调度算法具有较好的性能．文章在分析了基于任务复制的几个典型算法(如TDS，OSA等算法)及其假设条件后，提出了以使调度长度最短作为主要目标、减少处理机数目作为次要目标的处理器预分配算法PPA．该算法对任务计算时间与任务间通信时间未做任何限制(即不考虑任务粒度)．通过与相关工作的比较可以看出：PPA算法在调度长度与处理器使用数目上均优于其它算法或与其它算法相当，同时，该算法具有与TDS，OSA相同的时间复杂度．这对嵌入式实时分布系统具有重要的意义。     

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

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

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

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

一个调度Out-Tree任务图的新算法

Out-Tree任务图代表分治算法的一大类问题。本文专门针对该类任务图，提出了一个新的调度算法。它利用fork结构的最优调度为各任务定义优先级，准确的反映了任务对调度的影响，保证了任务的正确调度顺序，得到优的调度长度。并在不改变调度长度的情况下，将结点尽可能地分配到已用处理器上，节省了处理器。实验表明，本文算法的调度性能优于现有同类算法。     

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

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

基于异构多核处理器的静态任务调度研究

针对现存任务调度算法优先级选取过于单一、冗余任务处理较晚的问题,提出一种基于加权优先级的任务调度算法--WPTS算法.该算法综合考虑任务3个属性的加权值以决定任务被处理的先后次序,从而克服了任务选取时的单一性问题.在将任务分配到处理器的过程中,保证任务优先调度到完成时间最早的处理器上.同时,引入冗余任务处理过程,及时消除冗余任务,达到对处理器空闲时间段进行有效回收、减少处理器调度长度的效果.性能对比实验表明,WPTS算法较CPFD算法、HCPFD算法和HDEFT算法能取得更好的性能.     

一种调度In-Tree任务图的算法

In-Tree任务图可用来表示归并、求和等分治算法的很多问题,该文针对这种任务图提出一种分层调度算法,利用队列存放被调度的任务,在同层任务调度中,优先把前驱不为空的任务调度到其一个前驱处理器上执行,只有前驱为空的任务才考虑是否分配新的处理器。实验表明,与以前的算法相比,该算法在调度长度相当的情况下,使用了更少的处理器。     

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

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

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

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

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

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

基于多核处理器的关联任务并行感知调度算法

关联任务在多核处理器上并行调度所产生的通信时延,会对任务调度长度和处理器利用率造成负面影响,为了改善多核系统对关联任务的处理性能,针对关联任务在多核处理器上的调度特点,提出一种并行感知调度算法。计算各任务与终点间的最长路径值,按照该值的降序来分配任务调度次序,在分配处理器内核时兼顾关联度和任务最早可执行时间,设置最佳匹配评价函数。实验结果表明,与busHEFT和DTSV算法相比,该算法具有更短的任务调度时延、更少的通信量以及更高的处理器利用率。     

A high performance algorithm for static task scheduling in heterogeneous distributed computing systems

Effective task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems (HeDCSs). However, finding an effective task schedule in HeDCSs requires the consideration of both the heterogeneity of processors and high interprocessor communication overhead, which results from non-trivial data movement between tasks scheduled on different processors. In this paper, we present a new high-performance scheduling algorithm, called the longest dynamic critical path (LDCP) algorithm, for HeDCSs with a bounded number of processors. The LDCP algorithm is a list-based scheduling algorithm that uses a new attribute to efficiently select tasks for scheduling in HeDCSs. The efficient selection of tasks enables the LDCP algorithm to generate high-quality task schedules in a heterogeneous computing environment. The performance of the LDCP algorithm is compared to two of the best existing scheduling algorithms for HeDCSs: the HEFT and DLS algorithms. The comparison study shows that the LDCP algorithm outperforms the HEFT and DLS algorithms in terms of schedule length and speedup. Moreover, the improvement in performance obtained by the LDCP algorithm over the HEFT and DLS algorithms increases as the inter-task communication cost increases. Therefore, the LDCP algorithm provides a practical solution for scheduling parallel applications with high communication costs in HeDCSs.     

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.