分布式多处理器环境下任务调度方法研究

论文摘要

针对操作系统下多任务与大任务的高性能执行的要求,分布式多处理器系统为解决最终问题（多任务与大任务的高性能计算）提供硬件层面上的基础支持,但是,如何将这种硬件能力转变成计算性能的提升,并充分利用分布式并行计算能力,这便需要有高效的适应多任务和大任务高性能执行要求的调度模型。一个好的调度模型能够高效实现任务与计算资源的映射,解决共享资源的竞争问题,实现任务时间跨度的最小化以及提升硬件资源的利用率,这也是当前分布式多处理器系统研究领域所面临的挑战之一。本文针对多任务与大任务的高性能执行的要求,以分布式多处理器系统为目标环境,研究相关性任务调度问题,从任务分解、时间跨度优化、通信竞争、动态优先级计算以及最优虚拟核分配等方面展开研究。在理论上,发现分布式多处理器系统的调度特性与规律,并进行相应的算法设计与实现,在方法上,给出创新的调度模型与算法,解决目前调度算法对于任务相关性考虑不足、以及对分布式多处理器体系结构的考虑不足等问题,给出面向任务执行性能最优的调度方法。在应用上,首先使所给出的新方法应用于操作系统一级或者支撑操作系统的环境上,支持多任务与大任务在分布式多处理器系统上的高度并发,形成透明的多处理器一级的并行高性能计算环境。本文的研究工作和成果主要包括以下四个方面:（1）为解决分布式多处理器系统环境中大任务的高性能并行计算问题,本文设计并实现了面向分布式多处理器系统的任务分解器,对任务分解器的类型语义、输入元素和输出元素进行形式化定义及描述,然后详细阐述了分解过程,并定义分解过程中所需的操作函数和解析函数。任务分解器将进入系统的原始任务（大任务）按照其输入数据和流程结构进行分解,将大任务分解成适当的多个子任务,构建成相关性任务集,这样可以大幅度提高任务的平均执行性能,同时相关性任务集也可作为后续调度算法的输入内容和调度对象。（2）为解决在通信资源竞争环境下的相关性任务集离线调度问题,提出了CRCHEFT调度算法。CRCHEFT算法在HEFT等算法的基础上充分考虑了处理节点间对通信资源的竞争问题。首先针对分布式多处理器系统的特点,在任务优先级方面改进了任务向上权值的计算方法,解决了以前向上权值计算中异构环境“同构化”的问题。在面向通信资源竞争的通信线路的选择方面,引入指定链路的最早开始时间和最早完成时间的定义,并将任务间的边映射到通信线路上,能够真实准确反映分布式多处理器系统实际运行时的状况。采用处理节点空闲区间插入技术和任务复制技术,实现任务到处理节点的最佳匹配,提高了相关性任务集的调度性能,降低了整体调度长度。CRCHEFT算法的平均时间跨度比主流算法优13%27%左右。（3）为解决在通信资源竞争环境下的相关性任务集在线调度问题,提出了DRSA调度算法。DRSA算法是则在CRCHEFT算法的基础上,面向相关性任务集在线调度问题,提出的一种基于动态重组的综合调度算法。DRSA算法的主要思想是在新任务集到达时对其进行向上权值aranku和向下权值arankd的改进计算,并找出老任务集中具有最大改进向上权值maxaranku,然后在新任务集中找出改进向上权值与maxaranku最近的任务t,最后老任务集出口任务结点的后继任务设置为该任务t,从而实现相关性任务集的合并重组,在重组过程中对系统中所有剩余任务集进行延迟度计算,可以进一步避免系统负载较重时老任务集剩余任务延迟较多的情况。负载的平均完成时间方面比主流算法优10%15%左右,任务完成次序也更加合理。（4）为解决在片上众核处理器系统（MPSoC）环境下具有期限和价值约束的独立任务并发调度问题,提出了VPD算法和DPS-CCS算法。针对MPSoC物理核心较多但单个物理核心运算能力不强的特点,VPD算法着重考虑如何将多个物理核心组合起来以提高单个独立任务的执行效率,该算法在任务执行过程中识别其运行阶段状态,当任务执行进入一个相对平稳的阶段状态时,计算出在该阶段状态中任务对虚拟核的需求,实时选取相应数量的物理核心临时组成与任务需求相匹配的虚拟核,在任务执行效率和资源占用数量之间达到平衡。DPS-CCS算法用于MPSoC环境下的独立任务高性能并发调度,本文所研究的独立任务具有价值和截止期两个影响任务执行性能的重要特征,DPS-CCS算法以VPD算法所计算得出的虚拟核粒度以及运行时间片为基础,综合考虑任务的未实现价值率与时间紧急度这两个因素,给出综合计算方法,同时为避免由于任务迁移和抢占而造成的大量系统开销,在任务组织上采用集中控制式的任务集合,在任务执行周期内根据任务的虚拟核粒度合理分配时间片。DPS-CCS算法针对多任务并发调度,在任务的完成率和累计价值两方面达到适当平衡,无论在静态多核系统还是在MPSoC系统上,能够充分发挥当前系统的优势,优化独立任务调度的公平性,提升任务的执行性能。在任务完成率方面,DPS-CCS算法比主流算法平均高12%40%左右,在累积完成价值率方面,DPS-CCS算法比主流算法平均高20%34%左右。

论文目录

• 摘要
• Abstract
• 主要符号对照表
• 第一章 绪论
•   1.1.研究背景和意义
•   1.2.分布式多处理器系统的发展现状
•     1.2.1.片上多处理器系统
•     1.2.2.基于NoC的多处理器系统
•     1.2.3.分布式多处理器系统
•   1.3.分布式多处理器系统环境下任务调度的研究现状
•     1.3.1.面向分布式多处理器系统的任务分解策略
•     1.3.2.任务相关性单一调度算法
•     1.3.3.任务相关性并发调度算法
•     1.3.4.面向通信竞争的任务相关性并发调度算法
•     1.3.5.独立任务并发调度算法
•     1.3.6.面向MPSoC的物理核分配算法
•   1.4.相关研究存在的问题
•     1.4.1.面向分布式多处理器系统的大任务分解问题
•     1.4.2.对相关性任务的调度优化问题
•     1.4.3.对共享通信资源的竞争研究不足
•     1.4.4.面向片上众核系统的资源划分和独立任务调度问题
•   1.5.研究内容和主要创新工作
•   1.6.论文组织结构
• 第二章 面向任务相关性的调度体系与实验系统
•   2.1.任务的典型特征
•     2.1.1.任务的相关性
•     2.1.2.任务的可分割性
•   2.2.面向任务相关性的调度体系
•     2.2.1.调度体系概述
•     2.2.2.相关性任务集
•     2.2.3.相关性任务集调度器模型
•   2.3.相关性任务集调度实验系统
•     2.3.1.相关性任务集的类型和生成
•     2.3.2.相关性任务集调度器（模拟器）的选择
•     2.3.3.相关性任务集调度器（真实环境）的设计与实现
•   2.4.本章小结
• 第三章 面向大任务调度的任务分解器设计与实现
•   3.1.任务分解器基本框架
•   3.2.任务分解器语义描述
•     3.2.1.类型语义描述
•     3.2.2.输入元素语义描述
•     3.2.3.输出元素语义描述
•   3.3.任务分解过程
•     3.3.1.分解过程概述
•     3.3.2.基本操作函数
•     3.3.3.解析函数
•   3.4.实例分析
•     3.4.1.实例描述
•     3.4.2.分解过程分析
•     3.4.3.生成DAX文件
•   3.5.本章小结
• 第四章 通信资源竞争环境下相关性任务集离线调度算法
•   4.1.相关工作
•   4.2.系统调度模型
•     4.2.1.分布式多处理器系统模型
•     4.2.2.面向通信竞争的相关性任务集调度模型描述
•   4.3.相关计算定义
•     4.3.1.向上权值的改进计算
•     4.3.2.通信线路选择的最早完成时间计算
•     4.3.3.处理节点选择时的最早完成时间计算
•     4.3.4.调度模型其他相关设定
•   4.4.CRCHEFT调度算法
•     4.4.1.CRCHEFT算法整体流程
•     4.4.2.计算最佳通信线路和时间
•     4.4.3.计算处理节点最早完成时间
•     4.4.4.算法复杂度
•   4.5.实验目的与方法
•     4.5.1.实验目的
•     4.5.2.实验平台与模型
•     4.5.3.性能指标
•   4.6.实验结果与分析
•     4.6.1.模拟器环境下实验结果分析
•     4.6.2.真实环境下实验结果分析
•     4.6.3.实验结论
•   4.7.本章小结
• 第五章 基于动态重组的相关性任务集在线调度算法
•   5.1.相关工作及问题
•   5.2.相关计算定义
•     5.2.1.向下权值的改进计算
•     5.2.2.计算实时延迟度的计算
•   5.3.DRSA调度算法
•     5.3.1.动态重组调度策略
•     5.3.2.DRSA算法描述
•     5.3.3.算法复杂度
•   5.4.实验平台与方法
•     5.4.1.实验目的
•     5.4.2.实验平台与模型
•     5.4.3.性能指标
•   5.5.实验结果与分析
•     5.5.1.模拟器环境下实验结果分析
•     5.5.2.真实环境下实验结果分析
•   5.6.本章小结
• 第六章 面向MPSoC的独立任务动态优先级调度算法
•   6.1.基于独立任务的优先级调度算法现状
•   6.2.独立任务调度模型
•   6.3.虚拟核资源分配算法
•     6.3.1.基于行为模式的任务状态识别算法（BTSR）
•     6.3.2.虚拟核资源分配算法（VPD）
•   6.4.DPS-CCS调度算法
•     6.4.1.动态优先级分派策略
•     6.4.2.全局调度策略
•   6.5.实验平台与方法
•     6.5.1.实验目的
•     6.5.2.实验平台
•     6.5.3.性能指标
•   6.6.实验结果与分析
•     6.6.1.静态多核目标环境下DPS-CCS算法性能分析
•     6.6.2.MPSoC目标环境下DPS-CCS算法性能分析
•     6.6.3.系统切换次数分析
•   6.7.本章小结
• 结论与展望
• 参考文献
• 攻读博士学位期间取得的研究成果
• 致谢
• 附件

文章来源

类型: 博士论文

作者: 沈阳

导师: 齐德昱

关键词: 分布式多处理器,任务调度,相关性任务集,通信竞争,虚拟核

来源: 华南理工大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机硬件技术

单位: 华南理工大学

分类号: TP332;O224

DOI: 10.27151/d.cnki.ghnlu.2019.004230

总页数: 152

文件大小: 3300K

下载量: 69