A Task Scheduling Algorithm for Multi-core Processors
A Task Scheduling Algorithm for Multi-core Processors
复制标题
一种多核处理器的任务调度算法
DOI：
10.1109/pdcat.2013.47
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Xiaojiang Du
中科院分区：
文献类型：
--
作者：
Xuanxia Yao;P. Geng;Xiaojiang Du
随着多核处理器的广泛应用，多核处理器的任务调度成为一个热点问题。人们从不同的角度对任务调度进行了大量的研究。针对现有的任务调度算法存在处理器利用率低、复杂度高等缺点，提出了一种基于优先级队列和任务复制的多核处理器任务调度算法。在该算法中，有向A循环图（DAG）被用来建立一个任务模型。该模型以任务关键度、任务提醒次数、任务执行时间和平均通信时间为优先级度量。通过综合分析和计算各任务的优先级，建立了基于优先级的任务调度表。然后采用间隔插入和任务复制策略将任务映射到处理器上，减少了通信开销，提高了处理器利用率，缩短了调度长度。实验结果表明，该算法比现有的调度算法具有更好的性能和更低的复杂度。
With the widespread use of multi-core processors, task scheduling for multi-core processors has become a hot issue. Many researches have been done on task scheduling from various perspectives. However, the existing task scheduling algorithms still have some drawbacks, such as low processor utilization rate, high complexity, and so on. This paper presents a task scheduling algorithm for multi-core processors, which is based on priority queue and task duplication. In the proposed algorithm, the Directed A cyclic Graph (DAG) is used to build a task model. Based on the model, task critical degree, task reminder, task execution time and the average communication time are all considered as the priority metrics. A priority based task dispatching list is set up by comprehensive analysis and calculating the priority for each task. Then interval insertion and task duplication strategies are employed to map tasks to processors, which can decrease the communication cost, improve the processor utilization rate and shorten the schedule length. Our experiments show that the proposed algorithm has better performance and lower complexity than the existing scheduling algorithms.