动态云环境中基于SLA的工作流调度

Workflow is an important use case of cloud computing. For running workflow, users usually require their QoS constraints, e.g. deadline, to be satisfied. However, there is always an unavoidable error in the prediction of workflow task execution time. And from this error, the satisfication of QoS constraints and the profit of cloud service providers may probably suffer. This issue has not yet been well addressed by the existing workflow scheduling systems in the context of cloud computing. This project proposes a SLA-based multi-phase workflow scheduling system, which consists of a series of methods including admission control, over-estimated advance reservation and rescheduling during runtime. We aim to implement an efficient workflow scheduling mechanism to meet the QoS requirements from users and service providers simultaneously, so that the potential of cloud computing can be fully explored to satisfy the increasing demands of large-scale computing from various scientific, industrial and commercial fields.

工作流是当前云计算平台的一个重要用例。对于工作流的运行，用户常见的一个服务质量(QoS)指标常常体现在要求一个明确的截止时间。然而，对工作流子任务的运行时间的预测不可避免地存在误差。此误差对满足用户的QoS要求和云计算服务商的利益均存在不利影响。当前在研的云计算调度系统尚不能很好地解决这些不利影响。因此，本项目提出了一个基于SLA(Service Level Agreement)的多阶段化的工作流调度框架，通过基于SLA的用户请求准入控制、过估预约和运行期重调度等一系列方法的组合，期望能在动态云环境中实现一个高效的的工作流调度机制，能同时满足用户方与云计算服务方的QoS要求，以充分发挥云计算平台的潜力，满足包括科学，工业，商业等社会各领域日益增长的对大规模计算的需求。

随着现代网络技术的发展成熟，云计算已经成为解决科学工作流大规模计算问题的主要途径之一。调度是云计算平台得以充分发挥系统性能的关键技术。由于云计算平台具有很强的动态特性以及有别于传统分布式计算方式的特征，因此简单地将传统的工作流调度算法应用到云计算调度系统中会带来不少问题。以解决这些问题为目标，本项目主要取得了如下研究进展：（1）基于工作流任务时间预测随机化的模型，提出了两个基于蒙特卡罗方法思想的随机化工作流调度算法，能够在可控的时间内生成一个调度结果，仿真实验表明该调度结果的平均总体运行时间明显优于静态调度算法以任务时间预测期望值为输入生成的调度结果；（2）在多目标优化工作流调度问题范畴内，考虑“截止时间+预算”和“总体运行时间+能耗”两种多目标优化背景，分别提出了BHEFT，GTI等多目标优化算法，性能评估结果表明这些算法能在相近的时间开销内取得比已有的同类其他调度算法更好的优化效果；（3）考虑工作流的在线调度模型，提出一个轻量型的调度算法PB，以更小的算法开销获得更优的总体运行时间。..通过以上研究进展，本项目的工作有效地改善了工作流任务在动态云环境中的计算性能和能耗，相关研究成果发表在多个分布式计算及高性能计算领域相关的高水平国际学术会议和期刊中，其中包括《Journal of Parallel and Distributed Computing》、《Journal of Grid Computing》、《Concurrency and Computation: Practice and Experience》、CCGrid等，并获得国内外学者的引用。