异构多核系统中面向细粒度任务集的调度算法研究

摘要

随着异构多核处理器的快速发展，异构多核系统中的任务调度成为研究热点。目前，适用于普通任务集调度的算法在调度细粒度任务集时，存在处理器负载失衡，处理器空闲时间多，并行性差和冗余任务等诸多缺陷，严重影响了多核系统的性能。本文针对这些问题展开研究。
　　 结合聚簇、列表和复制算法各自的优势，本文提出了一种高效的适合细粒度任务集的调度算法HCDUL，HCDUL分为聚簇、优先级计算和就绪任务列表建立、任务调度、复制上层节点四个阶段。通过聚簇降低了通信开销，调度过程中动态更新就绪列表，并实时对其排序，关键任务有最高的优先级；每次取列表头节点，并调度到完成时间最小的处理器核上；利用当前节点之前的空闲时间段复制上层节点，进一步减小通信开销，提前子任务的开始时间，从而缩短整个任务集的完成时间。
　　 针对复制算法存在冗余任务问题，本文提出了一种优化算法HDO。首先，查找并删除冗余任务，然后计算冗余任务后继节点的开始时间，最后调整后继节点。通过消除冗余任务，提前了后续节点开始时间，节省了处理器资源，并进一步缩短了调度长度。
　　 本文使用随机生成图进行了大量实验，在调度细粒度任务集时，与HEFT和HCNF算法比较，HCDUL算法的调度长度率SLR更小，加速比Speedup更大。同样，使用大量的随机生成图对HDO算法验证，HCNF和HCDUL算法的调度结果经HDO算法优化之后，总执行时间比率SETR更小，并且在一定程度上，调度长度率SLR减小，加速比Speedup增加。