基于加速效应的多核系统实时调度模型MAMORTS及其算法研究

研究面向多核的实时调度模型及其算法，基于经典实时调度算法及弹簧调度算法（Elastic scheduling），结合多核处理器上共享Cache的任务之间存在的访存加速效应，提出并建立基于加速效应的面向多核系统的实时调度模型MAMORTS(Mutual Association based Multi-core Oriented Real Time Schedule)，针对一定约束条件下的实时调度任务集给出实时可调度性判定条件，并给出对应算法和验证原型系统。主要研究内容为：（1）典型应用实时任务集并行加速因子的研究；（2）基于加速因子的静态MAMORTS调度模型及其算法；（3）基于任务动态迁移策略的MAMORTS调度模型及其算法。预期研究成果：（1）加速因子分析模型和测量方法；（2）静态和动态MAMORTS的理论模型、调度算法；（3）翔实的测试数据分析和原型系统。

课题的研究内容按具体开展的过程和主要研究结论主要分以下几个阶段说明：.（1）研究并分析Beehive多核处理器的互连结构以及实现技术。Beehive是微软硅谷研究院利用FPGA实现的令牌环结构多核处理器，课题基于Beehive设计与实现了一种采用新型互连结构的多核处理器NewBeehive。相比于Beehive，NewBeehive 将提供共享二级Cache和Cache一致性，并对其中的RISC核进行改进。.（2）针对多核系统中任务并行执行时的相互影响给出一种任务亲和性测试方法，并通过测试任务集对该方法进行验证。针对最短执行时间和RM调度的最坏执行时间拟合对任务亲和性进行应用分析，说明了任务亲和性对于任务在多核中的划分和调度所具有的积极意义，从而在此基础上给出并实现了多核实时调度模型-MAMORTS。实验数据和测试分析表明，该调度模型很好的给出了多核架构下的RM实时调度方法。.（3）给出了一种多核实时系统任务间加速因子的定义和测量方法。实验证明，运行于同一计算系统的相关任务集中，任意两个任务之间存在不同程度的计算加速效应，这种加速效应在实际系统中可以是加速和减速，定量的加速效果可以通过加速因子数值量化给出，对于周期任务集，加速因子的数值在一定范围内。本方法中给出了针对多个任务间（任务数 ）的加速因子的测量方法，采取装载前单独测量的方法，即在实际任务分配前通过测量计算出所有任务之间的加速关系，且保证加速因子的测量结果符合实际的系统运行情况，从而获得性能调优的调度策略。.（4）针对一组确定的任务集，找到了判断这种相关性的通用判定方法，进而可以根据加速因子的数值比较，将任务划分到不同处理器核上，增加正加速因子比例，减少负加速因子比例，对于提高任务可调度性将很有帮助。基于加速因子的多核实时系统任务划分方法针对多核实时系统给出了一种基于加速因子的任务划分方法BF-λ划分方法：这一划分方法是在Best-Fit装箱算法上考虑λ加速因子而得到的一种任务划分方法。对于该划分方法的简单说明：在具有k个处理器核的计算环境中，针对任务数量为n的总任务集S，该方法试图找到一种合适的方案将S划分为k个子集：对于每一个核i(1≤i≤k)，可以分配在该核上可实时调度的任务子集，且所有子集的和为S，则判定任务集S满足该方法的实时可调度条件；否则，判定任务集S不满足该方法的实时可调度条件。