基于任务分裂的多核平台实时任务调度研究

发布时间：2017-05-24 22:10

  本文关键词：基于任务分裂的多核平台实时任务调度研究，由笔耕文化传播整理发布。

【摘要】：近年来,随着多核平台在市场上的激增,研究热点逐渐转移到执行复杂、计算密集型的任务上,而多核处理器的复杂性往往会使任务行为不统一、不可预测,变化性极大。由于许多任务间可能存在约束性依赖关系,任务分配变得不协调,导致互相等待而错过期限超时。因此,基于独立任务的传统实时任务调度理论面临着巨大的挑战,考虑到依赖任务集合的调度算法越来越成为研究的新方向。 本文在分析和研究国内外现有多核平台实时任务调度算法的基础上,在分区调度和全局调度之间找到了折中点,提出了一种基于任务拆分的多核平台实时任务调度的策略TDTD/TS (Tree Dependent Task Dispatching/Task Splitting)并且设计和实施了该策略的算法。该策略构建于多核平台上的混合实时任务(依赖和非依赖任务)之上,鉴于实时应用中严格时间保证的共性需求,综合考虑任务的动态性和依赖性对系统性能的影响。采用层次调度的方式设计本方案,具体方法分为两个阶段：TDTD (TreeDependent Task Dispatching,多叉树依赖任务分配)和TDTS (Tree Dependent Task Split,多叉树依赖任务分裂)。TDTD将依赖任务转换成一系列的连续作业,通过多叉树任务模型获取相互关联的子任务路径,以及相应的最后期限,对任务分配,建立任务表；TDTS算法中,本地调度程序会根据任务表来分配给任务处理器内核使用权,空闲等待状态的依赖任务进行分裂,所有被阻止的子任务抢占CPU立即执行保证期限。与已有算法相比,本算法具有明显优势,任务集合对处理器利用率边界可达到69.31%。 通过仿真软件gem5和实验机上进行性能测试,并与已有算法进行对比,对协议进行可调度性和实时性QOS性能分析,在时间比率、调度下界比SLR (Schedule Length Ratio)和加速比Speedup方面表现优异,结果证明TDTD/TS提供了更高的效率和扩展性,具有相对的优越性。
【关键词】：实时调度 多核平台 任务依赖 任务分裂
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP332
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-13
• 1.1 研究背景与意义8
• 1.2 国内外研究现状8-11
• 1.3 论文主要工作11-12
• 1.4 论文组织结构12-13
• 2 多核实时任务调度综述13-21
• 2.1 多核处理器13-15
• 2.1.1 多核处理器分类13-14
• 2.1.2 多核处理器特点14-15
• 2.2 实时调度技术15-17
• 2.2.1 实时任务分类15-17
• 2.2.2 实时任务调度算法17
• 2.3 多核调度策略17-20
• 2.3.1 多核调度算法分类17-19
• 2.3.2 多核调度算法评估19-20
• 2.4 小结20-21
• 3 基于任务分裂的多核平台实时任务调度策略21-35
• 3.1 策略概述21-24
• 3.1.1 应用场景21-22
• 3.1.2 实现目标22-23
• 3.1.3 总体设计23-24
• 3.2 符号定义与建模分析24-27
• 3.2.1 系统模型24-25
• 3.2.2 任务DAG与多叉树25-26
• 3.2.3 依赖任务模型26-27
• 3.3 基于多叉树的任务分配算法27-31
• 3.4 运行时依赖任务分裂调度算法31-34
• 3.5 小结34-35
• 4 算法性能分析35-41
• 4.1 可调度性分析35-40
• 4.2 复杂度分析40
• 4.3 小结40-41
• 5 仿真实验与性能测试41-55
• 5.1 仿真工具与数据集41-44
• 5.1.1 gem5多核仿真器41-42
• 5.1.2 SPLASH-2 Benchmark42-44
• 5.2 实验与测试过程44-54
• 5.2.1 参数与指标44-46
• 5.2.2 仿真实验46-51
• 5.2.3 案例测试51-54
• 5.3 结果讨论54
• 5.4 小结54-55
• 结论55-56
• 参考文献56-59
• 攻读硕士学位期间发表学术论文情况59-60
• 致谢60-61

【参考文献】

中国期刊全文数据库 前2条

1 陈芳园;张冬松;王志英;;异构多核处理器体系结构设计研究[J];计算机工程与科学;2011年12期

2 王建红;晏立;;多处理器EPDFPfair算法的可调度性判定[J];计算机工程与应用;2013年01期

中国博士学位论文全文数据库 前2条

1 杨志邦;一类异构多处理器片上系统任务调度算法研究与应用[D];湖南大学;2012年

2 耿晓中;基于多核分布式环境下的任务调度关键技术研究[D];吉林大学;2013年

  本文关键词：基于任务分裂的多核平台实时任务调度研究，由笔耕文化传播整理发布。

，

本文编号：392119