一种改进的优先级列表任务调度算法

Improved Priority List Task Scheduling Algorithm

异构多核处理器任务调度是高性能计算领域的重要问题。针对优先级列表调度算法中存在的优先级排序方法失当、调度结果不理想的问题,提出一种改进的优先级列表任务调度算法。该算法对传统优先级列表任务调度中以任务执行时间平均值作为参数的优先级计算方式进行优化,提出一种基于异构核性能差异性、依赖任务特征加权优先级的排序方式。在此基础上,以当前格局下每个任务的向后关键路径执行时间为权值作为任务分配到处理器内核的依据,克服贪心思想在内核选择中带来的局部最优解问题。此外,在任务分配阶段利用任务复制和区间插入技术,缩短任务最早开始时间,提高处理器利用率。实例分析和模拟实验结果表明,该算法可有效降低任务的执行时间,能发挥异构多核处理器优势。

Task scheduling on heterogeneous multiprocessor is an important problem in the field of high performance computing.The paper proposed an improved priority list task scheduling algorithm to solve the problem that misconduct priority method exists in the task scheduling algorithm and the scheduling result is unsatisfactory.The algorithm improves the traditional priority list of task scheduling method which takes average execution time as parameter to calculate priority of task and proposes a weighted priority method to order the priority of tasks based on heterogeneous multi-core performance difference and dependent task characteristics.And then,the paper proposed a new way to select processor core for task which takes the current situation and backward critical path execution time as weight and overcame the local optimal problem brought by greedy though.Furthermore,at the task allocation stage,the algorithm takes task duplication and interval insertion technique to optimize schedule process and shorten the task earliest start time and improve the processor utilization successfully.The instance analysis and simulation experiments prove the algorithm can reduce the execution time of tasks effectively and give a full play to heterogeneous multi-core processor advantage.