学位论文 > 优秀研究生学位论文题录展示

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

作　者: 王立东
导　师: 徐成
学　校: 湖南大学
专　业: 计算机科学与技术
关键词: 周期任务异构多核系统多帧任务模型分配问题遗传算法
分类号: TP332
类　型: 硕士论文
年　份: 2009年
下　载: 87次
引　用: 2次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  5-6
Abstract  6-8
目录  8-10
插图索引  10-11
附表索引  11-12
第1章绪论  12-19
  1.1 研究背景和意义  12
  1.2 异构多核任务分配问题研究概况  12-16
    1.2.1 研究现状和发展趋势介绍  12-15
    1.2.2 涉及的关键问题  15-16
  1.3 论文的主要工作和论文结构  16-18
  1.4 小结  18-19
第2章异构多核任务分配相关研究  19-26
  2.1 任务分配问题的数学描述  19-23
    2.1.1 异构多核任务分配  19-20
    2.1.2 多帧实时任务  20-21
    2.1.3 一般性实时任务  21-23
  2.2 异构多核任务分配的非线性规划描述  23-24
    2.2.1 非线性规划相关概念  23
    2.2.2 问题的非线性规划描述  23-24
  2.3 遗传算法  24-25
    2.3.1 遗传算法简介  24
    2.3.2 遗传算法基本操作和流程  24-25
  2.4 小结  25-26
第3章异构多核多帧任务模型与分配算法研究  26-37
  3.1 异构多核多帧任务模型  26-33
    3.1.1 模型描述  26-29
    3.1.2 模型性质  29-33
  3.2 算法设计  33-36
    3.2.1 遗传算法要素  33-35
    3.2.2 遗传算法设计  35-36
    3.2.3 算法分析  36
  3.3 小结  36-37
第4章异构多核任务分配评估系统  37-50
  4.1 系统说明  37-38
  4.2 遗传算法  38-42
    4.2.1 随机产生一个任务集  39
    4.2.2 随机产生多个任务集  39
    4.2.3 MT 文件格式说明  39-41
    4.2.4 文件读取一个任务集  41-42
    4.2.5 文件读取多个任务集  42
  4.3 Matlab 两步法  42-44
    4.3.1 Matlab 引擎介绍  42-43
    4.3.2 fgoalattain 函数简介  43-44
    4.3.3 两步法流程  44
  4.4 模拟实验  44-49
    4.4.1 实验方法  44-45
    4.4.2 不同系统规模下对比帧差别影响  45-47
    4.4.3 算法时间和结果  47-49
  4.5 小结  49-50
第5章非AM 异构多核任务模型和分配算法研究  50-61
  5.1 一般异构多核任务集  50-54
    5.1.1 AM 异构多核多帧任务转化  50-53
    5.1.2 一般异构多核任务模型  53-54
  5.2 算法设计  54-56
    5.2.1 遗传算法要素  54-55
    5.2.2 遗传算法设计  55
    5.2.3 算法分析  55-56
  5.3 实验分析  56-60
    5.3.1 实验方法  56
    5.3.2 不同系统规模下对比帧差别影响  56-59
    5.3.3 算法时间和结果  59-60
  5.4 小结  60-61
总结与展望  61-63
  1 本文工作总结  61-62
  2 展望  62-63
参考文献  63-67
致谢  67-68
附录A 攻读学位期间发表的学术论文  68-69
附录B 攻读学位期间所参与的研究项目  69

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

内容摘要

全文目录

相似论文