首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 125 毫秒
1.
调度Fork-Join任务图的贪心算法   总被引:3,自引:2,他引:1  
任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题.虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题.Fork-Join结构是一种并行处理的基本结构.因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少.  相似文献   

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

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

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

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

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

7.
针对异构总线网络提出了一种动态实时可分性负载调度方法.首先,根据可分性负载调度最优性原理,分析了网络中处理器负载分配的最优次序以及参与计算的处理器数目;然后,针对实时任务的截止期限约束提出一种动态负载分配算法,该算法可以利用网络中最少的处理器数目,保证实时任务在其截止期限之前计算完成.理论分析和仿真测试都验证了所提出算法的有效性.  相似文献   

8.
随着多核处理器体系结构在计算机领域的广泛应用,如何合理地对计算任务进行调度成为人们广泛讨论的问题。目前已经有针对多处理器的任务调度算法,但是这些算法在执行时要经过多次迭代,执行效率比较低。提出一种改进的波前调度算法MEWFM,它是一种执行时间短,加速比接近处理器核数的一种算法。这种算法主要包括任务图分层,层内调度和误差下降调度三个子算法。详细分析了这些算法的特点和执行流程。实验评测表明,算法在多处理器环境下的任务调度方面具有执行速度快,性能高等优势。  相似文献   

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

10.
在非对称多核处理器上进行任务调度时,现有的操作系统调度器没有考虑其非对称性.针对单一指令集非对称多核处理器上的操作系统调度问题,首先建立线性规划模型,分析各种因素,得出行为匹配、减少迁移和负载均衡的调度原则.然后,基于调度原则提出一种综合性调度算法.该算法包括两个部分:1) 集成负载表征,提出集成行为的概念,全面衡量任务的整体性和阶段性行为;2) 基于集成行为的调度算法,有效开发非对称多核处理器的特性,能够保证各核心负载均衡,同时可以避免不必要的任务迁移.另外,该算法通过参数调整机制实现了算法的通用性.该算法是一种综合处理任务的整体性和阶段性行为,并具备通用性的调度算法.实际平台上的实验结果表明,该算法可通用于多种环境,且性能比其他对应算法提高6%~22%.  相似文献   

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

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

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

14.
We address scheduling independent and precedence constrained parallel tasks on multiple homogeneous processors in a data center with dynamically variable voltage and speed as combinatorial optimization problems. We consider the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on multiple processors. Our approach is to use level-by-level scheduling algorithms to deal with precedence constraints. We use a simple system partitioning and processor allocation scheme, which always schedules as many parallel tasks as possible for simultaneous execution. We use two heuristic algorithms for scheduling independent parallel tasks in the same level, i.e., SIMPLE and GREEDY. We adopt a two-level energy/time/power allocation scheme, namely, optimal energy/time allocation among levels of tasks and equal power supply to tasks in the same level. Our approach results in significant performance improvement compared with previous algorithms in scheduling independent and precedence constrained parallel tasks.  相似文献   

15.
The Garey–Johnson algorithm is a well known polynomial-time algorithm constructing an optimal schedule for the maximum lateness problem with unit execution time tasks, two parallel identical processors, precedence constraints and release times. The paper is concerned with the worst-case analysis of a generalization of the Garey–Johnson algorithm to the case of arbitrary number of processors. In contrast to other algorithms for the maximum lateness problem, the tight performance guarantee for the even number of processors differs from the tight performance guarantee for the odd number of processors.  相似文献   

16.
We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961; however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m-2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum  相似文献   

17.
一种新的分布式控制系统容错调度算法   总被引:3,自引:3,他引:0       下载免费PDF全文
目前多数容错调度算法在调度非周期任务时采用预留时间的方法,非周期任务无法得到充分响应。针对该问题,提出一种新的分布式控制系统容错调度算法,采用任务集划分的方法在不同处理机上运行不同的周期任务子集,使每个处理机具有不同的非周期任务预留时间,当非周期任务发生时,即可得到有效响应。结果表明,该方法能提高容错调度的效率。  相似文献   

18.
An algorithm has been developed to dynamically schedule heterogeneous tasks on heterogeneous processors in a distributed system. The scheduler operates in an environment with dynamically changing resources and adapts to variable system resources. It operates in a batch fashion and utilises a genetic algorithm to minimise the total execution time. We have compared our scheduler to six other schedulers, three batch-mode and three immediate-mode schedulers. Experiments show that the algorithm outperforms each of the others and can achieve near optimal efficiency, with up to 100,000 tasks being scheduled  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号