论文部分内容阅读
云计算作为一种新型计算范式,为解决更大规模计算和更高数量级数据处理提供一种新的系统体系结构。为了对这个新的体系结构进行编程,工作流将应用建模为有向无环图(DAG),实现将复杂应用表征为适合计算机处理的作业,成为云计算环境下一种有效编程范式。因此,云计算工作流调度问题是当前系统研究的一个重要方向。区别于传统工作流调度,云计算的一些新特性给这种体系结构下工作流调度带来新的挑战。这些新特性包括:资源动态接入和供给、资源使用效用性、性能抖动、能效比等。为应对这些挑战,本文对相关科学问题和关键技术进行了探索。具体来说,从以下五个方面开展了研究:第一、调取学术界相关论文,选取紧密相关的核心论文,对工作流调度在计算机发展不同阶段的研究工作进行归纳。对工作流调度问题的基础理论、算法设计和实际应用进行了梳理。结合云计算特性,提出了云计算工作流调度模型,总结了云计算工作流调度涉及到的9类主要问题,并对比分析了每一类问题的解决方案。基于分类问题的分析和对已有方案的评估,对未来亟待解决的问题进行了摸索。第二、预算受限工作流调度。相较于传统工作流调度,云计算支持工作流应用根据规模灵活选择资源进行实施。将应用开发人员从资源管理解脱出来的同时,对资源供给和作业调度也带来新的挑战。其中,在预算受限前提下如何选择合理的资源并对工作流进行调度是一类由云计算工作流调度引入的新问题。课题分析得出了由两种特殊结构的顺序、并行路径所构成工作流的理论最优预算分配机制。基于此理论最优方案,设计一种启发式簇工作流调度算法。第三、云计算工作流调度能耗优化。构建绿色云计算中心已经成为学术界和工业界的一个共识。课题研究了基于支持DVFS硬件技术的云计算工作流调度能耗优化问题;建立云计算工作流调度能耗模型;理论推导特殊结构工作流能耗最优调度;设计一种能耗感知的执行期限受限工作流调度启发式算法;此外,课题还对云计算工作流数据传输的能耗问题进行了研究,设计提出了一种能耗感知数据传输机制。第四、IaaS云计算工作流调度优化。截止目前,大部分云计算工作流调度技术假定云资源可以实现理论上的所用即所需的计费模式。从构成云计算系统的IaaS基础设施层可知,现在的技术还不能到达这种理想的状态。课题采用装箱方法对IaaS云计算工作流调度问题进行优化,定义了IaaS云计算工作流调度的装箱模型;基于模型设计了一种优化由其它算法生成调度的方法,和一种执行期限受限云计算工作流调度算法。第五、统一多约束多目标云计算工作流调度。实际使用中的复杂工作流应用通常会面临多种QoS约束和调度目标。课题对不同约束条件和目标的工作流调度问题以及提出的调度算法进行分类归纳;设计了一种统一多约束多目标调度框架,框架采用经济学帕累托最优理论评估调度的优劣;基于此框架,设计了一种解决带执行期限和预算受限的同时优化调度能耗和可靠性启发式算法。