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

A Recursive Parallel Scheduling Algorithm Based on Dynamic Critical Path

作　　者：张艳[1] 孙世新[1] 

机构地区：[1]成都电子科技大学计算机学院,610054

出　　处：《系统工程与电子技术》2001年第9期81-86,共6页Systems Engineering and Electronics

基　　金："九五"国防科技预研基金资助课题

摘　　要：并行任务在多处理机系统上的有效调度是获得系统高性能的关键所在。对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.

关 键 词：并行算法 调度程序算法 动态关键路径 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]