共查询到20条相似文献,搜索用时 0 毫秒
1.
DAG任务图的一种调度算法 总被引:1,自引:1,他引:1
并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷,提出了一种新的调度算法CPFMBF,它采用的策略是:优先调度关键路径节点,其次调度b-level值大的节点,再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。 相似文献
2.
3.
Out-Tree任务图代表分治算法的一大类问题。本文专门针对该类任务图,提出了一个新的调度算法。它利用fork结构的最优调度为各任务定义优先级,准确的反映了任务对调度的影响,保证了任务的正确调度顺序,得到优的调度长度。并在不改变调度长度的情况下,将结点尽可能地分配到已用处理器上,节省了处理器。实验表明,本文算法的调度性能优于现有同类算法。 相似文献
4.
5.
本文提出一种新的任务调度算法,是利用改进的启发式群聚算法,对MARL-LO算法进行了改进,弥补了MARY-LO算法的不足,并增加了一些动态控制功能,较好地解决了n个处理器的分配问题。 相似文献
6.
在异构计算环境中,有效的任务调度对于获得高性能是十分重要的。现在虽然已经有许多异构处理器调度算法,但它们或者不具有良好的效果,或者算法代价太高。提出了一种新的基于表的调度算法APS。APS利用有向无环图来计算任务优先级,并采用基于调度的策略分配任务到不同处理器,以获得任务最少完工时间。将APS和LMT,HEFT,CPOP算法做比较之后得出:在大多数情况下APS算法都能获得更好性能。 相似文献
7.
8.
9.
一个调度Fork-Join任务图的新算法 总被引:16,自引:1,他引:16
任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明, 相似文献
10.
提出了一个动态的集中式自适应任务调度策略,充分考虑到负载均衡的同时,尽量减少集中调度主机的负担.实验数据证明该任务调度机制能获得良好的效果. 相似文献
11.
Processor specialization has become the development trend of modern processor industry. It is quite possible that this will still be the main-stream in the next decades of semiconductor era. As the diversity of heterogeneous systems grows, organizing computation efficiently on systems with multiple kinds of heterogeneous processors is a challenging problem and will be a normality. In this paper, we analyze some state-of-the-art task scheduling algorithms of heterogeneous computing systems and propose a Degree of Node First (DONF) algorithm for task scheduling of fine-grained parallel programs on heterogeneous systems. The major innovations of DONF include:1) simplifying task priority calculation for directed acyclic graph (DAG) based fine-grained parallel programs which not only reduces the complexity of task selection but also enables the algorithm to solve the scheduling problem for dynamic DAGs; 2) building a novel communication model in the processor selection phase that makes the task scheduling much more efficient. They are achieved by exploring finegrained parallelism via a dataflow program execution model, and validated through experimental results with a selected set of benchmarks. The results on synthesized and real-world application DAGs show a very good performance. The proposed DONF algorithm significantly outperforms all the evaluated state-of-the-art heuristic algorithms in terms of scheduling length ratio (SLR) and efficiency. 相似文献
12.
13.
14.
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 相似文献
15.
云计算是一种新兴的计算模式,倡导一切皆服务.云计算由于能够共享分布在世界各地的计算资源,在大规模计算和数据存储中越来越受到重视.云计算是当前IT工业界、学术界研究的热点领域,云环境中的资源可用性已成为云计算不可忽视的问题.对于云计算,当处理器的处理速度不同,不是一直可用于计算时,可用性成为设计和发展云计算系统的关键需求.根据并行任务图及树形云平台的结构特点,分别讨论了影响并行任务可用性需求和计算资源可用性保障的关键因素,给出一种可用性的量化计算公式.并且通过感知任务“可用性需求”和计算资源“可用性保障”,实现可用性匹配,提出了两种可用性感知的调度算法Afsa和Agsa.模拟实验表明该算法能够改善云环境中资源可用性和可靠性,对提高任务调度的成功率具有实际意义. 相似文献
16.
介绍了一种基于并行测试完成时间的极限定理分析和设计的静态并行测试任务调度算法——TSUL(task scheduler based on UUTs model and limit theorem of parallel test finish time)算法.该算法在设计过程中运用并行测试完成时间的极限定理确定了并行完成所有测试任务所需的极限最短时间,生成的解能够尽量接近或达到问题的最优解.经实例验证,对于静态的并行测试任务调度问题,TSUL算法是一种有效的最优化算法. 相似文献
17.
18.
Triggered by the ever increasing advancements in processor and networking technology, a cluster of PCs connected by a high-speed network has become a viable and cost-effective platform for the execution of computation intensive parallel multithreaded applications. However, there are two research issues to be tackled in the scheduling problem for PC cluster computing: (1) how to reduce the communication overhead of executing a multithreaded application on the cluster; (2) how to exploit the heterogeneity, which is unavoidable in an evolving PC cluster, for the application. In this paper, we propose to use a duplication based approach in scheduling tasks/threads to a heterogeneous cluster of PCs. In duplication based scheduling, critical tasks are redundantly scheduled to more than one machine, in order to reduce the number of inter-task communication operations. The start times of the succeeding tasks are also reduced. The task duplication process is guided given the system heterogeneity in that the critical tasks are scheduled or replicated in faster machines. The algorithm has been implemented in our experimental application parallelization system for generating multithreaded parallel code executable on a cluster of Pentium PCs. Our experiments, using three numerical applications and one protocol processing kernel (multithreading per request), have indicated that heterogeneity of PC cluster is indeed useful for optimizing the execution of parallel multithreaded programs. 相似文献
19.
现有并行遗传算法采用随机方法划分子种群,算法收敛性能不高,并且不可避免的破坏种群的较优模式;为了改进这些缺陷,设计了一种新的多点交叉算子,提出了一种改进的粗粒度并行遗传算法;取资源数为6,任务数为50,种群的规模为60,遗传代数为600;采用相同的控制参数进行仿真实验;仿真实验表明,与传统并行遗传算法相比较,提出的改进算法在收敛速度和寻优空间方面有很大的提升。 相似文献
20.
分布式并行服务器透明性及任务调度研究 总被引:9,自引:1,他引:9
针对当前多服务器系统透明性和任务调度研究中存在的问题,提出一种分布式并行服务器的网络服务透明性实现机制和相应的任务调度算法。该透明性机制修改服务器结点的ARP地址解析协议以及客户端到服务器端的连接和数据请求处理,使得整个服务器系统对外界表现为惟一的VIP地址和VMAC地址;相应的任务调度算法则根据负载和阈值设置将服务器结点分成两个链:有效服务器结点链和过载服务器结点链,然后由量值循环法对有效服务器结点链进行任务调度,在修改Linux内核网卡驱动程序和部分底层网络协议的基础上进行了实现,测试结果表明其具有良好的响应特性和较强的服务能力。 相似文献