异构多核系统任务调度算法研究

Research on task scheduling in heterogeneous multi-core system

为解决异构多核系统任务调度问题,提出一种混合静态调度算法——HSCGS(hybrid successor concerned genetic scheduling),该算法分为启发式算法和遗传算法2个阶段。第1阶段采用所提出的考虑后继节点的列表启发式调度算法(SCLS)产生一个近似最优的调度结果;第2阶段采用针对调度问题改进的遗传算法IGA(improved genetic algorithm),对第1阶段产生的调度结果进行优化。将SCLS与StarPU相结合,实现一种动态调度算法——DSCLS(dynamic successor concerned list scheduling),通过与StarPU上已有调度算法的对比实验表明了DSCLS算法在运行时间和系统吞吐量两方面的优势。

To solve the heterogeneous multi-core systems task scheduling problem effectively, a novel hybrid static scheduling al- gorithm named HSCGS （hybrid successor concerned genetic scheduling） algorithm was proposed. The algorithm was combined with the heuristic and the genetic scheduling algorithm. In the first phase, a heuristic algorithm named SCLS （successor concerned list heuristic scheduling） was proposed to generate a high quality scheduling result. The second phase implemented an improved genetic algorithm （IGA） for scheduling to optimize the scheduling results of the first phase. A dynamic task scheduling algorithm DSCLS （dynamic successor concerned list scheduling） for the heterogeneous multi-core systems was proposed by combining the SCLS algorithm with the schedule engine of the StarPU. The performance of the DSCLS was illustrated by contrast experiments on a heterogeneous computing system consisting of the CPU and the GPU. The experimental results show that for most of the benchmarks, the DSCLS algorithm has significant advantages in both the application execution time and the system throughput.