同构集群系统中基于任务集依赖的节能任务调度算法研究

发布时间：2017-06-21 07:11

  本文关键词：同构集群系统中基于任务集依赖的节能任务调度算法研究，由笔耕文化传播整理发布。

【摘要】：科学数据和商业数据以数量级的速度增长对计算机技术提出了非常大的挑战,大规模的应用程序迫切需要高性能计算系统、海量存储系统和高速网络等基础设施的支持。在高性能计算领域,研究人员一直为提高系统性能不断进行改进,他们不断地增加集群中处理器数目,不断的提高处理器运算速度,为了追求更高的每秒峰值速度而不断努力。然而处理器集群的功耗管理在很长一段时间内被研究者和设计者所忽视,直到近年来才逐渐被人们所重视。 在大型计算机系统中,计算机运行能耗开支和散热所需能量己占据总能耗开支的绝大部分。能耗的大幅增长产生了大量的热量,这不仅增加散热的成本和难度,还影响系统部件的稳定性。同时,计算机产生的温室气体会对环境形成不利的影响,并且产生的温室气体呈现出逐年上升的趋势。因此,基于能耗问题的研究具有很深远的现实意义。 在降低集群系统功耗研究中,基于操作系统的节能任务调度策略是一种理想的解决方法。总体而言,并行调度可以分为四种类型：基于优先级的并行任务调度、基于聚类的并行任务调度、基于任务复制的并行任务调度和基于遗传随机技术的并行任务调度。其中,基于复制的任务调度在调度性能方面明显比其他两种方式更好。然而,基于复制的任务调度为了缩短调度的总时间,大量复制了关键路径上的任务,如果冗余任务的执行所需能耗比减少的通信能耗多,则会造成了系统总能耗增加。为了确保集群系统的调度性能,基于任务复制的节能调度算法研究具有现实意义。 本文在总结前人工作的基础上,仔细研究已有的任务复制调度算法和节能优化调度算法,分析现有算法的优势和缺陷,最终提出基于依赖度的任务调度算法。在基于依赖度的任务调度算法中,首先提出了任务间依赖度、任务与路径依赖度、路径与处理器依赖度等概念,然后在基于复制的任务调度算法基础上,限定处理器的个数,利用任务执行路径对处理器的依赖度大小,选择能够最大程度减少任务间的通讯能耗和减少冗余任务执行的处理器来分配路径,从而大幅降低系统能耗,同时释放空闲处理器,提高处理器的负载平衡。 本文最后用C++设计一个实验仿真平台,实现了三种基于任务复制的改进算法和三种原始算法。实验平台采用实际使用的处理器和高速互联网络进行参数配置,并对集群系统中常用的两个任务集进行测试,通过对松弛因子、处理器个数、任务集类型、网络类型和通信-计算比等条件,得到不同算法运行相同任务时的调度时间、系统总能耗和所用处理器个数等实验数据。通过实验证明,改进算法能够明显的降低处理器的使用个数,提高处理器的负载平衡和节省更多的能量,尤其对通信密集型的任务和高延迟的网络有更好的效果。
【关键词】：集群 并行计算 依赖约束 节能调度 依赖度
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP38;TP301.6
【目录】：

• 摘要10-12
• ABSTRACT12-14
• 第一章 绪论14-21
• 1.1 课题研究背景及意义14-16
• 1.2 国内外研究现状及分析16-18
• 1.3 本文的章节安排18-21
• 1.3.1 本文的主要工作18-19
• 1.3.2 本文的组织结构19-21
• 第二章 相关技术研究21-29
• 2.1 集群21-23
• 2.1.1 集群基本概念21-22
• 2.1.2 集群分类22
• 2.1.3 集群技术的特点22-23
• 2.2 基于DAG模型的并行任务调度算法23-28
• 2.2.1 基于DAG图的调度算法分类23-24
• 2.2.2 表调度算法24-25
• 2.2.3 聚簇调度算法25-26
• 2.2.4 基于复制的调度算法26-27
• 2.2.5 基于遗传算法和随机搜索技术的算法27-28
• 2.3 本章小结28-29
• 第三章 基于任务复制的三种节能调度算法29-45
• 3.1 节能调度问题模型29-38
• 3.1.1 任务模型30-31
• 3.1.2 处理器模型31-33
• 3.1.3 路径模型33-34
• 3.1.4 依赖度模型34-35
• 3.1.5 能耗计算模型35-38
• 3.2 基于任务复制的调度策略38-41
• 3.2.1 构造原始任务调度序列39
• 3.2.2 参数计算39-41
• 3.2.3 分配任务,生成任务调度序列41
• 3.3 TDS算法41
• 3.4 EAD算法41-43
• 3.5 PEBD算法43-44
• 3.6 本章小结44-45
• 第四章 基于依赖度的任务调度算法45-51
• 4.1 生成初始任务执行路径45-46
• 4.2 根据依赖度合并任务执行路径46-49
• 4.3 基于单核多处理器和同构多核异构多处理算法改进49-50
• 4.3.1 基于单核处理器同构集群调度改进算法49-50
• 4.3.2 基于多核处理器异构集群调度改进算法50
• 4.4 本章小结50-51
• 第五章 实验结果及分析51-73
• 5.1 仿真环境51-60
• 5.1.1 硬件配置51-52
• 5.1.2 系统参数52-53
• 5.1.3 仿真软件53-60
• 5.2 实验一：整体性能对比60-62
• 5.3 实验二：松弛因子(Slack Factor)的影响62-64
• 5.4 实验三：不同处理器个数对性能的影响64-65
• 5.5 实验四：不同任务集类型对性能影响65-67
• 5.6 实验五：不同网络类型对性能影响67-69
• 5.7 实验六：不同通信-计算比(CCR)的影响69-71
• 5.8 本章小结71-73
• 第六章 总结与展望73-75
• 6.1 全文总结73-74
• 6.2 课题展望74-75
• 参考文献75-81
• 致谢81-82
• 攻读学位期间发表的主要学术论文82-83
• 攻读学位期间参与科研项目及获奖情况83-84
• 学位论文评阅及答辩情况表84

【参考文献】

中国期刊全文数据库 前2条

1 李新;贾智平;鞠雷;赵衍恒;宗子良;;一种面向同构集群系统的并行任务节能调度优化方法[J];计算机学报;2012年03期

2 陈志刚,华强胜;EZDCP:A new static task scheduling algorithm with edge-zeroing based on dynamic critical paths[J];Journal of Central South University of Technology(English Edition);2003年02期

  本文关键词：同构集群系统中基于任务集依赖的节能任务调度算法研究，，由笔耕文化传播整理发布。

本文编号：467934