异构多核片上系统的任务调度及应用研究

论文摘要

随着大规模集成电路设计技术和半导体技术的飞速发展,多处理器片上系统（Multiprocessor System-on-Chip, MPSoC）作为各种嵌入式计算系统的核心部件已广泛应用于多媒体网络、通信、高性能计算和工业控制等诸多领域以期进一步提高产品的计算效能,降低其成本、功耗和面市时间。任务调度与分配是多处理器片上系统软件支撑环境研究中的一个关键问题,它将计算任务分配到不同的处理器单元上调度执行,并在满足整个应用系统的实时性、功耗和任务期限等方面约束的情况下最优化执行时间。任务调度与分配决定了软件系统在计算平台上的执行效率与性能,是推动异构多处理器片上系统进一步推广应用的关键。与传统任务调度问题不同,MPSoC系统的异构性、与应用领域结合的特殊性均给这个传统课题的研究带来了新的挑战。本文主要研究多处理器片上系统的实时多帧任务和可重构硬件任务调度相关问题,并基于三种典型的片上系统芯片开发了应用系统实例。嵌入式系统与应用领域密切相关,多帧任务模型正是与多媒体应用领域密切相关的一种实时任务模型。本文首先研究异构多处理器环境下的多帧实时任务调度问题。证明了异构多处理器系统上的多帧实时任务调度问题的难解性。然后从处理器利用率边界和任务响应时间两个方面分析了多帧实时任务的可调度性,给出了调度可判定性的充分条件和充要条件,从理论上分析了多帧任务模型在异构多处理器系统上的优势。以此为基础利用调度可判定性条件,提出了基于遗传算法的异构多处理器多帧实时任务调度算法。模拟实验表明,基于多帧任务模型进行任务描述可以提高实时任务在异构多核处理器系统上的调度成功率。MPSoC中的可重构计算资源增加了系统设计的自由度,但硬件任务的调度算法则需管理实时硬件任务的启动时间和放置位置。文中介绍了可重构硬件任务调度相关定义及系统模型,分析了硬件任务调度产生碎片的原因。由于硬件任务选择放置位置时需要考虑剩余资源空间有利于随后的任务进行布置,本文提出一种基于二维资源模型的分组-邻接边在线调度算法,该算法将硬件任务按照长宽比进行分组并分别考虑在可重构资源上的放置位置。同时引入任务邻接边数作为选择合理放置位置的重要指标,使得硬件任务放置更为紧凑、减少资源碎片、提高调度成功率。模拟实验表明,与已有算法相比,本文算法具有更高的任务接受率,而运行时开销没有明显增加。在对两种硬件任务放置策略进行对比后表明,尽可能早的安排任务启动有利于提升高负载情况下的调度成功率。基于二维可重构资源模型,本文进一步基于整数线性规划方法准确地描述可重构场景下的任务调度问题。为了增加调度算法的实用性,本文考虑了可重构配置预取、模块重用和反碎片技术等与目标平台实现相关的特性,并通过使用更为有效的任务放置策略提高了求解问题的时间效率。其后,本文提出了一种启发式方法解可重构硬件任务调度问题,在获得较好结果的同时大大减少运算时间。仿真实验表明,与类似的调度算法相比,本文的方法在调度质量和运行时间方面均有改进。MPSoC的体系结构经历了从简单的片上集成辅助计算单元,到集成多个可自由编程的处理器,再进一步集成可重构计算资源的不断发展,体现了面向应用领域设计的显著特点。本文基于三种典型片上系统计算平台,面向网络多媒体和数值计算领域设计与实现了移动学习平台、智能视频监控系统和化学分析计量分析专用设备三个应用实例。文中描述了各种计算平台的基本特点、开发流程与方法及系统设计与实现的关键技术,并根据实际应用场景进行了系统部署与评估。实验表明,原型系统达到设计目标并在实际部署中得到了初步的应用。综上所述,本文围绕多处理器片上系统任务调度这个关键问题,依托国家项目,按照“研究基本理论、突破关键技术、实现典型应用”的技术路线,研究了多帧实时任务和可重构硬件任务调度相关问题,并面向实际应用领域设计和实现了三个应用系统,对于进一步推进多处理器片上系统任务调度的研究和实用化以及应用系统开发具有一定的理论意义和应用价值。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 课题研究意义
• 1.2 多处理器片上系统概述
• 1.2.1 体系结构
• 1.2.2 软件支撑系统
• 1.2.3 MPSoC设计挑战
• 1.3 多处理器任务调度
• 1.4 本文的主要工作
• 1.5 论文结构
• 第2章 相关研究
• 2.1 引言
• 2.2 MPSoC任务调度研究进展
• 2.2.1 任务调度算法分析
• 2.2.2 任务调度实现框架
• 2.3 可重构硬件任务调度
• 2.3.1 可重构计算系统
• 2.3.2 硬件任务调度相关研究
• 2.4 MPSoC任务调度亟待解决的问题
• 2.4.1 任务分配、映射与体系结构探索问题
• 2.4.2 任务模型的改进
• 2.4.3 任务迁移等问题
• 2.4.4 调度器的实现
• 2.5 小结
• 第3章 多帧任务在多处理器平台上的调度
• 3.1 引言
• 3.2 相关研究
• 3.3 系统模型与问题的描述
• 3.3.1 系统模型
• 3.3.2 调度问题描述
• 3.3.3 调度问题复杂性
• 3.4 可调度性判定
• 3.4.1 处理器利用率边界
• 3.4.2 响应时间分析
• 3.5 调度算法设计
• 3.5.1 遗传算法设计
• 3.5.2 迭代算法
• 3.6 实验结果与分析
• 3.6.1 实验方案与平台
• 3.6.2 实验结果分析
• 3.7 小结
• 第4章 一种异构可重构片上系统的实时任务调度算法
• 4.1 引言
• 4.2 可重构任务调度模型
• 4.2.1 任务调度模型
• 4.2.2 调度问题描述
• 4.3 分组-邻接边调度算法
• 4.3.1 任务邻接边指标
• 4.3.2 算法描述
• 4.4 分组-邻接边调度算法实例
• 4.5 实验结果与分析
• 4.5.1 仿真实验
• 4.5.2 实验结果分析
• 4.6 小结
• 第5章 基于ILP的二维可重构硬件任务调度
• 5.1 引言
• 5.2 问题的描述
• 5.2.1 器件结构模型
• 5.2.2 任务模型
• 5.3 ILP建模
• 5.3.1 参数说明
• 5.3.2 约束条件
• 5.3.3 调度实例
• 5.4 启发式算法
• 5.5 实验结果与分析
• 5.6 小结
• 第6章 几种MPSoC应用系统设计与实现
• 6.1 引言
• 6.2 基于PXA255的无线多媒体学习平台
• 6.2.1 计算平台结构特点
• 6.2.2 系统设计方案
• 6.2.3 原型系统与评测
• 6.3 基于TI DAVINCI的数字视频监控系统
• 6.3.1 计算平台结构特点
• 6.3.2 系统设计方案
• 6.3.3 原型系统与评测
• 6.4 基于可重构计算的化学计量分析专用系统设计
• 6.4.1 计算平台结构特点
• 6.4.2 系统设计方案
• 6.4.3 原型系统
• 6.5 小结
• 结论
• 1 工作总结和贡献
• 2 工作展望
• 参考文献
• 致谢
• 附录A 攻读学位期间发表的论文和参加的科研工作