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

异构多核嵌入式软件关键问题研究

作　者: 蒋建春
导　师: 汪同庆
学　校: 重庆大学
专　业: 仪器科学与技术
关键词: 异构多核处理器操作系统架构任务划分静态调度动态调度
分类号: TP368.12
类　型: 博士论文
年　份: 2011年
下　载: 97次
引　用: 0次
阅　读: 论文下载

内容摘要

如何充分利用异构多核处理器的异构特性,将单核的应用软件快速的移植到多核处理器上以及快速地开发基于多核处理器的应用程序是多核处理器应用中面临的主要问题。而解决这些问题的方法要求主要集中在多核软件等关键技术研究上,只有开发出与异构多核硬件相适应的操作系统及其应用软件,才能真正地发挥异构多核处理器的性能。由于异构多核处理器中不同性质程序在不同内核的执行效率存在差异,且应用系统存在功耗、效率、实时性等要求,这就要求操作系统能够对任务进行有效的管理,如分配调度、通信、同步等,以实现多核处理器的最大化利用。而要实现这些功能必须针对异构多核处理器特点研究和设计相应的操作系统架构、调度算法、通信与同步机制等关键技术。传统的多处理器和分布式计算机与异构多核处理器在架构和通信机制上存在巨大差别,相应的分布式操作系统也不适用于异构多核处理器,特别是在嵌入式系统领域。本课题针对嵌入式系统领域,通过研究异构多核处理器的结构特点,分别在操作系统架构、任务划分、异构核间的任务分配以及同构核间动态任务调度等几个关键问题方面进行了大量深入的研究,主要完成了以下工作:1.研究了异构多核的操作系统架构针对多处理器系统的分布式结构以及应用于同构多核系统的主从式结构操作系统不能解决异构多核处理器的实时调度和效率问题,本课题提出一种适用异构多核处理器的多主模式实时操作系统架构。这种架构将通信总线中的多主模式引入多核操作系统架构中,采用对称式结构及组件模式设计操作系统模型,使多核处理器中每个内核都可以作为主核实现对资源、任务的实时管理,提高系统性能,同时可以解决主从式操作系统存在的由于处理器核增多而带来的主内核不能满足系统性能要求存在的瓶颈问题。通过这种单一架构模型可以进行灵活配置适应不同结构及功能要求处理器内核,降低操作系统开发难度。2.研究了异构多核处理器的任务划分问题任务的调度与任务的属性、粒度、任务之间的关系等因素密不可分。异构多核的任务划分是多目标优化问题,怎样针对具体的任务执行环境进行任务分割,使任务在粒度大小、通信调度花费、并行化处理、负载均衡等方面得到一个有效的综合,从而通过调度获得系统的最大执行效率,是任务划分需要解决的关键问题。本课题从任务本身属性和调度两个方面针对异构多核处理器的任务划分中的重要影响因素进行分类分析,提出一种基于聚合性的微粒群分层任务划分方法,通过参数匹配,获得一个较好的划分结果,从而提高任务调度和执行的效率。3.研究了异构多核处理器的任务静态调度问题在异构多核处理器中,任务有最小最大完成时间、负载均衡、最低功耗等要求,异构环境下的任务分配和作业调度问题往往是局部目标和全局目标是相互制约,不能同时满足,任务静态调度被证明是一个NP-Hard的组合优化问题。本课题针对异构并行系统的作业调度和任务分配问题进行研究,提出一种基于Sufferage启发式算法和DPSO(Discrete Particle Swarm Optimization)算法的混合离散微粒群SDPSO (Sufferage Discrete Particle Swarm Optimization)独立任务分配算法,改进DPSO算法效率和搜索精度。由于实际的任务之间存在耦合性,针对独立任务设计的静态调度算法不能很好解决非独立任务的调度问题。因此,本课题在SDPSO算法的基础上,根据任务划分实际存在的耦合性,研究并提出一种基于耦合性的SDPSO静态任务调度改进算法。4.研究了异构多核中同构核间的任务动态调度问题在异构多核处理器中,有可能存在多个同构核,在这些同构核中的任务除了进行任务的静态分配以外,还存在运行过程中的动态调度问题。在动态调度中主要存在基于任务复制和基于表的动态调度算法,而基于任务复制的动态调度算法对存储空间要求较高不适合实时系统。本课题针对嵌入式系统并行同步任务的实时性要求在动态表的基础上提出一种基于任务划分的最小最大关键点执行时间MMKPT(Min-Max Key Point Time)算法,该算法根据同步任务的同步执行时间点和任务之间的耦合性对就绪任务和执行内核进行选择和调度,以满足嵌入式系统的实时性要求。通过这些关键技术的研究工作及成果,可以为异构多核处理器的实时操作系统的研究与开发提供一些帮助和参考,以促进异构多核处理器的应用推广。

全文目录

中文摘要  3-5
英文摘要  5-11
1 绪论  11-29
  1.1 研究背景及意义  11-16
    1.1.1 多核处理器的发展及应用现状  11-12
    1.1.2 课题的研究意义  12-16
    1.1.3 课题来源  16
  1.2 多核处理器的发展现状  16-20
    1.2.1 多核处理器的分类及发展趋势  16-18
    1.2.2 异构多核处理器的分类和结构  18-20
  1.3 异构多核嵌入式软件关键问题的研究现状  20-24
    1.3.1 操作系统的架构研究  20-21
    1.3.2 任务划分的研究  21-22
    1.3.3 异构多核处理器任务分配和调度研究  22-24
  1.4 本文的研究目标和主要工作  24-28
    1.4.1 本文的研究目标及拟解决的关键问题  24-27
    1.4.2 论文的基本结构  27-28
  1.5 本章小结  28-29
2 异构多核操作系统架构研究  29-49
  2.1 多核操作系统的基本架构  29-34
    2.1.1 常用同构多核操作系统的基本架构分析  29-32
    2.1.2 常用异构多核操作系统的基本架构  32-34
  2.2 基于多主模式的异构多核操作系统架构研究与设计  34-37
    2.2.1 异构多核操作系统设计需求分析  34-35
    2.2.2 多主模式异构多核操作系统设计  35-37
  2.3 操作系统调度机制及核间通信研究与设计  37-43
    2.3.1 任务状态设计  38-39
    2.3.2 基于令牌表的调度机制设计  39-40
    2.3.3 任务的通信与同步机制设计  40-42
    2.3.4 基于共享内存消息机制设计  42-43
  2.4 性能分析  43-47
    2.4.1 调度步骤对比分析  43-46
    2.4.2 调度时间测试  46-47
  2.5 本章小结  47-49
3 异构多核的任务划分方法研究  49-75
  3.1 任务划分的目的及常用方法  49-52
    3.1.1 任务划分目的  49-51
    3.1.2 常用任务划分方法  51-52
  3.2 基于聚合性和耦合性的任务划分方法研究  52-64
    3.2.1 任务划分的聚合性与耦合性关系研究  52-57
    3.2.2 基于聚合性和耦合性的任务划分方法  57-64
  3.3 任务划分的实验分析  64-74
  3.4 本章小结  74-75
4 异构多核任务静态调度研究  75-95
  4.1 任务静态调度目标及常用算法  75-80
    4.1.1 异构多核处理器任务静态调度目标  75-76
    4.1.2 常用任务静态调度算法  76-80
  4.2 基于微粒群算法的独立任务静态调度研究  80-91
    4.2.1 静态任务调度目标函数  81-82
    4.2.2 SDPSO 算法设计  82-88
    4.2.3 仿真实验及结果分析  88-91
  4.3 基于任务划分的非独立任务静态调度算法研究  91-94
    4.3.1 具有耦合性的任务分配存在的问题  91-92
    4.3.2 SDPSO 任务静态调度算法的改进  92-94
  4.4 本章小结  94-95
5 基于任务划分的动态任务调度研究  95-111
  5.1 多核处理器的任务动态调度分析  95-98
    5.1.1 异构多核动态调度的主要目标  95-96
    5.1.2 常用的多核动态调度算法  96-98
  5.2 基于任务划分的动态调度算法研究  98-106
    5.2.1 异构多核处理器任务动态调度特点  98-99
    5.2.2 任务的完成时间分析  99-100
    5.2.3 基于任务划分的同步任务动态表调度算法  100-106
  5.3 算法分析与测试  106-110
  5.4 本章小结  110-111
6 结论与展望  111-115
  6.1 论文所做的主要工作和创新点  111-112
  6.2 未来的工作展望  112-115
致谢  115-117
参考文献  117-127
附录  127-128
  A. 作者在攻读学位期间取得的科研成果  127
  B. 作者在攻读学位期间发表的论文  127-128

异构多核嵌入式软件关键问题研究

内容摘要

全文目录

相似论文