|
|
论文:2013,Vol:31,Issue(6):985-990 |
|
|
引用本文： |
|
|
尤涛, 杨凯, 杜承烈, 钟冬, 朱怡安. 基于动态关键路径与边消除的任务复制分配算法[J]. 西北工业大学 |
|
|
You Tao, Yang Kai, Du Chenglie, Zhong Dong, Zhu Yi'an. A Task Duplication Algorithm Based on Dynamic Critical Path and Edge-Zeroing[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 基于动态关键路径与边消除的任务复制分配算法 |
|
| 尤涛, 杨凯, 杜承烈, 钟冬, 朱怡安 |
|
| 西北工业大学 计算机学院, 西安 710072 |
| 摘要: |
| 当前的分布式任务调度算法中,都存在无法得到调度最优解、无法最小化处理器资源的问题。针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,提出了一种基于动态关键路径与边消除的任务复制算法。该算法依据调度长度不增加原则,发展了子节点无约束复制的调度长度不增加定理、子结点带约束复制的调度长度不增加原则、动态关键路径聚簇的调度长度不增加原则,从而缩短了任务的执行时间和占用资源的个数。整个算法流程对任务计算时间与任务间通信时间未做任何限制。通过与相关工作的比较可以看出:DDE算法在调度长度与处理器使用数目上优于其他同类算法。 |
| 关键词:
分布计算系统
任务静态调度
聚簇算法
任务复制
|
|
| A Task Duplication Algorithm Based on Dynamic Critical Path and Edge-Zeroing |
|
| You Tao, Yang Kai, Du Chenglie, Zhong Dong, Zhu Yi'an |
|
| Department of Computer Science and Engineering, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| Task scheduling is critical for a parallel and distributed system.The task duplication and scheduling al-gorithm and other typical algorithms cannot obtain the optimal solutions for scheduling length even under optimal conditions.Moreover, they are constrained by the node selection scope and node execution time scope when alloca-ting nodes, being unable to minimize the number of processors required by the algorithms.To carry out the static scheduling of the related tasks in the parallel and distributed system, this paper proposes the task in the parallel and distributed system, this paper proposes the task duplication algorithm based on dynamic critical path and edge -zeroing, whose main objective is to reduce the number of resources.The algorithm develops the principles that the scheduling length of sub-nodes that are duplicated with no constraints should not increase, that the scheduling length of sub-nodes that are duplicated with constraints should not increase and the scheduling length of dynamic critical path clustering should not increase, thus reducing the task execution time and the number of resources used. The algorithm does not limit the task computing time and the task communication time.The comparison o the task duplication algorithm proposed in the paper with other algorithms show that the former is superior to the latter in terms of scheduling length and number of processors used. |
| Key words:
distributed computer systems
static task scheduling
clustering algorithms
task duplication
|
|
| 收稿日期: 2013-03-05
修回日期:
|
| DOI: |
| 基金项目: 国家高技术研究发展计划863项目(2011AA010102);航空科学基金(20135553034);自然科学基金(61303225);西北工业大学基础研究基金资助 |
| 通讯作者:
Email： |
| 作者简介: 尤涛(1983-),西北工业大学讲师,主要从事分布式数据处理的研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 尤涛 在本刊中的所有文章 |
| 杨凯 在本刊中的所有文章 |
| 杜承烈 在本刊中的所有文章 |
| 钟冬 在本刊中的所有文章 |
| 朱怡安 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Palis M A, Liou J C, Wei D S L. Task Clustering and Scheduling for Distributed Memory Parallel Architectures. IEEE Trans on Parallel and Distributed Systems, 1996, 7(1): 46-5
[2] Ahmad I, Kwork Y K. On Exploit Task Duplication in Parallel Program Scheduling. IEEE Trans on Parallel and Distributed Systems, 1998, 9(9): 872-892
[3] Park C I, Choe T Y. An Optimal Scheduling Algorithm Based on Task Duplication. IEEE Trans on Computers, 2002, 51(4):444-448
[4] Radulescu A, Van Gemund A J C. Low-Cost Task Scheduling for Distributed-Memory Machines. IEEE Trans on Parallel and Distributed Systems, 2002, 13(6): 648-665
[5] Yang T, Gerasoulis A. DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors. IEEE Trans on Parallel and Distributed Systems, 1994, 5(9): 951-996
[6] Bajaj R, Agrawal D P. Improving Scheduling of Tasks in a Heterogeneous Environment. IEEE Trans on Parallel and Distributed Systems, 2004, 15(2): 107-111
[7] Darbha S, Agrawal D P. Optimal Scheduling Algorithm for Distributed-Memory Machines. IEEE Trans on Parallel and Distributed Systems, 1998, 9(1): 87-89
[8] Chen Zhigang, Hua Qiangsheng. EZDCP: A New Static Task Scheduling Algorithm with Edge-Zeroing Based on Dynamic Critical Paths. Journal of Central South University of Technology, 2003, 10(2): 140-144 |
|
|
|
|
|
|
|
