基于周期任务的异构多核多帧任务分配算法研究

发布时间：2020-09-11 13:56

　　任务调度问题是计算机科学研究的基本课题,多核系统的出现为任务调度问题带来了新的变化。多核系统的任务调度问题首先考虑能否在保证任务得以完成情况下,寻求分配方案使得处理器繁忙程度平均,这也称为任务的分配问题。该问题在异构多核系统中更为复杂。在异构系统的任务分配问题中需要综合考虑处理器的异构特性,使得各处理器各尽所能,任务各取所需。当前在异构多核任务分配的研究中对经典的周期任务研究较为深入,但这些研究并没有关注具有多帧性质的任务,导致在分析中使用任务的单一最大处理时间,悲观的误判某些可以分配的任务集不能分配。本文从经典的周期任务入手,在研究当前异构多核任务分配的流行算法基础上,将多帧性质应用于异构多核系统,建立新的任务模型:异构多核多帧任务模型。该模型具有更全面的描述能力,集中体现了计算系统的异构性和任务的多帧性。利用非线性规划的描述方法证明新模型的优势,并借助遗传算法进行验证。首先对于具有AM(累积单调)性质的异构多核多帧任务,从理论上分析新模型的优势,即能分配更多任务,其后设计遗传算法进行解决。为验证理论结果和算法性能,同时针对异构多核研究没有统一平台的问题,本文设计了一个易于扩展的异构多核任务分配评估系统,实现文中使用的两种方法:遗传算法和Matlab两步法。本文基于该系统进行AM异构多核多帧任务的模拟实验。在此基础上,对一般异构多核实时任务进行了讨论,使得模型具有更广泛的应用范围。给出了一般异构多核任务的相似理论分析和遗传算法设计,通过模拟实验证实模型的可用性,以及更全面的体现任务。理论分析和实验结果表明,考虑了多帧特性的异构多核任务模型较悲观的使用最大处理时间的任务分配方法可以成功分配更多任务,更全面的表现任务性质。遗传算法的设计简单实用,在较短的时间内即能获得很好的结果,移植性好,具有一定的应用价值。
【学位单位】：湖南大学
【学位级别】：硕士
【学位年份】：2009
【中图分类】：TP332
【部分图文】：

主界面,任务集,可分配性,帧差

图 4.1 HTES 主界面对两个模块分别进行介绍。算法算法需要具备的功能包括：单个任务集的可分配性测试。S 随机产生任务集，对该任务集的可分配性以及分配结果进行个任务集的分配成功率计算。随机产生的多个任务集中可分配的比例；不同帧差别下的单个任务集可分配性。定的一个任务集，改变其帧差别的大小，考察可分配性的变化个任务集的分配成功率对比。定的多个任务集，改变其帧差别大小，考察可分配比例的变化 HTES 在遗传算法（简称 GA）下设计四个子功能：随机产生

曲线,成功率,帧差,多帧

有 124 组任务不能分配。考虑多帧，使用 FRM 进行分配，帧差别范围[5,10],[10,50]和[50,100]分别可以分配这 124 组任务中的 103，110 和 112 个。由此得到三组 RPSP 的变化情况，结果如图 4.7 所示：图 4.7 m=2 相对分配成功率图 4.7 横坐标为任务个数，表示在两个处理器的异构系统中需要分配的任务数目，纵坐标为相对分配成功率 RPSP。三组曲线分别表示任务帧差别产生范围在[5,10],[10,50]和[50,100]的情况。由图 4.7 可知，对比不考虑多帧，三组曲线均可多分配至少 60%的任务集，说明了新模型在提出帧差别后带来的分配成功率提高，验证了理论分析的正确性。同时在图 4.7 中，三组曲线[50,100]最高，基本维持在 90%左右

曲线,成功率,异构处理器,分析算法

c） d）图 4.8 m=4,6,8,10 相对分配成功率以上五组实验都表现出高的帧差别范围曲线较高，说明了理论分析的正确性。4.4.3 算法时间和结果为分析算法性能，分别使用 HTES 中的 GA 模块和 M-TS 模块分配一组相同的异构多核任务（如图 4.9），系统规模为 10 个异构处理器，25 个任务，利用率范围在[0.00295, 0.495]，对本文算法和文献 [13]进行比较。

【引证文献】