混合云平台上多目标任务调度算法研究

发布时间：2017-06-09 10:12

  本文关键词：混合云平台上多目标任务调度算法研究，，由笔耕文化传播整理发布。

【摘要】：云计算是并行计算(Parallel Computing)、分布式计算(Distributed Computing)、和网格计算(Grid Computing)技术的演化和发展。任务调度是云计算的基本研究问题之一,它根据任务的各种需求,采用适当策略把不同的任务分配到云中合适的资源节点上执行。在云计算系统中,任务调度问题也称为任务映射,就是在大量异构节点构成的数据集群中,结合考虑每个计算处理节点的能力,网络带宽等性能,以最合理的方式把用户提交的所有任务分配到数据集群中的计算节点上。这已经被证明是一个非确定多项式(non-deterministic polynomial, NP)问题。目前云计算模式主要有三类：私有云、公有云和混合云。私有云是针对特定的组织或企业内部提供云计算服务的一种云计算模式,能够根据资源节点数量、性能等不同的建设需求而定制,具有数据安全性好、服务质量高、单次计算成本较低的特点：公有云是在公共网络环境(Internet)上,以第三方服务供应商的方式,为用户提供可租用服务及基础设施,具有节点数量大、可用资源多、按计算使用情况计费、对通信质量较为敏感等特点；而混合云则由两个或多个云(私有云、公有云或社区云)组成,它们之间相对独立但又可协同工作。在混合云平台中,任务调度存在新的挑战。首先,混合云通常包含了数量庞大的云计算节点,其任务调度是一个大规模优化的NP问题。其次,由于混合云上的用户差异性较大,其所提交的任务需求多样化,不同的任务对实时性、带宽、计算成本等其中某一项或多项有较高要求。最后,用户作业潜在以分散形式提交,导致云平台上的任务调度,必须考虑任务及各节点资源的动态性问题。因此,在混合云计算环境中,任务调度需要解决的两大问题：一是由于节点数的增多所带来的调度计算复杂度骤然增加；二是异构节点的增多以及用户在提交任务时的需求因素增多,使调度优化的计算维度增大。由此可见,混合云平台上的任务调度,是一个带有多目标条件的大规模优化问题。综合国内外的发展现状,混合云平台上的任务调度面临着以下问题：(1)资源管理难度高。由于混合云中加入大规模异构资源,导致资源管理难度增加。随着物联网、智能终端等技术的发展,不同级别规模的开发云、移动网络及无线传感网等网络资源,都将接入到公共网络中,并作为混合云的一部分。这些云资源数量巨大且具备鲜明的异构性。从国内外的研究情况上来看,在考虑任务特性时,主要工作还是集中在同构资源的动态分配或是单一特性资源自动分簇等方面。对这些大规模异构资源的组织和管理,还有待深入研究。(2)任务分发优化难度大。在大规模异构资源上进行任务分发的难度增大。由于混合云所具有的大规模异构资源,使用启发式算法进行任务调度时,计算效率受到极大影响,而采用在线方法进行调度时,尽管速度快,又不容易得到满足多任务需求最优调度方案。因此,混合云上的任务调度方法,需要综合考虑任务特性、资源异构性等对任务调度的影响。(3)多任务调度目标及其动态性增加了调度难度。目前的任务调度算法中,由于多是考虑单个目标(如QoS、计算成本等),因此多采用权值计算或者决策树的方式,将任务分发与调度综合在一起进行优化。当综合考虑多个目标同时满足时,沿用以往的办法,无疑将提升维度,增大算法求解难度。而且,任务完成后的资源释放也是一种动态性,同样影响着任务调度的策略制定。本研究针对混合云平台上任务调度面临的挑战,将其抽象成大规模异构资源上的多目标调度优化问题。通过将异构资源按其多属性分类成同构资源池,来解决资源的异构性问题；通过对任务与资源池的相似度及偏好关系计算,来解决任务的快速分发问题；最终设计并实现多目标任务调度优化算法,来解决任务在资源池中的多目标调度。所做的工作包括：本文中针对混合云上任务调度问题,给出了其抽象的数学优化模型。针对任务调度问题自身的特点,设计了一种单目标差分演化算法——GaDE算法,该算法在交叉操作,选择策略以及控制参数的调整方面对jDE算法进行了改进,能够以最少的仿真次数保留最多的有效遗传信息；同时给出了一种偏序关系,使其能够用于处理约束条件。为了更好的处理混合云任务调度中常出现的多目标优化,在提出的改进GaDE算法的基础上,结合非支配排序算法NSGA_Ⅱ中基于Pareto最优的快速排序的方法,提出了一种多目标算法——NSjDE算法,算法同样也对减少评价的次数做了一些考虑和尝试。通过实验对比了Min-Min算法、GaDE算法和NsjDE算法等三种启发式算法。实验结果表明,在单目标的任务调度上,GaDE算法和NsjDE算法在近似最优解的获取上有更好的表现。而多目标的NSjDE算法在优化速度上明显优于单目标的改进jDE算法,并且可能在一次运行中产生多个满足要求的非劣解,以便于向用户提供更多的选择。针对混合云中任务提交的分散性及动态性,本文提出了基于协同过滤的混合云任务调度算法。该算法将个性化推荐技术引入到任务调度中,把任务当做是需要选择资源的用户,为其进行推荐。该算法使用相似度矩阵计算任务对资源的偏好,以达到快速将任务分配到资源的目的。在算法设计中,本文设计了基于属性的评分方法,并且结合多目标的需求,使用类似于多F1标求解方法中聚合函数的方式,给出了最资源的多同标加权评分。为了提高预测评分的准确性,文中采用多元线性回归的方法给出了评分预测模型,在此基础上完善了协同过滤器的设计。通过实验将协同过滤任务调度算法与GaDE算法及NsjDE算法进行对已。实验结果表明,尽管相比于单/多目标启发式优化算法,协同过滤推荐算法在以极小最短完成时间、极小计算成本为目标的调度方案上无法得到最优解,但是其计算时间快、可扩展性强。而且由于在评分模型中,已经考虑了冲突目标(计算成本与最短完成时间)的负分评价,因此在得到的调度方案中,协同过滤推荐算法能够得到一个多目标间较为均衡的解。协同过滤调度算法在计算速度上的优势,及在多目标调度上的表现,使得其可以作为混合云在线任务调度方法的一个选择。针对协同过滤任务调度算法的计算效率提升问题,本文研究了Map-Reduce编程模型下的大矩阵乘法并行化方法。通过矩阵乘法的定义发现,矩阵乘法的计算部分是相互独立的,可以并行计算。在设计基于MapReduce的内积法时,为了减小存储空间开销,采用了稀疏矩阵的存储方法。由于map阶段有大量的拷贝工作,导致计算效率降低,实验表明,该算法对稀疏矩阵的效果较好,对稠密矩阵的效果较差。并且当矩阵规模扩大时,算法的执行时间显著增长,不适合于更大规模的矩阵运算。MapReduce框架的分布式缓存可以将文件存储在计算节点的缓存中,使得map函数和reduce函数在运行时能够读取。本文根据这一特点设计了基于分布式缓存的矩阵乘法的算法,将右矩阵存储在计算节点缓存中,在map阶段只读取并分发左矩阵的数据,在reduce阶段读取右矩阵的数据并与接收到的左矩阵的数据计算最终结果。核算法与基于MapReduce的矩阵乘法相比算法复杂度大为降低,在map阶段仅仅是分发左矩阵的数据,没有任何拷贝工作,因此shuffle阶段网络开销不大。在reduce阶段,两种算法复杂度相同,计算时间开销相当。通过实验证明了该算法与基于MapReduce的矩阵乘法的计算效率的提高。并且矩阵的规模对该算法的执行时间没有影响,表明该算法具有更好的普适性。针对协同过滤任务调度算法的评分矩阵降维,研究了基于演化的多标签分类算法。K最近邻结点(KNN)算法,对包容型数据的特征变量筛选尤其有效,且原理简单,实现起来比较方便,支持增量的学习,能对超多变形的复杂决策空间建模,是多标签分类中常用的算法。KNN算法的核心原理是通过计算样本之间的距离从而得出记录的标签,而距离是通过记录的属性用合理地距离公式计算出来的,所以对属性值的依赖性较高,而对于KNN分类算法来说,许多数据集中的特征(计算距离时是指属性值)有冗余或是不相关,这会导致距离计算的偏差,当冗余度较高时,偏差就会影响分类的准确性。本文提出了一种基于PSO的特征加权KNN算法P SOKNN,该算法将KNN分类器的精确度计算当做PSO算法的适应函数,并且把一个加权KNN的特征属性的权值向量当做PSO算法的一个微粒,随机设定多个权值向量形成微粒群,再通过微粒速度与距离的变更,进而找到一个适应值最优的微粒即权值向量。每个数据集都能产生一个最优权值向量,因此KNN分类器针对每个数据集都能达到一个很高的分类精度即形成了一个精确度高的自适应分类器。最后通过实验结果表明,PSOKNN算法在几个经典的分类数据测试集上都能表现出良好的效果。本文工作存在的不足之处在于(1)没有对两种启发式算法做并行化研究。在云环境下将两种启发式算法并行化,应该是提升其计算速度的有效方法。但由于演化算法本身是计算密集型,因此其并行化计算模型的研究也是目前研究的一个方向,但本文未在这上面做工作。另外,任务模型相对理想化,而实际的任务调度过程中,不一定能够得到满足任务模型定义的所有信息,也是制约着该算法的实用性的主要因素。(2)在协同过滤调度算法的评分模型有待改进。在协同过滤调度算法的评分模型式3-5中,使用的是对各属性分量评分的等权重加成的方法,没有考虑不同分量在针对不同调度目标时的倾向性影响,因此在推荐成功率上,仍有较大的改进空间。另外,本文提出的协同过滤算法的评分机制,依然依赖于任务对资源的详细需求,而在实际的调度过程中,这样的需求并不一定能够完全得到。因此如何利用现有可以得到的任务信息来实现有效推荐,在算法上仍有改进空间。(3)矩阵乘法在MapReduce计算模型下的算法仍需要更多的改进。对于内积法,当遇到稀疏矩阵的时候,存储开销较低,在map阶段的拷贝工作时间开销并不大,但是遇到稠密矩阵的时候,map阶段的拷贝工作的计算时间开销与矩阵规模成指数增长。因此可以研究从减少拷贝工作的时问开销入手,将拷贝工作分发到更多的计算节点上,增大拷贝工作的并行效率。而对于缓存法,map阶段的主要工作仅仅是分发矩阵数据,不同的计算节点可能具有不同的计算资源。可以结合本文中的调度方法,使得map任务能够最大化并行效率,避免出现map阶段等待某一个map任务的情况发生,造成计算资源空闲。(4)基于演化的多标签分类算法的扩展性还考虑不足。一方面,由于使用了启发式算法对分类器进行优化,因此当数据规模增大时,其计算耗时也将迅速增加,可尝试通过使用MapReduce技术来并行实现分类,缩短计算时间。另一方面,在验证算法时使用的模拟数据与实际发生的数据仍有较大差异,实际数据在数据的准确性、完整性上不一定满足算法中PSO部分的训练需求,在这方面本文没有做考虑。任务调度的优化对混合云上的计算效率具有关键作用。本文采用多标签分类理论和方法,针对混合云上的大规模异构资源分类问题进行了研究,分析了资源属性间的关联性,建立了异构资源表示模型,设计了多属性分类算法：采用在线推荐及分类匹配理论和方法,针对动态任务的快速分发问题进行了研究,分析了任务需求对分发策略的影响,建立了任务偏好及快速匹配模型,设计了基于任务特性的动态任务分发算法；采用了多目标优化的理论和方法,针对多目标任务调度问题进行了研究,分析了任务需求对资源分配的影响,建立了多目标任务调度优化模型,设计了满足混合云平台的多目标优化算法。通过研究,在理论上揭示了异构资源环境下多目标任务调度的机理,阐明了资源分类、作业分发及调度优化之间的内在联系,建立了大规模混合云平台上多目标的任务调度机制；在应用上实现了对混合云平台上动态任务的快速有效分发。
【关键词】：混合云 任务调度 多目标优化
【学位授予单位】：中国地质大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP301.6
【目录】：

• 作者简介6-9
• 摘要9-13
• ABSTRACT13-22
• 第一章 绪论22-35
• §1.1 选题的目的和意义22-23
• §1.2 云上的调度策略及算法23-27
• 1.2.1 云上的调度策略23-25
• 1.2.2 云上的调度算法25-27
• §1.3 国内外研究现状27-31
• 1.3.1 面向任务的云资源分配方法27-29
• 1.3.2 任务调度方法29-31
• §1.4 任务调度面临的挑战31-32
• §1.5 研究内容32-33
• §1.6 论文的组织结构33-35
• 第二章 基于差分演化的任务调度算法35-65
• §2.1 任务调度模型35-37
• §2.2 演化算法概述37-40
• 2.2.1 演化算法概述37-38
• 2.2.2 演化算法框架38-39
• 2.2.3 演化算法的基本特征39-40
• §2.3 差分演化算法40-44
• 2.3.1 差分演化算法简介40-43
• 2.3.2 差分演化算法研究情况43-44
• §2.4 改进的jDE算法及其在混合云任务调度中的应用44-48
• 2.4.1 jDE算法简介44-45
• 2.4.2 改进jDE算法——GaDE45-48
• §2.5 基于非支配排序的改进jDE算法48-55
• 2.5.1 多目标演化算法概述48-50
• 2.5.2 NSGA_Ⅱ算法简介50-53
• 2.5.3 基于非支配排序的多目标jDE算法——NSjDE53-55
• §2.6 实验结果与分析55-63
• 2.6.1 实验环境55
• 2.6.2 算法性能分析55-58
• 2.6.3 混合云任务调度结果分析58-63
• §2.7 本章小结63-65
• 第三章 基于协同过滤的在线调度算法65-79
• §3.1 影响混合云上任务执行性能的因素65-66
• §3.2 个性化推荐技术66-68
• §3.3 基于协同过滤推荐的任务调度方法68-74
• 3.3.1 评价模型69-71
• 3.3.2 评分预测模型71
• 3.3.3 协同过滤推荐模型71-74
• §3.4 实验结果与分析74-78
• 3.4.1 实验环境74
• 3.4.2 算法验证74-78
• §3.5 本章小结78-79
• 第四章 矩阵乘法并行化研究79-97
• §4.1 矩阵的奇异值分解原理79-81
• 4.1.1 矩阵的奇异值79
• 4.1.2 矩阵的奇异值分解(SVD)79-80
• 4.1.3 奇异值分解的算法80-81
• §4.2 矩阵运算的研究现状81-82
• §4.3 矩阵乘法的实现82-85
• 4.3.1 矩阵乘法定义82-83
• 4.3.2 伪代码及复杂度分析83
• 4.3.3 矩阵分块83-85
• §4.4 MapReduce编程模型85-86
• 4.4.1 MapReduce编程模型概述85
• 4.4.2 数据分片85-86
• 4.4.3 数据流86
• §4.5 基于MapReduce的内积法86-89
• 4.5.1 数据存储86-87
• 4.5.2 计算模型87
• 4.5.3 伪代码实现87-88
• 4.5.4 存在的问题88-89
• §4.6 基于分布式缓存的矩阵乘法研究89-91
• 4.6.1 分布式缓存技术89-90
• 4.6.2 基于分布式缓存的矩阵乘法90
• 4.6.3 性能分析90-91
• §4.7 实验结果与分析91-96
• 4.7.1 实验环境91
• 4.7.2 分片实验91-92
• 4.7.3 稀疏矩阵与稠密矩阵比较92-93
• 4.7.4 不同集群规模比较93-94
• 4.7.5 内积法与缓存法比较94-95
• 4.7.6 稀疏矩阵和稠密矩阵比较95-96
• §4.8 本章小结96-97
• 第五章 基于演化的多标签分类方法97-117
• §5.1 多标签分类问题的研究现状97-100
• §5.2 多标签分类方法的选择100-102
• §5.3 粒子群优化算法及其改进102-105
• 5.3.1 粒子群优化算法概述102-103
• 5.3.2 粒子群优化算法的模型及流程103-105
• §5.4 基于粒子群算法的多标签分类算法105-114
• 5.4.1 PSO优化部分的详细设计106-108
• 5.4.2 KNN分类算法的详细设计108-109
• 5.4.3 KNN算法中距离计算算法的选择109-112
• 5.4.4 基于PSO的KNN分类算法112-114
• §5.5 实验结果与分析114-116
• 5.5.1 实验环境与流程114-115
• 5.5.2 实验结果与分析115-116
• §5.6 本章小结116-117
• 第六章 总结与展望117-120
• §6.1 工作总结117-119
• §6.2 展望119-120
• 致谢120-121
• 参考文献121-129

【参考文献】

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

1 邢春晓;高凤荣;战思南;周立柱;;适应用户兴趣变化的协同过滤推荐算法[J];计算机研究与发展;2007年02期

2 康立山，陈毓屏;演化计算[J];数值计算与计算机应用;1995年03期

3 姚忠;魏佳;吴跃;;基于高维稀疏数据聚类的协同过滤推荐算法[J];信息系统学报;2008年02期

4 苏博;刘鲁;杨方廷;;基于灰色关联分析的神经网络模型[J];系统工程理论与实践;2008年09期

中国博士学位论文全文数据库 前2条

1 刘晓茜;云计算数据中心结构及其调度机制研究[D];中国科学技术大学;2011年

2 孙小华;协同过滤系统的稀疏性与冷启动问题研究[D];浙江大学;2005年

中国硕士学位论文全文数据库 前3条

1 唐犀;基于仓库策略的虚拟化资源调度系统关键技术研究与实现[D];电子科技大学;2011年

2 李锋华;基于蚁群算法的云计算资源负载均衡调度算法研究[D];云南大学;2013年

3 胡腾飞;服务搜索引擎中个性化服务推荐功能的设计与实现[D];北京邮电大学;2013年

  本文关键词：混合云平台上多目标任务调度算法研究，由笔耕文化传播整理发布。

本文编号：435128