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

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

您可以在本站搜索以下学术论文文献来了解更多相关内容

一种面向同构集群系统的并行任务节能调度优化方法    李新;贾智平;鞠雷;赵衍恒;宗子良;

并行累积可视性分析中的任务调度研究    宋效东;窦万峰;汤国安;张刚;江岭;

面向多处理器资源预留的实时程序划分方法    吴以凡;张桦;戴国骏;

三层客户/服务计算技术研究及其应用    吕西红;陈志刚;曾碧卿;曾志文;

同构DVS集群中基于自适应阈值的并行任务节能调度算法    刘伟;尹行;段玉光;杜薇;王伟;曾国荪;

云数据管理系统能耗基准测试与分析    宋杰;李甜甜;朱志良;鲍玉斌;于戈;

云环境下计算资源动态能耗感知的并行任务调度方法    曹洁;曾国荪;

云计算环境下多有向无环图工作流的节能调度算法    刘丹琦;于炯;英昌甜;

异构环境下Out-Tree任务图的调度算法    旷文;张建军;刘永凯;

Improving Scalability of Cloud Monitoring Through PCA-based Clustering of Virtual Machines    Claudia Canali;Riccardo Lancellotti;

异构集群下的任务调度算法研究    刘莉;姜明华;

网格任务调度与优化机制研究    杨博

面向可重构阵列结构的任务调度算法研究    郭力

基于DAG模型的高效并行任务调度算法研究    华强胜

网格计算任务的复制异构动态调度方法    乔伟光

网格环境中任务DAG调度算法研究    李佳

网格环境中基于DAG的并行任务调度算法研究    杜杰

基于最早完成时间的网格任务调度算法    秦涛

异构集群下并行任务的复制调度算法    刘莉

云计算环境下节能任务调度策略研究    张陶

基于混沌蚁群算法的网格任务调度研究    马远向

基于改进粒子群的异构CMP依赖任务调度研究    张博

一种面向异构实时集群系统的使用率反馈控制方法    王洁;王宏安;傅勇;李新;

网络集群计算系统中的并行任务调度    黄金贵,陈建二,陈松乔

绿色网络和绿色评价:节能机制、模型和评价    林闯;田源;姚敏;

一种基于模糊聚类的网格DAG任务图调度算法    杜晓丽;蒋昌俊;徐国荣;丁志军;

一种基于UUTs模型的并行测试任务调度算法    李云涛;崔少辉;

基于遗传算法的网格任务调度方法研究    周建中;王树宗;石章松;王成飞;

网格工作流的动态贪心调度算法    邓定兰;于炯;谭亚丽;吕良干;

BALANCE-II:一个基于Internet环境的负载平衡系统    邓万涛,彭德纯,林子禹,陈天雄

树形异构网格的启发任务调度算法    黄鲲;王知衍;翁小雄;

基于OPNET的局部网格任务调度平台设计    薛桂香;赵政;史伟;孟和;宋建材;

分布式网格系统的任务调度算法DE Scheduling    于洋;杨愚鲁;杨学刚;贺铭;

基于Min-Min遗传算法的网格任务调度方法    马景奕;隋兵;舒万能;

网格任务调度算法的研究    刘先刚;廖述剑;

基于QoS Guided Min-min任务调度算法局部优化    王祖析;

一种基于Q学习的任务调度算法的改进研究    杜琳;石慧;刘晓平;

电信社群网络中介度的网格并行算法及调度算法    陈平;王柏;徐六通;吴斌;王艳辉;

一种兼有语音通信功能的实时定位系统的设计与实现    吕默威;韩世杰;张晓彤;何杰;余美强;

海量信息系统中服务器机群和客户机结合的分布式虚拟现实计算    王益;邢春晓;周立柱;

基于令牌总线的网络控制系统中信息的优化调度    刘怀;黄建新;曹弋;

实时系统动态优先级任务调度算法的研究    巴巍

一类异构多处理器片上系统任务调度算法研究与应用    杨志邦

任务间相互依赖的并行作业调度算法研究    马丹

单芯片系统（SoC）中的实时任务调度算法研究    贺小川

云计算环境下最小化运营开销的调度技术研究    李健

基于网格的煤炭企业信息化关键技术研究    钟锋

现代控制局域网技术在飞行器控制系统中的研究    张宏巍

云环境下的任务调度算法研究与实现    李坤

云计算环境下基于网络博弈的任务调度算法    李晓

云计算中任务调度算法的优化与研究    马睿

云计算环境下任务调度算法的研究    张希翔

云计算环境下基于改进粒子群的任务调度算法    封良良

基于反馈机制的实时弹性任务调度算法研究    朱雪庆

云计算任务调度算法的研究与实现    王登科

云计算环境下基于时间富余度的任务调度算法研究与实现    高鸣

Hadoop平台任务调度算法的研究与改进    马宝来

云计算环境下基于MapReduce模型的任务调度算法研究    邹伟明