基于动态关键路径与边消除的任务复制分配算法  

A Task Duplication Algorithm Based on Dynamic Critical Path and Edge-Zeroing

作　　者：尤涛[1] 杨凯[1] 杜承烈[1] 钟冬[1] 朱怡安[1] 

机构地区：[1]西北工业大学计算机学院

出　　处：《西北工业大学学报》2013年第6期985-990,共6页Journal of Northwestern Polytechnical University

基　　金：国家高技术研究发展计划863项目(2011AA010102);航空科学基金(20135553034);自然科学基金(61303225);西北工业大学基础研究基金资助

摘　　要：当前的分布式任务调度算法中,都存在无法得到调度最优解、无法最小化处理器资源的问题。针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,提出了一种基于动态关键路径与边消除的任务复制算法。该算法依据调度长度不增加原则,发展了子节点无约束复制的调度长度不增加定理、子结点带约束复制的调度长度不增加原则、动态关键路径聚簇的调度长度不增加原则,从而缩短了任务的执行时间和占用资源的个数。整个算法流程对任务计算时间与任务间通信时间未做任何限制。通过与相关工作的比较可以看出:DDE算法在调度长度与处理器使用数目上优于其他同类算法。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 .

关 键 词：分布计算系统 任务静态调度 聚簇算法 任务复制 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]