论文部分内容阅读
在高性能分布式计算领域中,云计算已经成为一种越来越流行的计算范式,因为其在网络中以自助、动态可拓展以及可计量的方式提供按需访问共享资源池的服务。当前,云计算仍处于一种起步的阶段,为了充分获得其益处,需要对许多主题进行交叉的大量研究。其中,最需要关注的重要研究议题之一就是如何进行高效的任务资源多目标调度优化,调度的目标在于映射任务至合适的资源中以优化一个或者多个目标的方式进行。在云环境中的调度问题由于需要大量的解决方案空间而属于一类被称之为NP-难的问题,因此需要花费大量的时间来寻找一个最佳的解决方案。对于该问题,没有算法能够在多项式的时间内产生最优解来解决这些问题。因此在云环境中,能够做到的是在尽可能短的时间内寻找到次优解或接近最优解。基于元启发式算法的技术已经被证实能够针对以上问题在合理的时间内获得近似的最优解,但存在计算时间复杂度高,有可能过早收敛等问题。通常来说,在分散异构的云环境中有不同的因素以及“参与者”,它们每个都从不同的角度来观察并解决问题。云系统用户们通常致力于最小化应用的执行时间以及减少所花费的经济成本,而系统的管理员总是关注于如何最大化资源利用,尽可能减少能耗,提高作业吞吐量以及保证系统用户公平等。因此,在现实世界的调度问题中,经常会面临一种多目标优化的场景,尤其是其中许多重要的目标是互相冲突的。例如,强大的处理器通常需要花费较高的价格从云计算供应商处租用,然而,其会消耗更多的能量,并且由于大量的请求和用户的争用而可能变得不可靠。如今,云环境中的相关任务调度工作大多只限于一个优化目标(通常是完工时间),也有一些研究方法试图在两个标准之间进行权衡优化。一个通用的调度框架(高效并且低时间复杂度)和基于启发式算法来优化并且动态权衡多个目标的方法仍然缺失。针对云环境中任务流的多目标调度优化技术,本文开展了一系列的研究,首先针对云环境中任务流的多目标调度优化技术的研究现状进行深入总结分析。然后从能耗优化问题展开本文的第一项研究工作,致力于设计一种针对IaaS云的绿色节能管理策略。在对元启发式调度优化相关算法的分析中,设计出一种满足用户不同性能和能耗要求的调度算法,并寻找到了系统最高能效的极值条件。在针对一般启发式调度算法的研究中,结合帕累托优化的相关内容,设计出了基于Spark云的若干种用来帮助云服务提供商选择合适的时间-经济权衡方案建议消费者的算法策略。最后,针对元启发式调度算法高时间复杂度的缺点设计出一种高效的多目标调度优化算法,计算开销的有效降低给现实的云数据中心带来了重要意义。本文的主要的研究成果如下:(1)针对虚拟化云计算数据中心通常根据主机节点的利用率来确定能耗情况并不准确的问题,提出IaaS云能效模型和低能耗解决方案。在云平台级别,设计出两种基于时区的能量管理策略,其重要优势是独立于其它平台级的节能方案。所提节能策略首先在模拟环境下进行验证,然后部署在真实的IaaS架构云平台中。通过采用不同的任务类型(CPU密集型和I/O密集型)验证了所提节能方法的适用性,得到了现实云数据中心可以借鉴的结论。通过实验验证,采取所提的节能策略能使云数据中心表现出更好的低能耗特性,平均节省约12.98%的能量消耗。(2)针对云环境中用户对任务的性能和能耗动态调控的问题,提出一种性能和能耗权衡的基于遗传算法的E-PAGA任务调度策略,满足了用户对性能和能耗的不同需求。通过实验验证了所提算法克服了其它启发式算法存在的过早收敛问题,并得出了以下重要结论:在保证总任务时间最低的同时通常能保证一定的低能耗;而一味地降低总任务的能量消耗,付出的代价就是必须牺牲足够的性能;存在最佳能效比的极值条件等。总的来说,E-PAGA算法可以适用于数据中心中云任务的分配问题并且对计算服务器的能耗最小化大有裨益,也能够满足用户的不同需求。在实际的云数据中心中具有重要借鉴意义。(3)针对云环境中从经济成本的角度来有效调度大量任务流应用的关键问题,提出一个基于Spark的优化框架,针对Spark中的两种算子(transformation,action算子)进行时间和经济建模,并利用云环境中资源的弹性特征来研究并探索经济-性能权衡的调度优化。在综合实验中,设计相关贪婪,概率等搜索算法进行验证并总结了一些有益的普遍特征,比如不同类型的任务流有着不同的弹性类型,不同需求的最优解来自不同的算法,转换操作更易在完成时间和经济成本上带来显著开销等。研究成果的现实意义在于可以用来帮助云服务提供商去选择合适的时间-经济权衡方案来建议消费者。(4)针对主流的元启发式多目标调度优化算法存在高时间复杂度、计算开销过大、最优解存疑等问题,提出一种快速收敛的高效多目标调度优化(MOG)算法。该算法从不同角度将优化目标分别划分为用户指标(完工时间和经济成本)和云系统指标(网络带宽、存储约束和系统公平度)。能够在优化用户指标的同时,实现系统指标的约束,并保证云资源的效率和公平度。通过综合实验,证实所提MOG算法和其它相关算法相比,在算法复杂度(明显改进数量级),结果质量(一些情况下最佳),系统级别公平性上具有明显优越性。