一种多核系统改进型列表调度算法

在任务调度领域,基于列表的任务调度算法被广泛应用。经典列表调度算法在节点排序阶段会对权值一致的任务节点进行随机排序,但这种节点排序方式过于粗糙,难以取得较好效果。针对这一缺陷,文中提出了一种改进型列表调度算法,通过特殊列表片段将权值一致的任务整合到一起,并对特殊列表片段的调度解空间进行遍历,以迭代产生更优的调度列表获得更好的调度效果。随机DAG图测试结果表明,提出的算法调度效果优异,算法平均增强比最高可达15.3%,不仅适用于多种任务图规模,且在CCR和平均出入度较高的情况下有更好的调度性能。

A Multicore System Improved List Scheduling Algorithm

The list-based task scheduling algorithm has been widely used in the field of task scheduling. The classic list scheduling algorithm randomly sorts the task nodes with the same weight in the node sorting stage. But the sorting method is rough and difficult to achieve better results. In view of this defect, this study proposed an improved list scheduling algorithm. This algorithm integrated tasks with consistent weights through special list fragments, and traversed the scheduling solution space of special list fragments to iteratively generate better scheduling lists to obtain a better scheduling results. The results of random DAG graph test showed that the proposed algorithm had excellent scheduling effect, and the average algorithm enhancement ratio was up to 15.3%, indicating the proposed method was not only suitable for multiple task map scales, but also had better scheduling performance under the condition of higher CCR and higher average access.