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

发布时间：2019-04-29 16:16

【摘要】：异构多核处理器任务调度是高性能计算领域的重要问题。针对优先级列表调度算法中存在的优先级排序方法失当、调度结果不理想的问题,提出一种改进的优先级列表任务调度算法。该算法对传统优先级列表任务调度中以任务执行时间平均值作为参数的优先级计算方式进行优化,提出一种基于异构核性能差异性、依赖任务特征加权优先级的排序方式。在此基础上,以当前格局下每个任务的向后关键路径执行时间为权值作为任务分配到处理器内核的依据,克服贪心思想在内核选择中带来的局部最优解问题。此外,在任务分配阶段利用任务复制和区间插入技术,缩短任务最早开始时间,提高处理器利用率。实例分析和模拟实验结果表明,该算法可有效降低任务的执行时间,能发挥异构多核处理器优势。
[Abstract]:Heterogeneous multicore processor task scheduling is an important problem in the field of high performance computing. In this paper, an improved priority list task scheduling algorithm is proposed to solve the problem that the priority list scheduling algorithm is not suitable and the scheduling results are not satisfactory. This algorithm optimizes the priority calculation method based on the average of task execution time as the parameter in the traditional priority list task scheduling, and proposes a sort method based on the heterogeneous kernel performance difference and depends on the task feature weighted priority. On this basis, taking the execution time of the backward critical path of each task in the current pattern as the weight of the task assigned to the processor kernel, the problem of local optimal solution caused by the greedy idea in the kernel selection is overcome. In addition, the task replication and interval insertion techniques are used in the task assignment phase to shorten the earliest start time of the task and improve the processor utilization. The results of example analysis and simulation show that the proposed algorithm can effectively reduce the execution time of tasks and take advantage of heterogeneous multi-core processors.
【作者单位】：哈尔滨工程大学计算机科学与技术学院;
【基金】：国家自然科学基金(61003036) 黑龙江省基金项目(F201124) Fundamental Research Funds for the Central Universities(HEUCF100606)资助
【分类号】：TP332

【参考文献】