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

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

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

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

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

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

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

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

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

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

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

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

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

并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法

现代嵌入式系统正在向使用多核或多处理器进行并行处理的方向发展.针对并行嵌入式系统中具有通信竞争情况下的任务调度问题,文中提出3项高级技术以提高列表调度方法的性能.首先使用5组(已存在的两组和新提出的3组)节点等级作为节点优先权来生成节点列表;然后使用关键子节点技术来改善调度过程中处理器的选择;最后使用通信延迟技术扩大通信连接线上的空闲时间区间.文中还给出了组合使用这3项技术的高级动态列表调度方法.实验结果表明,在中等通信代价和高通信代价的情况下,组合高级动态方法能够有效地缩短调度长度,可以在通信代价很高时通过优化使用硬件资源使调度结果加速高达80%.     

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

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

基于QoS的任务分类调度算法

分析了QoS Guided Min-Min及其改进算法,指出了这些算法调度不均衡的缺点.在此基础上设计出基于QoS的任务分类调度算法.先对特殊任务使用Min-Min方法进行调度,然后采用贪心策略对一般任务进行调度,转移或交换最大负载和最小负载机器上的一般任务,使各机器上的任务快速达到均衡.实验表明该算法在保证应用QoS的前提下,相对于以往算法负载分布更加均衡,任务总的完成时间更短.     

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。     

Communication contention in APN list scheduling algorithm

Task scheduling is an essential aspect of parallel process system. This NP-hard problem assumes fully connected homogeneous processors and ignores contention on the communication links. However, as arbitrary processor network (APN), communication contention has a strong influence on the execution time of a parallel application. This paper investigates the incorporation of contention awareness into task scheduling. The innovation is the idea of dynamically scheduling edges to links, for which we use the earliest finish communication time search algorithm based on shortest-path search method. The other novel idea proposed in this paper is scheduling priority based on recursive rank computation on heterogeneous arbitrary processor network. In the end, to reduce time complexity of algorithm, a parallel algorithm is proposed and speedup O(PPE) is achieved. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm significantly surpasses classic and static communication contention awareness algorithm, especially for high data transmission rate parallel application. Supported by the National Natural Science Foundation of China (Grant Nos. 90715029 and 60603053), the Cultivation Fund of the Key Scientific and Technical Innovation Project, Ministry of Edacation of China, and the Key Project of Science & Technology of Hunan Province (Grant No. 2006GK2006)     

一种基于遗传算法的网格任务调度算法

任务调度算法是网格计算研究的一个重要方向,已被证明是一个NP完全问题。提出了一种新的网格任务调度算法。该算法基于遗传算法,为加快算法的收敛速度,在生成初始种群时优先分配关键路径上的任务;由于资源间存在着通信延迟,引入任务复制方法,并结合遗传操作控制任务复制的深度,可以减少任务之间的通信开销,缩短整个调度的完成时间;最后进行优化操作,减少冗余的任务复制。模拟实验结果表明,该算法在收敛速度和调度完成时间均优于普通遗传算法。