一种多核系统任务扰动迭代算法

任务调度问题是多核处理器相关技术的一个重要组成部分。基于列表的调度算法因其低复杂度和高效率得到广泛关注,但确定任务优先级列表方法的单一性使得算法对解空间搜索不够,易陷入局部最优。为此,提出一种基于任务扰动的迭代型列表调度算法(task perturbation iteration algorithm, TPIA)。该算法通过选取任务扰动因子按照一定扰动策略进行调度列表迭代,对迭代后的列表进行贪心选择,生成更优的调度列表序列以得到更好的调度结果。通过实例和随机有向无环图(DAG)有限集对算法进行验证,结果表明算法能有效改善调度解,调度性能提升平均可达16.51%,适宜处理大规模、高出入度的复杂DAG图;针对TPIA算法在低任务总数高通讯开销情况下性能有所下降的问题,对平均任务节点数130以下的任务图进行分组测试,获得了对应的CCR上界值及其变化趋势。