微信号:SSE-TechService

介绍:上海证券交易所为证券公司、基金管理公司等市场参与者及相关行业机构提供交易技术支持与服务,包括日常交易技术支持、技术交流研讨、市场调查反馈、证券信息技术知识库、测试等服务.

绿色节能云计算资源整合和任务调度关键技术报告(二)

2018-08-06 16:21 上交所技术服务


南京邮电大学课题组
课题主持: 徐小龙
课题研究与主办人:上交所技术有限责任公司 牟亦奇
课题研究员:朱洁 刘茜萍 张栖桐
谌运 刘广沛 胡留赟

3. 主要研究成果

3.1 云数据中心能耗模型与绿色云计算模型

       1、云数据中心能耗模型
       建立云数据中心能耗模型是构建绿色云计算的前提,而建立科学能耗模型的前提是对云数据中心的各个耗电组件进行功耗测量和评估。本项目综合采用实际数据中心调研、硬件测量、理论计算、软件模拟来获得云数据中心的能耗数据,以此作为构建云数据中心能耗模型的依据:
       (1)硬件测量指对被测量的硬件设备外接仪器得到实时的电压和电流,进而算出功率和功耗,该方法需要专用硬件支持;
       (2)理论计算方法为根据工作频率或电压计算其处理器的功耗,根据工作状态计算硬盘等外部设备的功耗,从而计算出整个计算机系统的功耗;
       (3)软件模拟法主要包括以Wattch为代表的峰值功耗估算模型和以SimplePower为代表的动态功耗模拟模型。
       之所以要综合上述三种方法,是因为上述三种方法各有优劣,例如理论计算方法有时会与实际情况有所偏离,精度不高。
       经过本课题组成员经过研究,构建了云数据中心能耗模型。目前数据中心的节点系统的总功耗 主要由3部分构成,不同的设备具体功耗模型不同,但大多数都符合多项式分布,计算式如下:
       Pexecuting(s)=Pstatic+Pdynamic(s)+Paircondition(s)       (1)
       式(1)中的 是系统的静态功耗,即系统处于不执行任何任务的空转状态时功耗,与具体的设备采用的硬件制造工艺和所采用的操作系统软件关系密切; 是任务执行点的工作速率, 是系统的动态功耗,该功耗随着工作速率 变化而变化:
       Pdynamic(s)=μesα,(α>1)       (2)
式(2)中的μe和α为常数,与具体的设备有关。
       Pdynamic(s)是温控系统针对该计算设备的功耗,当任务执行节点的负载加重、工作速率 增加时,执行点的处理器等部件温度也将显著升高,为了继续将设备维持于安全的温度范围内,Pdynamic(s)也必然随着增加;除此之外,Pdynamic(s)还受制于制冷能效比eer 、空间因素 r。设当前的环境温度为 t,安全温度上限为 ρ:





       式(3)中的b是温控设备的基本能耗;由上式还可以看出:制冷能效比eer越高,Pdynamic(s)越低,温控设备需要覆盖的范围越大(即r越大),Pdynamic(s)越高。制冷能效比eer主要取决于设备的制造工艺(产品标准),是比较恒定的参数。在制冷策略上,如果能实现精确的、具有较强针对性的环境温度控制,将可以有效的控制制冷系统的能耗。
       仅用功耗这一指标来衡量系统是否“绿色”并不全面、准确,降低功耗并不总能降低能耗。例如可以通过简单地降低工作速率来减少计算机系统的功耗,但是如果系统处理事务的时间相应地延长了,那么系统总的能耗可能是相等的。系统对能源在时段的总消耗量(即系统能耗)应该受制于功耗和时间两个因素,其计算式为:




       云数据中心为了能够承受服务高峰的负载,保障令用户满意的QoS和系统稳定性,在系统设计、构建时即留有余量,并采用冗余机制。但在非高峰时段,处于“空转”状态的空闲节点将产生不必要的能耗问题。特别是数据中心中各个节点在不同时间的负载不同,导致难以实施精确温控,这种基于热力学稳态系统的工作模式使得数据中心的有效制冷量还不到50%。通过建立热力学散热模型,基于集群功耗的实时监控数据与功耗分配策略进行精确制冷是必然的发展方向。
       2、绿色云计算模型
       本项目组成员将绿色云计算定义为是一种环境友好型的云计算模式,通过构建低能耗、高能效、可持续的基于大规模数据中心的云计算环境,实现合理的资源整合和高效的任务调度,保证整个系统全局服务的高效性和可靠性,达到节能、环保的目的。基于绿色云计算思想和云计算体系架构,设计高效的绿色云计算体系架构,有利于促进各种基于绿色云环境的技术(资源整合、任务调度等)的开发与研究,并推动云数据中心的合理设计。
       本项目通过将原本在云数据中心随机部署的任务、数据与节点、资源的有序化聚集和重新分布,从而充分利用数据中心中的部分计算存储节点,而允许另外一部分计算存储节点处于深度休眠状态或者关机状态,与服务器关联的温控设备也可以处于相应的待机或关闭状态,从而在保障QoS的同时,达到“绿色”节能目标。本项目围绕这一基本思路,从实现绿色云计算的内部和外部因素出发,来建立高能效、低能耗的绿色云计算系统模型,如图6所示。

图6绿色云计算系统模型

       图6中,通过资源配置和任务调度模块实现系统内部计算与存储设备的资源配置和任务调度;通过能耗监测和温控模块实现外部监控系统的控制和调节。重点从绿色云计算系统内部考虑,设计具有低能耗、高效率的资源配置和任务调度模块。其中,资源配置模块保证云计算系统具有足够的计算/存储资源来完成用户提交的各种不同类型的任务;任务调度模块实现云计算系统对不同类型任务的实时调度。绿色云计算系统涉及以下几个主要模块:
       (1)用户交互模块(User Interaction Module,UIM):用户和云端资源交互的接口,该模块帮助用户简化任务的提交过程。
       (2)计算模块(Computing Module,CM)与存储模块(Storage Module,SM):这两个模块由管理节点和任务节点组成,负责具体任务的执行和存储工作,实现用户与云端计算/存储资源的交互。
       (3)资源配置模块(Resource Allocation Module,RAM):对于整体的云计算系统而言,对某种类型的任务节点需求量表现为对某种计算与存储资源的需求量,而资源配置模块负责资源的总体配置,统筹全局的资源分配。资源配置模块包括预测子模块,资源调度器子模块等,采取合理的资源配置策略,调整资源的需求,保证云计算系统具有足够的计算/存储资源来完成用户提交的各种不同类型的任务。
       (4)任务调度模块(Task Scheduling Module,TSM):负责各个不同类型的任务调度,从局部(即任务节点)的角度提高不同类型任务的执行效率,降低管理节点的负担。为了实现高效可靠的任务管理,任务调度模块需要设计一种合理的任务调度模型,配合高效的任务调度算法,提高系统资源的利用率,减少整个云计算系统的总能耗。
       (5)节点状态监测(Node State Monitoring,NSM):负责监测管理节点和任务节点的各种状态,包括任务的执行状态、节点的温度和资源利用率等各类信息,将这些信息汇总并分类汇报给相应的模块,帮助整个云计算系统实现绿色计算。
       (6)能耗监测模块(Energy Consumption Monitoring Module,ECMM):负责监测整个云计算系统的能耗。
       (7)温控模块(Temperature Control Module,TCM):负责监测外界环境温度,根据收集的实时系统温度进行合理性调节,降低系统能耗。

3.2 节能型资源整合和任务调度关键技术

       1、面向绿色云计算任务调度的资源配置算法
       目前大多数面向云计算系统的节能资源配置算法存在以下一些问题:
       (1)云数据中心的规模,当数据中心的规模达到一定程度时,算法的执行时间会成指数级增长,不能满足用户对响应时间的要求,因此不适用于大规模云数据中心;
       (2)任务的多样性,算法仅针对一种类型的任务,而未考虑云数据中心可能接受任务的多样性,适用于特定类型任务的算法,可能不适用于其他类型的任务,因此不能处理多种类型任务的情形,这显然是不合理的;
       (3)调整的时机,有些研究工作只根据当前时刻的任务到达量来进行调整,没有考虑调整算法及节点调整的时间开销,导致调节落后于负载请求的变化;
       (4)预测算法的准确性,不论采用何种预测算法,预测值都有可能存在或多或少的误差波动,导致出现预测值小于实时负载值的情况,系统实时性要求得不到保障,除此之外,预测值的频繁波动,导致系统稳定性极差,不能满足实际需求。
       (1)多目标约束优化模型
       实现面向绿色云计算任务调度的资源配置算法,是本项目的研究重点之一。经过研究,本项目提出了一种灵活的“关闭冗余,开启需求”的资源预配置策略,根据提出的资源配置模型,基于虚拟化技术,将任务调度问题抽象为虚拟机部署问题;其次,预测用户请求的负载大小,结合当前系统状态和资源分布,采取保守控制策略,计算下一个周期内任务对系统资源的需求量;然后,建立满足多目标约束的能耗模型,提出基于概率匹配的资源配置算法,实现低能耗资源配置。在该算法的基础上,提出面向绿色云计算的新型资源配置算法,进一步降低系统能耗。预测算法和保守控制策略应能够有效避免资源配置滞后于用户请求的问题,提高系统的响应比和稳定性;提出的资源配置算法能够激活更少主机,实现激活主机集合之间更好的负载均衡和资源的最大化利用,降低云计算系统能耗。
       不同类型的任务对计算资源的需求是不同的,所以将任务分类为计算密集型任务、数据密集型任务、通信密集型任务、和I/O密集型任务等不同类型。假设有M种类型的任务,在某一时刻系统需要处理的每种类型任务的总数为Mio根据不同类型的任务对计算资源的需求,将不同类型的任务调度到匹配类型的虚拟机上,完成任务的执行。即第i(1≤i≤M)种类型的任务taski调度到VMi上执行:<taski>→<VMi>,i∈(1,M)。对于用户提交的各种类型的任务量,需要多个相应类型的虚拟机来执行。为了分析问题的方便:现将任务的调度问题抽象为“以尽可能最优的方式,将能够满足用户需求的多个虚拟机调度到规模为N的节点(Host)集群上, 实现最高能效比”,即:<VMi>→<hostj>,i∈(1,M),j∈(1,N)。将任务调度到相应类型的虚拟机上,需要考虑到虚拟机的分布和当前状态。
       对于所有物理主机集合:<hostj>=(host1,host2,,hostj,,hostN)和虚拟机类型集合:<VMi>=(<VM1>,<VM2>,,<VMi>,,<VMM>),定义M×N状态统计矩阵AMxN。其中AMxN矩阵中的元素aij定义为:VMi类型的虚拟机在hostj上启动的总个数。对于所有的物理主机集合:<hostj>和任务类型集合:<taski>,定义M×N的平均速率矩阵UM×N。矩阵中的元素uij定义为:taski类型的任务在hostj上执行的平均速率(平均执行时间为1/uj)。集群中的物理主机的总数为N。对于启动的n(n≤N)个物理主机,每个物理主机(hostj)上启动的各类虚拟机副本总数为qj,负责执行相应类型的任务,虚拟机处于运行/空闲状态。定义状态量Rik表示在该物理主机上的第K个虚拟机(类型为 VMi),是否正在执行相应类型的任务,即表示为,其中:i∈{1,M},K∈{1,,MJ}。
       通过分析集群和各个相应类型的虚拟机状态及分布,结合合适的预测算法,可以提前做出相应的控制行为,在提高云计算平台的资源利用率,降低能耗的同时,可以提高系统的实时响应比和稳定性。
       对于所有物理主机集合:<hostj>和虚拟机类型集合:<VMi>,定义M×N的开启控制矩阵StartM×N。矩阵中的元素Startij定义为:在hostj上启动Startij个VMi类型的虚拟机。对于所有物理主机集合:<hostj>和虚拟机类型集合:<VMi>,定义M×N的关闭控制矩阵ShutM×N。矩阵中的元素Shutij定义为:在hostj上关闭Shutij个VMi类型的虚拟机。本项目提出的绿色云计算系统模型中,对于所有的物理主机集合:<hostj> ,VMi类型的虚拟机在某一次资源预配置的过程中需要控制开启或关闭的总数分别定义为
       通过上面的讨论,我们得出这样的结论:云计算平台产生的能耗主要取决于开启的主机数和虚拟机数,频繁的开关机同样会带来巨大的额外能耗。使需求的资源配置在尽可能少的主机上可以提高能效,降低能源消耗。本项目采取“关闭冗余,开启需求”类型的虚拟机,提高集群整体的能效比。
       本项目把每个物理主机的可用资源抽象为一个二维向量hostj:(MIPSjremain,Memjremain),MIPSjremain代表hostj的可用CPU资源,Memjremain 代表hostj可用的内存空间。向量空间分析如下:
       (1)主机内存空间(Mem)的大小决定了该主机能够同时运行虚拟机的数量,也就是说,没有足够的剩余内存无法启动更多的虚拟机。分配给所有虚拟机的Mem总和不得超过物理主机Mem上限。
       (2)主机CPU内核单元是所有虚拟机共享的,本项目采用虚拟机时间共享策略。内核为每个虚拟机分配时间片。所有虚拟机运行时,CPU峰值不得超过主机的承受能力。本项目使用MIPS(Million Instructions Per Second,每秒百万级机器语言指令数速率)来衡量CPU性能,即分配给所有虚拟机的MIPS总和不得超过物理主机CPU的MIPS上限。
       选取二维向量:hostj:(MIPSjremain,Memjremain)作为物理主机的资源空间。每个虚拟机亦选取二维向量:VMi:(mipsi,memi)作为虚拟机的资源需求,即:hostj:(MIPSjremain,Memjremain),VMi:(mipsi,memi)。
       综上所述,将所要研究的问题建立为多目标约束优化模型,其数学形式如下所示:
       Min:        式(5)中表示开启的主机和虚拟机产生的稳定能耗,正比于集群开启的主机总数n和各个主机上开启的各类虚拟机总和qj,pjhost,pjvm 分别表示主机hostj的功耗和开启每个虚拟机需要增加的功耗;式(6)中 表示开关虚拟机和物理主机所带来的额外控制能耗,其中等于开启虚拟机过程产生的额外控制能耗,等于关闭虚拟机过程产生的额外控制能耗,等于开启主机过程产生的额外控制能耗,等于关闭主机过程产生的额外控制能耗。分别表示在主机hostj上开启虚拟机的瞬时功率、开启虚拟机的时间、关闭虚拟机的瞬时功率和关闭虚拟机的时间,分别表示开启主hostj的瞬时功率、开启时间、关闭主机hostj的瞬时功率和关闭时间;在约束式(7)中,表示开启的相应类型的虚拟机总数等于测算需要开启的虚拟机个数,约束式(8)表示关闭的相应类型的虚拟机总数等于测算需要关闭的虚拟机个数;约束式(9)和(10)分别指明集群中物理主机的可用CPUMem资源对虚拟机的约束。
       (2)任务量预测方法
       为了提高云计算平台的系统资源利用率,降低系统能耗,需要对集群中各个物理主机资源进行配置,完成虚拟机的调度。在此过程中,通过查看物理主机和虚拟机实时信息的方法,只能够得到当前时刻物理主机和虚拟机的负载状况,资源配置过程始终滞后于用户请求。因此,本项目依托合适的负载预测模型,采取保守控制策略,对云计算系统内不同类型任务的到达量进行周期性预测和控制,从而实现合理的资源预配置,避免资源配置滞后于用户请求的问题。
       为了使资源配置能够持续满足各类任务对资源的需求,避免资源配置滞后于用户请求的问题,需对下一时刻周期内各类任务的到达量进行预测。针对不同的任务类型、预测周期和应用场景,需要选取不同的预测算法,如指数平滑法、周期分析法、趋势外推法和马尔科夫预测模型等。本项目利用三次指数平滑算法预测相应类型负载的大小。预测周期的大小应当取决于任务的执行时间、算法耗时、物理主机和虚拟机的开关机耗时等因素。如果选取的预测周期过短,对系统的稳定性会产生较大的影响,同时会增大系统控制能耗的开销。云计算服务提供商可以根据不同的情况合理选择预测周期的大小。
       假设系统当前处于第k个周期,第k+1个周期taski类型的任务预测值表示为:
其中的参数分别为:



       其中:xi(k)为第k个周期内taski类型任务的实际负载值;α为平滑系数,取值在(0,1)之间。使用三次指数平滑法需要关注初始值 的选取问题。
       不论采用何种预测算法,预测值都有可能存在或多或少的误差波动,导致出现预测值小于实时负载值的情况,系统实时性要求得不到保障,除此之外,预测值的频繁波动,导致系统稳定性极差,不能满足实际需求。为了解决上述问题,本项目在采用三次指数平滑法预测的基础上,采取保守控制策略:假设在第k+1个周期, 类型的任务等待集群系统处理的任务总量在之间,其中为: 其中,ci(k)表示集群当前时刻需要处理taski类型的任务总量;ξi表示预测波动误差;表示在T周期内当前集群对taski类型的任务处理能力。定义实时响应比γ:

       表示下一时刻taski类型的任务等待处理的任务总量(cif(k+1))和需要相应类型的虚拟机总数(Vif(k+1))之间的比值。当γ为1时,理论上达到最高响应比。由分析可知: 表示当前集群中VMi类型虚拟机总数。
       采用上述保守控制策略,能够有效的提升系统的响应比和稳定性。

       (3)基于概率匹配的资源配置算法
       依托多目标约束优化模型,本项目提出的低能耗的资源配置算法旨在实现激活主机集合之间更好的负载均衡性和资源的最大化利用。经过研究,我们提出了一种基于概率匹配的资源配置算法RA-PM
       在开启/关闭的过程中,需评估可用物理主机的适用性,从而决定所需控制的虚拟机选择哪些物理主机来处理相应的控制策略。这取决于多种因素,包括物理主机的硬件资源使用情况、已启动虚拟机的分布和虚拟机的资源要求等。由于本项目采取了“关闭冗余,开启需求”类型的虚拟机,因此选择每个物理主机当前开启的虚拟机的总数qj来对主机的适用性进行划分,定义适用性划分阈值qthreshold
       (1)qj>qthreshold选出 的主机,加入高适用主机集合;
       (2)0<qj<qthreshold选出 的主机,加入低适用主机集合;
       (3)0=qj选出 的主机,加入休眠主机集合。
       对于需要关闭类型的虚拟机,优先从低适用主机集合中关闭相应空闲的虚拟机,适当迁移低适用主机集合中的虚拟机,减少开启的主机个数;如果在低适用主机集合中的虚拟机都不满足关闭要求,从高适用主机集合中关闭相应空闲的虚拟机。对于需要开启类型的虚拟机,优先从高适用主机集合中开启相应的虚拟机;如果在高适用主机集合中的虚拟机都不满足开启要求,再从低适用主机集合中开启相应的虚拟机;如果还是不能满足开启要求,就从休眠主机集合中激活新的主机。
       在资源配置的过程中,需要考虑到高适用主机集合之间负载的均衡和资源的最大化利用。在虚拟机调度过程中,需要均衡物理主机硬件资源的使用,防止其出现 “木桶效应”。该效应表现为CPU利用率过高、但内存利用率低下,或者CPU利用率低下、但内存利用率过高。所以RA-PM算法在选择控制目标主机的过程中,考虑了待放置虚拟机与目标物理主机的匹配程度,定义VMi类型的虚拟机对主机hosti的匹配函数:

       其中为常系数。μ越大,MRv表明VMi类型的虚拟机对主机hosti匹配程度越高。主机对当前待分配虚拟机接受的概率取决于匹配概率和对该虚拟机的容量大小。考虑到所选主机集合的负载状况,能够使得激活主机集合获得更好的负载均衡,待分配虚拟机被当前主机接受的概率定义为:
       依据式(24)选择一个合适的物理主机来放置该类型的虚拟机。
       虚拟机和主机匹配过程如下:
       步骤 1 遍历待放置虚拟机队列。记当前需要放置的虚拟机类型为VMi
       步骤 2 选择满足条件的主机集合,策略如下:
              a) 计算当前高适用主机集合中每个物理主机所能容纳VMi类型的虚拟机能力: ,若,则转步骤3,否则:
              b) 计算当前低适用主机集合中每个物理主机所能容纳VMi类型的虚拟机能力: ,若,则转步骤3,否则:
              c) 计算休眠主机集合中每个物理主机所能容纳VMi类型的虚拟机能力: ,转步骤3;
       步骤 3计算所选主机集合中每个物理主机与VMi类型的虚拟机的匹配程度:MRv
       步骤 4 从所选主机集合中选择物理主机来放置该类型的虚拟机。选择一个合适的物理主机来放置该类型的虚拟机,且 Stratij++;
       步骤 5 用下式刷新被选物理主机资源(hostj):        若所选主机集合为低适用主机集合,将该主机归类为高适用主机集合类型;若所选主机集合为休眠主机集合,将该主机归类为低适用主机集合类型。
       步骤 6 若虚拟机放置队列遍历结束,则程序终止,否则转步骤1。
       上述方法先对可用物理主机的适用性进行评估,考虑受控虚拟机与目标物理节点的匹配程度,相比传统的任务调度算法,在资源配置的过程中,该算法能够实现激活的主机集合之间更好的负载均衡和资源大的最大化利用,激活更少的主机,降低系统的能耗,实现高效能绿色云计算。但该算法本身存在固有的缺陷:得到的解只是可行解,并非最优解。为了尽可能得到资源配置最优方案,进一步地,本项目拟引入基于改进型模拟退火的资源配置算法,搜索全局近似最优解,完成资源的配置。
       对于求解多目标约束最优解的过程为NP-hard问题。为快速搜索出近似最优解,本项目拟采用基于改进型模拟退火的资源配置算法完成资源的配置。在传统模拟退火算法的基础上增加“存储环节”来记录最优解,避免搜索过程中由于执行“概率接受”而遗失当前遇到的最优解。
       算法的思想为:从产生的初始解和初始温度值开始,重复“产生扰动解→ 接受或舍弃扰动解为当前解→记录最优解”的迭代,并逐步衰减温度t,算法终止得到最优解。在当前解的领域结构内以一定概率“产生扰动解”,尽可能保证了扰动解遍布全部的解空间,其中解空间满足多约束条件;“接受或舍弃扰动解”依据了Metropolis准则:在温度t时趋于以e-(ΔE/kt)为概率接受扰动解,其中ΔE为扰动解和当前解能耗差值,k为Boltzmann常数;“记录最优解”是为了记忆到当前状态为止的最优解;采用算法得到的最优解,部署需求虚拟机到主机集群中;刷新主机信息。
       不同的开启控制矩阵StartM×N构成算法的解空间,其中解空间满足多约束条件。虚拟机采用的放置策略是算法产生解空间的关键因素。通过产生初始解,在内循环对当前解进行适当扰动,产生扰动解,实现局部最优解搜索;当内循环结束,进入外循环,重新产生新解,跳出当前解的局部近似最优解搜索,通过内外循环完成全局近似最优解搜索,使得资源预配置的过程消耗更少的能耗。
       (4)基于改进型模拟退火的资源配置算法
       RA-PM算法是一种低能耗资源配置算法,先对可用物理主机的适用性进行评估,考虑受控虚拟机与目标物理节点的匹配程度。相比传统的任务调度算法,在资源配置的过程中,RA-PM算法能够实现激活的主机集合之间更好的负载均衡和资源大的最大化利用,激活更少的主机,降低系统的能耗,实现高效能绿色云计算。但该算法本身存在固有的缺陷:得到的解只是可行解,并非最优解。为了尽可能得到资源配置最优方案,进一步地,本项目引入基于改进型模拟退火的资源配置算法,搜索全局近似最优解,完成资源的配置。
       为快速搜索出近似最优解,本项目采用基于改进型模拟退火的资源配置算法完成资源的配置。在传统模拟退火算法的基础上增加“存储环节”来记录最优解,避免搜索过程中由于执行“概率接受”而遗失当前遇到的最优解。
       算法运算过程中涉及的三个解方案,分别用于记录最优解、当前解和扰动解及对应的能耗;第2行初始化算法所需的最高温度、最低温度、当前温度迭代次数和当前温度值;第3、4行分别用于获取所需启动的虚拟机信息和当前主机集群信息。
       算法主体过程,从产生的初始解和初始温度值开始,重复“产生扰动解(GetNewSolution())→ 接受或舍弃扰动解(PerturbationSolution)作为当前解(CurrentSolution)→ 记录最优解(OptimalSolution)”的迭代,并逐步衰减t值,算法终止得到最优解OptimalSolutionRA-ISA算法中,在当前解的领域结构内以一定概率“产生扰动解”,尽可能保证了扰动解遍布全部的解空间。“接受或舍弃扰动解”依据了Metropolis准则:在温度t时趋于以e-(ΔE/kt)为概率接受扰动解;“记录最优解”是为了记忆到当前状态为止的最优解。
       最后采用算法得到的最优解,部署需求虚拟机到主机集群中;刷新主机信息。虚拟机采用的放置策略是RA-ISA算法产生解空间的关键因素。通过RA-PM算法产生初始解,在RA-ISA的内循环内,对当前解进行适当扰动,产生扰动解,实现局部最优解搜索;当RA-ISA的内循环结束,进入外循环,重新通过RA-PM算法产生新解,跳出当前解的局部近似最优解搜索。RA-ISA算法通过内外循环完成全局近似最优解搜索,使得资源预配置的过程消耗更少的能耗。
       (5)实验验证与性能分析
       本节从不同角度出发,衡量调度算法性能。实验将针对预测算法和控制策略的准确性、算法的耗时和能耗、开启的主机集群内资源的利用率和激活的主机数等指标来展开实验分析。将本项目提出的低能耗任务调度算法对比于基于性能选择的贪婪算法(Greedy)和分组遗传算法GABAGreedy算法在选择物理主机放置虚拟机的过程中,总是选择能够放置该虚拟机最多的主机,以此获得当前集群性能上的最优;GABA则基于二次指数平滑算法实现负载的预测。下文所有的实验结果均为实验25次后取平均值所得的结果。
       本项目在数据中心部署3种类型的任务,其中2种类型采用2005年WLCG (Worldwide LHC Computing Grid)数据中心采集的数据。依据数据集合中用于区分系统资源分配大小的组ID,选择前10天内提交的任务,每隔4小时来进行统计。采用其中较为典型的2组数据:lcg-1、lcg-2。第3种类型的任务请求采用现实中常见的泊松分布p-3。数据集如图7所示:
       算法的时间开销受到待配置虚拟机的数量、种类和主机节点的规模等因素的影响。实验中,每一种类型的待配置虚拟机数量相等。图8(a)©(e)(g):控制所有类型的待配置虚拟机总数为1000(不同类型的虚拟机数量相等),考察待配置虚拟机的种类和主机节点的规模对Greedy、RA-PM、GABARA-ISA算法耗时的影响,从图中可以看出Greedy、RA-PM、GABARA-ISA算法随着集群主机规模的增大,算法耗时呈现类线性增长,而待配置虚拟机的种类对算法的影响很小;图8(b)(d)(f)(h):控制待配置虚拟机种类为5,考察待配置虚拟机的数量(不同类型的虚拟机数量相等)和主机节点的规模对Greedy、RA-PM、GABARA-ISA算法耗时的影响,从图中可以看出Greedy算法随着待放置虚拟机数量的增大,算法耗时增速小于RA-PM、GABARA-ISA算法。由分析可知:RA-PM算法耗时略大于Greedy算法,对待配置虚拟机的数量(任务数量)和集群规模的时间复杂度为O(MN);GABARA-ISA算法耗时远大于RA-PM算法和Greedy算法。在采用GABARA-ISA算法时,需要考虑到资源预配置的周期:采用GABARA-ISA算法对资源预配置的周期有较高的要求,如果资源预配置的周期过短,即预测周期小于GABARA-ISA算法耗时,则GABARA-ISA算法失效,这也是所有求解多目标约束最优解的共性,宜采用RA-PM算法。RA-ISA对比于GABA算法(进化250次),我们可以发现RA-ISA算法耗时更短,效率更高。

图8Greedy、RA-PM、GABA和RA-ISA算法的时间开销

       为了衡量两种算法的能耗,我们将这两种算法对比于GreedyGABA算法。仿真设定系统中存在5种粒度的虚拟机划分,集群规模为1500个节点,图9显示了待放置虚拟机数量和系统能耗的关系。从图9分析可知:GABA、RA-PMRA-ISA算法相比Greedy算法在能耗上减少了2-4倍;随着待放置虚拟机数量的增加,RA-ISA算法比RA-PM和GABA算法的优势愈加明显,消耗更少的能耗。在资源预配置周期允许的情况下,采用RA-ISA算法优于RA-PMGABA算法。但是我们应该注意到RA-PM算法耗时明显快于GABARA-ISA算法,如果预测周期很短,RA-PM算法更好。
       利用三次指数平滑算法实现各类负载大小的预测,平滑系数α取值为0.5,为了衡量系统预测与保守控制的效果,我们取实时响应比γ为1,各类实时提交的任务与三次指数平滑算法预测的任务如图10 (a)中所示。由图10(a)分析可知:存在较多的预测值小于实时提交的任务。对于实时性要求比较高的任务,将导致该种任务不能达到响应比为1的要求。本项目在三次指数平滑算法的基础上提出保守控制策略,实验效果如图10 (b)所示。为了更加直观的分析控制效果,我们以LCG第一种任务为例,图10 ©显示了实时提交的任务、预测值和控制值之间的关系。由图10 ©分析可知:对于存在较大波动的任务,采取的保守控制策略有效的提高了系统的实时响应比和稳定性。同时,我们以lcg-1为例,给出GABA算法中采用的二次指数平滑预测算法和本项目提出的预测算法实际开启虚拟机的个数,详细结果如图10 (d)所示。
       Greedy、RA-PM、GABARA-ISA算法都采取“关闭冗余,开启需求”的策略。在相同的预测算法和控制策略情况下,图11列出了数据中心在资源预配置的过程中采用三种不同预配置算法开启主机的MIPS利用率。从图11可以看出,Greedy算法的整体利用率大约在25%-60%之间,RA-PM算法的整体利用率大约在80%-90%之间,两者波动比较大;GABARA-ISA算法利用率保持在90%左右,系统表现平稳。
       为了更加直观的表现在该云计算系统模型下的资源使用情况,我们对Greedy、RA-PM、GABARA-ISA算法激活的主机数做出分析,如图12所示:数据中心共900个主机节点,部署3种类型的任务,相比传统的Greedy算法,RA-PM 、GABARA-ISA算法激活了更少的主机数,实现了激活主机集合之间更好的负载均衡和资源的最大化利用。
       数据中心在虚拟机部署时分别采用Greedy、RA-PM、GABARA-ISA算法,在各个时刻产生的功耗如图13所示。由图13分析可知:在资源预配置的过程中,RA-PM算法相比传统的Greedy算法,平均减少约40%的功耗;GABA算法相比于RA-PM算法,平均减少约10%的功耗;同时,RA-ISA 算法相比于GABA算法,平均减少约8%的功耗。RA-PMRA-ISA算法能够降低系统的能耗,实现高效能绿色云计算。尽管GABA 算法相比于RA-PM 算法可以节约更多的能耗,但是其耗时是巨大的。我们再次重申:如果预测周期很短,RA-PM算法优于GABARA-ISA算法。

2、面向绿色云计算的低能耗任务调度策略

(1)调度模型

tab>面向绿色云数据中心的低能耗任务调度策略基于以下两个目标:一是使工作节点的数量同当前的任务量匹配,其余的节点在低能耗或休眠的节能模式下运行;二是让每一个节点的存储方式和计算能力同该节点所分配的工作负载匹配,避免因节点不充分利用而造成的资源和能源浪费。

       Srikantaiah等证明了对于某个确定的云数据中心存在一个最优资源配置值,在最优资源配置时每进行单位次运算所消耗的能量最低;基于这个最优资源配置值,将整个过程抽象为一个二维装箱过程,目标是在用尽可能少的箱子的前提下,尽可能的装满每个箱子(即尽可能的接近最优资源配置值)。这种方法可以从一定程度上降低数据中心的能耗,但仍存在以下三个问题:
       (1)没有充分考虑云数据中心的规模。随着云数据中心规模的增大,该算法为某一个任务选择出合适的节点的时间呈指数增长,考虑到云数据中心本身所具有的海量节点,该算法并不能在合理的时间内提供合适的结果。
       (2)没有充分考虑数据中心节点本身的复杂情况。目前的云数据中心,节点通常被分为多种运行状态。算法并没有考虑到这一点,不能够针对节点的多种状态进行有效的区分,而是将所有节点都视为同一状态的节点进行任务分配。导致云数据中心大量休眠节点被不必要的激活,造成额外的能源浪费。
       (3)没有充分考虑云数据中心可能接受的任务的复杂情况。云数据中心作为一个开放的平台,很可能在同一时段接受大量各种不同的任务。目前算法不能够提供一个合适的方法来对不同的任务进行有效的区分。当同一时段有大量任务时,常常采取简单的先来先服务策略,这显然缺乏合理性。
       研究表明:运行在低利用率和高利用率的服务器所产生的热量和消耗的电力十分接近,单个服务器节点在CPU利用率低的情况下所产生的能耗与得到充分利用的情况下所产生的能耗相差无几。当磁盘利用率一定时,CPU利用率在10%和80%的情况下所产生的能耗差别很小。
       为了有效设计和部署面向大规模云数据中心的低能耗任务调度策略,本项目首先构建节点模型和任务模型,目的是将云环境下的复杂情况进行了有效的抽象,这种抽象不仅可以反应出云数据中心在进行任务调度的实际情况,也能够有效屏蔽其他干扰因素。
       数据节点可被抽象为以下四元组:DN=(ID,CPU,DIO,State)。其中ID为数据节点的唯一标识;CPU为数据节点的当前CPU利用率,DIO为数据节点当前的磁盘传输速率,这两个指标用于表示数据节点当前已使用的计算能力;State为数据节点当前状态。
       对于一个特定规模的云数据中心,存在着一个CPU利用率和当前磁盘传输速率的最优资源组合。
       最优资源配置(Optimal Configuration of Resource Utilizations,OCORU),可被抽象为以下二元组:OCORU=(CPU,DIO) 。当该云数据中心的每个数据节点的DN.CPUDN.DIO都工作在ORORU.CPUORORU.DIO时,整个云数据中心处理单位数据的能耗最低,即此时每消耗单位电力所获得的回报最高。对某一特定的云数据中心OCORU.CPUOCORU.DIO均为常数,可实际测得。
       任务(Task)可被抽象为六元组:Task=(ID,Data,Code,CPU,Amount)。其中ID为任务的编号,是该任务与其他任务相区别的唯一标识;Data表示用户向云计算中心提交的,其想要处理的原始数据,将会被管理节点切分成多份子数据,以便分布在若干个数据节点上进行处理;Code表示用户向云计算中心提交的处理Data的程序代码,Code中用户包含处理Data的方法和这些方法与Data的映射关系;CPU表示运行该任务所需的CPU利用率,管理节点只向 的数据节点派遣该任务的子任务;DIO表示运行该任务所需的DIO利用率,管理节点只向OCORU.DIO-DN.DIO>Task.DIO的数据节点派遣该任务的子任务;Amount表示该任务子任务的数量,对于特定环境的特定任务而言是一个常数。
       用户租用云计算中心的设备,需要向云数据中心提供其想要处理数据以及处理数据的程序代码,管理节点将用户提供的任务切分成若干个的子任务分布到数据节点上执行。
       子任务(SubTask)可被抽象为三元组:SubTsak=(ID,Data,Code)。其中ID为子任务的编号,每个子任务有且只有一个与其他子任务不同的编号,是这个子任务与其他子任务相区别的唯一标识;子任务的ID与任务的ID存在对应关系,可以通过子任务ID推知这个子任务属于哪个任务;当所有子任务完成后,管理节点依据子任务的ID将结果有序汇总后返回给用户。Data表示由管理节点将用户提交的原始数据切分后得到的子数据。Code表示用户提交的代码中与该子任务的子数据相映射的部分代码,包含了该子任务相关的子数据的处理方法。

(2)基于胜者树的低能耗任务调度算法

       一个大规模云数据中心的任务调度问题可以抽象为以下情况:云数据中心的最优资源配置值为(OCORU.CPU,OCORU.DIO),共有n个处于活跃态的同构数据节点和k个处于休眠态的数据节点,第i个处于活跃态的数据节点表示为(DNi.CPU,DNiDIO)。任务Task被切分成Task.Amount个子任务 {SubTask1,SubTask2,SubTask3……SubTaskTaskAmount},管理节点需要将这Task.Amount个子任务部署在云数据中心的数据节点上。
       本项目引入胜者树模型,提出一种基于胜者树的低能耗任务调度算法:
       (1)将所有n个数据节点作为一棵完全二叉树的叶节点,从能耗的角度将所有叶节点进行两两比较,较低能耗的节点作为优胜者,依此可以比较得到[n/2]个优胜者,作为叶节点上面一层的非叶节点保留下来;
       (2)然后再对这[n/2]个非叶节点进行两两比较,如此重复,直到选出根节点为止,根节点即为最合适的数据节点。
       (3)当部署剩余子任务时,并不需要重新初始化胜者树并计算出该胜者树的根节点,而只需重新执行从根节点对应的外部节点到根的路径上的所有比赛即可。
       在用完全二叉树定义胜者树时,用数组e[1…n]表示n名参加比较的数据节点的节点编号,用数组t[1…n-1]表示组成的完全二叉树的n-1个内部节点,t[i]的值是数组e[ ]中的比较优胜者的下标。图14给出了n=5时的胜者树中各节点与数组e[ ]和t[ ]之间的对应关系。
       假设有两个数据节点DNAA,DNBBDNAA的当前CPU利用率为30,磁盘传输速度为30 (表示为(30,30)), DNBB的当前CPU利用率为40,磁盘传输速度为10 (表示为(40,10))。管理节点将选择两个节点中的一个来承担某一需求(10,10)的任务,云数据中心的最优资源配置值为(80,50)。该方法首先计算欧几里得距离 ℑ,数据节点DNA的初始距离,数据节点DNBB的初始距离。若将任务分配给 DNAA则分配后的距离变为41.2,若将任务分配给DNBB则分配后的距离变为42.4。把作业分配给数据节点DNAA后使得数据节点DNAA和数据节点DNBB的总的欧几里得距离更大,所以选择此方案。
       云系统是开放的大型多用户系统,这很大程度上增加了问题的复杂性,在同一个时段,多个用户都提交了各自的任务。若此时同时有(10,10)和(50,20)两个任务。按照初始算法,将(10,10)分配给节点DNAA后变为DNAA(40, 40),DNBB(40,20)此时为了部署(50,20)的任务需重新激活一个休眠节点,成为有三个数据节点(40,40)、(40,20)和(50,20)的情况。若先部署(50,20)的任务,可知DNAADNBB中只有前者有能力承载该任务,于是将其分配给DNAA。后再部署 (10,10)任务此时只有DNB有能力承载该任务,于是分配给DNBB。最终只有两个数据节点分别为(80,50)、(50,50)。第一种分配方式不仅比第二种多用了一个数据节点,而且每个数据节点距离最优资源配置值都有一定的差距,从节能的角度来说显然第二种分配方式更为合理。
       计算量小的任务有更好的灵活性,优先部署大任务后再部署小任务,往往可以利用小任务的灵活性填补数据节点剩余的计算资源以接近最优资源配置,而不用激活休眠节点,减少了系统的开销。
       我们将多任务的情况抽象为如下形式:假设有m个任务,云数据中心共有n个处于活跃态的同构数据节点和k个处于休眠态的数据节点,管理节点需要将这m个任务部署在云数据中心上。数据中心的最优资源配置值为(OCORU.CPU,OCORU.DIO),所有节点均运行在该值之下。
       在云数据中心同时收到多个任务的情况下,本项目的基于胜者树的多任务调度策略采取大任务优先的调度原则:先利用胜者树对所有任务进行排序,将比较系数大的任务选择为胜利节点,重复进行比赛,由此可得到一个优先级由大到小的任务队列。管理节点按所得的任务队列再依次进行分配,直到所有任务都分配完毕为止。

       (3)实验验证与性能分析

       下面针对调度所需时间、低利用率节点比率、休眠节点数量和任务能耗等指标,将本项目提出的低能耗任务调度策略对比于原始的资源整合算法来展开实验分析。基于数据中心的节点状态和任务状态均为系统随机生成,为了更准确的反应实际结果,所有的实验结果均为实验100次后取平均值所得的结果。
       图15是当任务数为300时,不同规模的数据中心的管理节点为每个子任务计算出所要部署的数据节点的耗时图。RIA表示资源整合策略(Resource integration algorithm,RIA)LTSA-M即本项目提出的基于胜者树的多任务调度策略。可以看出RIA随着数据中心规模的不断增大,性能损耗越发明显,已经不能够胜云环境下大规模数据中心的任务调度工作。对比于RIALTSA则衰减的非常平缓,具有明显的性能优势,当云数据中心的活跃节点的数达到15000时依然能够在10s之内得到结果。可见LTSA大规模节点的前提下依然能够在可以接受的时间内得到结果。
       如图17所示,随着任务数的逐渐增加,云数据中心需要激活休眠节点才能满足任务的需求。对比与FCFS策略,LTSA-M策略由于采取了更合适的任务优先顺序,因此只需要激活少量的休眠节点便可部署完成所有任务。当任务数量为1800时,采用FCFS策略的数据中心的休眠节点已经所剩无几,而采用LTSA-M策略的数据中心只激活了极少量的数据节点便部署完所有任务。
       相比FCFS算法,LTSA-M算法能够让每一个节点的计算能力同该节点所分配的工作负载更加匹配,避免因节点不充分利用而造成的能源浪费;在此基础上也能够使活跃节点的数量同当前的任务量匹配,有效的减少不必要的活跃节点的数量。
       为了得到最优的能耗比,我们采取了穷举法,对每一个Mix穷尽了所有的可能,从而找出最优值。
       如图18所示,Mix1任务之间的差别较小,因此FCFS与LTSA-M两种策略所得的结果都十分接近,这导致两种调度策略所对应的能耗比非常接近。而Mix2由于各个任务之间的差别非常明显,相比FCFSLTSA-M算法则可以更加接近最优策略,在节能方面的表现更加优秀。

未完

注意:由于该报告篇幅较长,将分多期推送


 
免责声明


本公众号内容仅供参考。对任何因直接或间接使用本公众号内容而造成的损失,包括但不限于因有关内容不准确、不完整而导致的损失,本公众号不承担任何法律责任。如有问题请反馈至tech_support@sse.com.cn。

-------------------------- 上海证券交易所为证券公司、基金管理公司等市场参与者及相关行业机构提供交易技术支持与服务,包括日常交易技术支持、技术交流研讨、市场调查反馈、证券信息技术知识库、测试等服务。

点击"阅读全文"了解详情

 
上交所技术服务 更多文章 绿色节能云计算资源整合和任务调度关键技术报告(一) 【通知】关于开展收盘集合竞价、综业EzCS及FAST行情全网测试的通知 高效内存数据库及索引算法的研究报告 结合容器技术的行业云可行性方案研究报告(三) 结合容器技术的行业云可行性方案研究报告(二)
猜您喜欢 【成都站】安卓巴士·成都站火热报名中! 是这个人,一步步把“深度学习”从边缘课题变成Google等网络巨头仰赖的核心技术 我眼中的 DaoCloud 奔跑吧,途牛人 【解密】在这个看脸的时代,你居然让我看嘴!