论文部分内容阅读
针对操作系统下多任务与大任务的高性能执行的要求,分布式多处理器系统为解决最终问题(多任务与大任务的高性能计算)提供硬件层面上的基础支持,但是,如何将这种硬件能力转变成计算性能的提升,并充分利用分布式并行计算能力,这便需要有高效的适应多任务和大任务高性能执行要求的调度模型。一个好的调度模型能够高效实现任务与计算资源的映射,解决共享资源的竞争问题,实现任务时间跨度的最小化以及提升硬件资源的利用率,这也是当前分布式多处理器系统研究领域所面临的挑战之一。本文针对多任务与大任务的高性能执行的要求,以分布式多处理器系统为目标环境,研究相关性任务调度问题,从任务分解、时间跨度优化、通信竞争、动态优先级计算以及最优虚拟核分配等方面展开研究。在理论上,发现分布式多处理器系统的调度特性与规律,并进行相应的算法设计与实现,在方法上,给出创新的调度模型与算法,解决目前调度算法对于任务相关性考虑不足、以及对分布式多处理器体系结构的考虑不足等问题,给出面向任务执行性能最优的调度方法。在应用上,首先使所给出的新方法应用于操作系统一级或者支撑操作系统的环境上,支持多任务与大任务在分布式多处理器系统上的高度并发,形成透明的多处理器一级的并行高性能计算环境。本文的研究工作和成果主要包括以下四个方面:(1)为解决分布式多处理器系统环境中大任务的高性能并行计算问题,本文设计并实现了面向分布式多处理器系统的任务分解器,对任务分解器的类型语义、输入元素和输出元素进行形式化定义及描述,然后详细阐述了分解过程,并定义分解过程中所需的操作函数和解析函数。任务分解器将进入系统的原始任务(大任务)按照其输入数据和流程结构进行分解,将大任务分解成适当的多个子任务,构建成相关性任务集,这样可以大幅度提高任务的平均执行性能,同时相关性任务集也可作为后续调度算法的输入内容和调度对象。(2)为解决在通信资源竞争环境下的相关性任务集离线调度问题,提出了CRCHEFT调度算法。CRCHEFT算法在HEFT等算法的基础上充分考虑了处理节点间对通信资源的竞争问题。首先针对分布式多处理器系统的特点,在任务优先级方面改进了任务向上权值的计算方法,解决了以前向上权值计算中异构环境“同构化”的问题。在面向通信资源竞争的通信线路的选择方面,引入指定链路的最早开始时间和最早完成时间的定义,并将任务间的边映射到通信线路上,能够真实准确反映分布式多处理器系统实际运行时的状况。采用处理节点空闲区间插入技术和任务复制技术,实现任务到处理节点的最佳匹配,提高了相关性任务集的调度性能,降低了整体调度长度。CRCHEFT算法的平均时间跨度比主流算法优13%~27%左右。(3)为解决在通信资源竞争环境下的相关性任务集在线调度问题,提出了DRSA调度算法。DRSA算法是则在CRCHEFT算法的基础上,面向相关性任务集在线调度问题,提出的一种基于动态重组的综合调度算法。DRSA算法的主要思想是在新任务集到达时对其进行向上权值arank_u和向下权值arank_d的改进计算,并找出老任务集中具有最大改进向上权值maxarank_u,然后在新任务集中找出改进向上权值与maxarank_u最近的任务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%左右。