基于异构多核处理器的高效任务调度算法

An efficient task scheduling algorithm for heterogeneous multi-core processors

针对现有异构多核处理器任务调度算法效率低的问题，提出了一种综合性的、高效的静态任务调度算法，即聚簇与复制列表优化调度（CDLOS）算法。该算法首先通过对任务图进行聚簇优化，降低某些特殊任务的通信开销；然后从整个任务图的拓扑结构出发计算任务的优先级权值，提高关键任务的优先级；继而采用区间插入和任务复制技术进行调度，降低处理器资源浪费；最后通过优化调度结果，消除冗余任务，减小整个任务的调度长度。实例分析和模拟实验结果表明：与以往算法相比，此新算法较高地提升了多核处理器任务调度的效率，具有更好的应用前景。

In view of the low efficiency problem of present task scheduling algorithms for heterogeneous multi-core proces- sors, a new efficient static task scheduling algorithm, called the clustering and duplicate list optimization scheduling （CDLOS） algorithm, is proposed. Firstly, this new algorithm optimizes task graphs by using clustering to greatly minimize the communication costs of special tasks. Secondly, the task priority value is calculated in the case of the whole topological structure of task graphs is considered, for giving a higher priority to crucial tasks. Then, the tech- niques of task insertion and task duplication are applied to the process of task scheduling to enhance the efficiency of processor resources. Lastly, the result of task schedule is optimized effectively, so as to reduce the redundant tasks and the makespan of all tasks. The analysis and simulation results show that compared to old scheduling algo- rithms, this new CDLOS algorithm can enhance the task scheduling efficiency obviously and will have excellent ap- plication prospects.