一种基于动态关键路径的递归并行调度算法

A Recursive Parallel Scheduling Algorithm Based on Dynamic Critical Path

并行任务在多处理机系统上的有效调度是获得系统高性能的关键所在。对BNP(BoundedNumberPro cessors)调度问题 ,提出了一种新的基于动态关键路径的递归调度算法 ,对调度节点进行递归选择 ,并结合调度节点的后继任务为它选择了最佳时间槽。该算法克服了已有调度算法不能保证对动态关键任务进行最早调度这一缺点 ,优于现有BNP调度算法。

An efficient scheduling of parallel tasks onto the processors is vital for achieving a high performance from a parallel computer system. For scheduling problem with bounder number processors, this paper proposes a new recursive scheduling algorithm based on dynamic critical path, it chooses scheduling node in a recursively method, and chooses the best time slot by combining with its subsequence task. This algorithm overcomes the shortcoming of the previously proposed algorithms: they can not guarantee the early schedules for dynamic critical tasks, better than the previously proposed BNP scheduling algorithms.