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

• 作者: 张多利 廖金月 罗乐 倪伟 宋宇鲲
• 来源期刊: 电子测量与仪器学报
• 关键词: 静态任务 调度算法 扰动因子 扰动策略 搜索空间
• 年，卷（期）: 2020,（9）
• 所属期刊栏目: 学术论文|PAPERS
• 页码范围: 133-139
• 页数: 7页
• 分类号: TN401
• 语种: 中文
• DOI: 10.13382/j.jemi.B2002911

摘要

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