本文将介绍文章“随机任务在云计算平台中能耗的优化管理方法”。

原文链接：http://pan.baidu.com/s/1jGp5mBG

参考文献：Min-Min算法和Max-Min算法

摘要

背景

针对云计算系统在运行过程中由于计算节点空闲而产生大量空闲能耗，以及由于不匹配任务调度而产生大量“奢侈”能耗的能耗浪费问题，本文提出一种通过任务调度方式的能耗优化管理方法。

1. 高能耗是云计算系统最为严重的问题之一
2. 云计算系统中，除了处理任务时产生的必要能耗开销，其运行过程中还存在能耗浪费的现象

解决方案

1. 用排队模型对云计算系统进行建模，分析云计算系统的平均响应时间和平均功率，建立云计算系统的能耗模型；
2. 提出基于大服务强度和小执行能耗的任务调度策略，分别针对空闲能耗和“奢侈”能耗进行优化控制。基于该调度策略，设计满足性能约束的最小期望执行能耗调度算法ME³PC (minimum expectation execution energy with performance constraints).

结果

 大量实验表明，本文提出的能耗优化管理方法在保证其性能的前提下，大幅度降低了云计算系统的能耗

下一步工作

将研究在给定和真实的云计算系统体系结构下，如何根据任务到达率的大小和分布规律，决策系统中应该处于运行状态的计算机个数，结合关闭/休眠技术和电压动态调整技术，进一步对云计算系统的能耗进行优化控制，并且将研究的理论成果在实际云平台上进行评测，以验证其正确性

能耗

能耗分类

1. 空闲能耗：由于计算任务达到的随机性，使得单位时间内到达的任务量时而稀疏，时而密集，而现有的云计算系统通常是长时间处于开启状态，等待计算任务的到达。但是当计算机处于空闲状态时，其空闲功率会占峰值功率的50%~60%。因此，云计算系统会产生大量的空闲能耗。
2. 奢侈能耗：由于云计算系统中通常包含不同的计算机，实验结果表明，不同计算机对不同计算任务的执行功率和响应时间一般不同。例如，同一图像处理任务分别在CPU 和GPU 上的执行功率和响应时间不同，任务执行完成后，产生的总能耗也不同。因此，当未考虑能耗因素时，不匹配的调度方式会造成:本来用较低能耗就能解决问题，但却用了较高能耗。本文把由于任务的不合理调度而浪费的能耗称为“奢侈”能耗。
3. 执行能耗：执行能耗可定义为：任务在计算机上运行时，指令和数据驱动计算机硬件运转所产生的能耗

传统节能的方法

1. 关闭/休眠技术：最大限度的降低空闲能耗，缺点是当使用计算机时需要较长的启动时间，导致系统性能一定程度的下降
2. 电压动态调整技术：为了便于研究，本文假定执行功率为任务整个执行过程的平均耗电功率。根据CMOS 电路动态功率公式P_dynamic~αCV²f 可知，动态功率与电压的平方成正比。因此，降低处理器的电压可以降低处理器的动态功率。但该方法的缺点是，随着电压的下降，处理器的性能会随之下降
3. 虚拟化技术：可实现多个任务在一个计算机的不同虚拟机上运行，通过提高计算机资源利用率，以减少所需计算机数量的方式降低能耗。虚拟化技术实现了计算机资源从物理实体向虚拟实体的迁移，提高了计算机资源的利用率。但虚拟化，特别是深层次的虚拟化本身也要付出高昂的效能代价，因为虚拟化技术通过对底层硬件部件到高层服务应用的层层虚拟，每一级的虚拟都造成了效能的损失。

任务和系统模型

随机任务模型

1. 根据任务对计算机资源的需求特征，可分为计算密集型、通信密集型、数据密集型和I/O密集型等。
2. 随机到达云计算系统的任务可以用三元组（T，Λ，W）表示，第i类任务可以表示为(t_i，λ_i，w_i)。t_i表示第i类任务，λ_i表示t_i任务单位时间平均到达数量，w_i表示t_i任务的计算量

云计算系统模型

1. 现有云计算平台的硬件基础设施通常是架构在大规模廉价服务器集群之上，系统中的不同服务器或计算机通常是由不同公司生产，有不同的硬件配置。这些计算机不仅有不同的功能和性能，其耗电的功率也不同，具体可表现为：功能异构、性能异构、空闲功率和峰值功率异构、执行功率异构；
2. 云计算系统可以定义为六元组：(C，P^busy_m×n，P^idle，P^peak，U_m×n，S)

云计算系统和能耗分析

调度模型

         云计算系统任务调度的过程可描述为：不同类型任务以不同的速率随机到达系统，调度器则根据任务类型、任务到达时机、系统中所有计算机当前的执行状态等信息对任务进行合理映射，最后调度执行
         目的是降低系统运行过程中产生的空闲能耗和执行能耗
         本文暂不考虑云计算系统中与通信相关的能耗和时间开销

问题描述

根据2.1节和2.2节的分析，并结合能耗的计算公式E=P*T，则任意一个任务从进入云计算系统到执行完成离开所产生的期望能耗可表示为

在给定任务类型、确定云计算系统体系结构的条件下，只有调度概率P _ij 的值是根据调度策略的不同而动态变化的，云计算系统的期望能耗与任务和计算机之间的调度策略有关

能耗优化管理

实质

根据任务的到达时间和类型、不同计算机的功率和性能、计算机实时的负载情况，对任务进行合理调度，使系统在满足一定性能的条件下，降低云计算系统运行过程中产生的空闲和执行能耗

假设

1. 根据任务对计算机资源的需求特征，可分为计算密集型、通信密集型、数据密集型和I/O密集型等。不同类型任务要处理的数据形式和问题规模一般不同。为了便于研究，本文假定同一类型任务的计算量相同
2. 由于用户服务请求的自主性、地域的分布性，导致不同用户提交的任务之间通常没有优先约束关系，即任务是独立的
3. 假设对于系统中的每个计算机，任务的到达间隔相互独立,且服从同一参数的负指数分布
4. 每个计算机对不同任务的服务时间也相互独立，且服从同一参数的负指数分布
5. 到达间隔时间与服务时间相互独立
6. 不同类计算任务以不同的概率调度到不同的计算机上

性能约束的最小期望执行能耗调度算法ME³PC(minimum expectation execution energy with performance constraints)

调度器针对不同的情况，采用不同的调度策略，详情请参考第3章

1. 根据负载情况，将节点分在三个队列：C_light、C_normal、C_high，
2. 如果C_light不为空，则优先考虑集合C_light中的计算机，并采用基于大服务强度的任务调度策略，使对tC_i类任务有大服务强度的计算机cC_j有较大的调度概率，其中j∈C_light
3. C_light为空，C_normal不为空，采用基于较小执行能耗的调度策略,使对tC_i类任务有较小执行能耗的计算机cC_j有较大的调度概率，其中j∈C_normal
4. C_light、C_normal为空，C_normal不为空，即所有计算机都处于重载状态。这样，在任务调度时，把任务调度到负载最小的计算机上

定理满足性能约束的最小执行能耗调度算法ME³PC的最坏时间复杂度为O(3mn)，其中，m为任务的类型数，n为云计算系统中计算机的个数。

实验

实验环境的设置

        为了验证ME³PC算法的有效性，本文使用Matlab 的离散事件模拟工具进行模拟实验。实验环境涉及的相关参数以及取值或取值范围见下表。

        实验中任务分为4 类。第i类任务的到达间隔时间服从参数为1/λ_i的负指数分布。该间隔时间可通过负指数分布函数exprnd(1/λ_i)来生成，其中，λ_i的值在[10，15]区间随机生成。根据任务的到达间隔，利用函数cumsum(⋅)可得到第i 类每个随机任务到达系统的时刻。最终可确定所有6000个任务到达系统的时刻。计算机c_j对t_i类任务的服务时间服从参数为1/μ_ij的负指数分布，同样，服务时间也通过函数exprnd(1/μ_ij)来生成，参数μ_ij的值在[1，5]区间随机生成
        为了让模拟系统的运行存在平衡状态，需要满足条件

实验与结果分析

        为了进一步说明ME³PC算法的有效性，本文又设计了最小执行功率调度算法(minimum execution power，简称MEP)，并将ME³PC与MEP、经典MIN-MIN 算法进行比较。其中，MEP的算法思想是:在任务调度时，将任务调度到执行功率最小的机器上，而不考虑该计算机当前的负载情况以及执行该任务的服务时间。MIN-MIN是针对独立任务的动态调度算法，广泛应用于同构或异构分布式并行计算环境，有良好的调度性能。本文分别从系统执行任务的平均能耗、任务的平均响应时间、系统的平均功率、负载平衡和可扩展性这5个方面对3种算法进行对比分析

        从图2可以看出，采用MEP算法时系统的平均功率最小，ME³PC略大于MEP，MIN-MIN的功率最大，且远大于ME³PC和MEP。分析原因是，MEP算法专注于系统执行功率的优化，任务调度时只将任务调度到执行功率最小的机器上，因此系统平均功率最小，但没有考虑调度的机器性能，因此总体性能最差。MIN-MIN算法则相反，只专注于任务的完成时间，而不考虑能耗、负载平衡等其他因素，因此响应时间最小，但是系统平均功率最大。ME³PC算法则同时考虑了功率和性能因素，虽然系统功率较MEP算法平均增加了6.4%，响应时间比MIN-MIN算法平均增加了5.7%，但是任务在系统中的所产生的能耗却最小，如图4所示。究其原因是:（1）由于ME³PC算法针对空闲或轻载计算机采用了大服务强度优先的调度策略，大大降低了系统中计算机出现空闲的概率，使系统的利用率高于MEP和MIN-MIN。其中，采用ME³PC算法时，系统产生的空闲能耗平均是MEP和MIN-MIN算法的81%和73%，如图5所示。（2）由于优先对空闲和轻载计算机进行调度，最大限度地避免了负载不平衡的发生。因此，ME³PC算法保证了系统的负载平衡，如图6（a）、图6（b）所示。可见，只有同时考虑功率和性能因素才能真正降低云计算系统的能耗。

         从实验结果中，我们发现了一个有趣的现象:当计算机个数为1时，3种算法下的系统平均功率、任务平均响应时间和任务平均能耗自然都相等。但是随着计算机个数的增加，系统执行任务的平均能耗却呈线性下降。当计算机个数为8时，系统执行任务的平均能耗最小。随着计算机个数的继续增加，系统执行任务的平均能耗开始增大，且呈指数级增长。究其原因是:（1）当计算机个数从1增加到8的过程中，任务平均响应时间呈指数级减少（如图3所示），但是系统的平均功率的增势却基本趋于平稳（如图2所示），这导致系统执行任务的平均能耗在该过程中是逐渐降低的，并且由于此时系统平均功率的绝对值较小，因此降低的趋势呈线性。（2）当计算机个数从8增加到128的过程中，任务平均响应时间下降的趋势趋于平缓（如图3所示），但是系统的平均功率的增势却呈指数级增加（如图2所示），这导致系统执行任务的平均能耗在该过程中是逐渐增加的，并且由于此时系统平均功率的绝对值较大，因此增长的趋势呈指数级。由此可见，在等能耗的条件下，计算机个数为8时系统有最好的扩展性。对于实际的云计算系统，如何根据系统的体系结构、任务到达的规律确定系统中应该开启或关闭的机器个数，以及开启或关闭哪些机器进行能耗的优化控制，将作为下一步的研究内容。