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

【Abstract】 Task scheduling is critical for a parallel and distributed system. The task duplication and scheduling algorithm 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 allocating 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 edgezeroing,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.更多还原