一种改进的基于任务复制的多核调度算法

Improved multi-processor scheduling algorithm based on tasks duplication

在多核系统中,任务调度是决定系统性能的关键因素之一。为优化任务调度,基于一些典型的任务调度算法(如PPA,徐成提出的算法等),提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序,而且进行两个阶段的复制,从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间;另一方面,通过去除不影响任务系统调度长度的冗余簇,然后进行簇之间的合并,以减少处理机的数目和调度长度。实验表明,改进后的算法在任务调度的性能上优于典型算法。

In the multi-processor system, task scheduling is one of the key factors which decide the performance of system. In order to optimize the task scheduling, this paper proposes a new task scheduling algorithm based on some typical algo-rithms（e.g., PPA, the algorithm which is put forward by XU Cheng etc.）. On the one hand, the algorithm establishes reason-able order to duplicate precursor task, and two stages of replication, which can duplicate more precursor task to reduce scheduling length and spare time. On the other hand, the algorithm removes redundant clusters which don’t affect the sched-uling length of the task system, then carries on the merger between clusters to reduce the number of the processor and scheduling length. Simulation results show that the improved algorithm on the performance of task scheduling is superior to the above typical algorithms.