目前,大规模计算系统采用并行技术可具高吞吐信息服务和海量数据处理能力,在科学计算和金融等领域需求迅猛增长^[1].随着规模的不断扩大,异构计算聚合广域分布的各种同构与异构的计算机、工作站、机群、群集、数据库、高级仪器和存储设备等资源,可形成对用户相对透明的、虚拟的高性能环境^[2].并行系统效能的高低,很大程度上由部署在体系架构上的资源管理系统决定^[3].任务调度是资源管理的核心,为了优化某个目标函数,其在一组具有任意特性的处理机中对任务集合进行排序和资源分配^[4].当前,同构调度问题已被广泛研究^[5];但异构调度,鉴于其复杂性、环境的多样性、应用的新需求和调度目标的折衷性等,是一个亟待解决的高维多模优化难题^[6].

与此同时,绿色计算因为与环境保护和人类可持续发展的密切关联,引起越来越多的社会关注^{[7, 8]}.2010年,信息技术(information communication technology,简称ICT)产业能耗占到总的全球电能消耗的8%、全球能耗的25%,成为全球第五大耗能产业;ICT设备的CO₂排放占到全世界排放总量的2%~2.5%,这个数字跟全世界航空运输业相当,并约等于汽车CO₂排放的1/4.之后,ICT总能耗逐年增长5%,数据中心占其40%.2011年,中国数据中心能耗占全国能源耗电总量的5%,其中,服务器占数据中心耗电量的46 %.以2004年落户上海超级计算中心的每秒10万亿次曙光4000A为例,这台机器每年光电费就要400多万元,平均每天就是1万多元.能源的消耗远远大于超级计算机自身的价值.与此同时,数据显示,ICT产业存在能源浪费,其中,全世界数据中心目前的服务器能力平均利用率只有10%~30%.因此,高性能领域的绿色计算成为数据和计算中心实际运行的关键问题^[9].

另外,对高度数据密集型工作负载的支持,正成为下一代计算和数据中心的关键技术.这里,实时任务据其间的依赖性,分为独立任务或依赖任务应用;而数据密集型应用是指以数据为中心,存在海量数据传输的依赖任务应用.计算资源的异构性、调度技术的局限性和调度指标的平衡性,是面向数据密集应用调度研究所需考虑的重要因素^[10].

再者,调度算法的研究主要集中在基于需求建模的启发式算法^[11-14]和基于进化理论的元启发式算法^[15-23].

对任务的多项需求,启发式调度会将多目标聚合成单一目标函数处理.这种方法简单而有效,因此被广泛研究和采用.但其自身也存在一些固有的缺陷:由于多目标优化问题的解并非唯一,而是存在一个最优解集合,称为非劣解;而单目标优化算法仅能根据聚合函数得到决策空间的一个可行解,降低了最终解的质量,缺乏灵活性和扩展性.

更为合理的途径是采用多目标组合最优化算法来解决这个问题,基于进化理论的元启发式算法是较为有效的方法.但面对其复杂多样性,目前算法大多存在两个瓶颈:种群的收敛速度较慢或个体多样性不能保持.并行与分布式元启发式算法(parallel distributed meta-heuristics,简称PDM)因在较大目标空间的搜索高效性及鲁棒性,近年来被广泛应用,具体分为4类:主从模型、细粒度模型、粗粒度模型和混合模型.其中,粗粒度模型被广泛应用在超计算机体系结构上^[24-26].但上述PDM在面向大规模实时实例时,运行算法的超计算机虽然能达到峰值需求,很多时候却效率不高.因此,面向多核CPU+GPU混合的超计算机体系结构,元启发式算法的并行设计,也是决定问题高效求解的重要元素之一.

本文在对大规模计算系统从高性能向高效能发展的充分需求调研、分析基础上,为解决当前异构资源管理及调度存在的问题,以适应不同环境及应用的新需求和新特征,围绕节能减排和调度协同等热点,重点展开云计算中融合能效感知调度建模及相关算法等方面的研究.本文主要研究工作和创新点如下.

(1) 综合分析当前异构调度技术的发展、局限和空白;

(2) 提出融合能效感知的云调度框架和模型;

(3) 设计多学科启发的协同进化全局多目标优化算法;

(4) 实现算法评测系统和仿真方法.

1 相关工作

调度问题研究如何把任务集或一组程序在时间和空间上最优化地分配到一组处理单元,以满足一定的调度目标,一般由3个部分构成:系统模型、应用模型和调度目标^{[8, 9]}.近年来,异构调度模型除简单时限或基于成本约束以外,基于能耗约束^[11-14]引起学者广泛关注.

能耗管理技术的研究包括两个方向:基于硬件体系结构的低功耗方法^[10]和基于软件的功耗感知方法^[11-14].前者通过低功耗的组件改变嵌入式系统架构,以减少能源消耗.这种方法是有效的,但它依赖于特定元件,具有设计和更换费用昂贵等缺陷;后者对系统性能和能耗指标之间实现折衷,能以更低的成本广泛可行.而功耗感知调度,采用操作过程中能耗监管和优化调节技术(例如动态电压频率缩放(dynamic voltage and frequency scaling,简称DVFS)和动态电源管理(dynamic power management,简称DPM)),属后者^[11-14].

根据不同的调度应用,功耗感知调度一般分为独立任务和依赖任务调度.针对大规模计算,文献^[11]研究同构集群优化调度算法,以求解时间和空间不同维度下共享资源的能耗优化;文献^[12]提出云环境面向独立任务的能耗优化算法,即,基于博弈理论调节短时间作业的响应时间期望加快执行速度,其实质也是DVFS技术的使用;文献^[13]实现同构云多作业的功耗感知调度,可借助休眠工作站减少能耗,并用Pareto最优前沿来折中性能和成本指标;文献^[14]考虑的温度和热约束的面向独立任务的时限调度算法,允许云计算长时间运行作业通过在不同节点间的迁移来优化能耗值.然而,上述研究仍然有一些局限性,例如DVFS技术的不可实施性、静态能量重要性的忽略、数据密集型应用程序的不适合以及异构计算环境的不可扩展性等.

启发式算法是相对于最优化算法提出的,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计.对任务的多项QoS需求,启发式调度会将多目标聚合成单一目标函数处理.这种方法简单而有效,因此被广泛研究和采用,但其自身也存在一些固有的缺陷:由于多目标优化问题的解并非唯一,而是存在一个最优解集合,称为Pareto最优或非劣解;而单目标优化算法仅能根据聚合函数得到决策空间的一个可行解,降低了最终解的质量,缺乏灵活性和扩展性.

元启发式算法应用在异构调度问题已有十余年,包括遗传算法^[15]、模因算法^[16]、细胞模因算法^[17]以及遗传算法与其他一些技术的融合,比如变邻域搜索^[18]、神经网络^[19]和列表调度技术^[20].另外,文献^[21]提出元启发式算法求解能耗感知调度问题,文献^[22]研究了元启发式算法在多处理器优先约束的云调度问题中应用以及文献^[23]主要探讨实时云调度的元启发式算法.但面对大规模云调度实时实例的复杂多样性,上述研究算法存在两个瓶颈:种群的收敛速度较慢或个体多样性不能保持.

元启发式算法的并行与分布式设计具体可划为4类:主从模型、细粒度模型、粗粒度模型和混合模型.其中,粗粒度模型也称为孤岛模型,被广泛应用在超计算机体系结构上.该模型将种群划分成若干个子群,子群各自独立进行相关进化操作,而子群间借助迁移算子通过个体交换的方式相互影响.随着多核CPU+GPU混合结构超计算机服务器的兴起,相关的几个孤岛模型研究主要集中在选择函数、替代函数、迁移率或拓扑结构的设计上.文献^[25]面向超计算机计算平台,基于遗传算法和孤岛模型提出了新的并行进化算法pCHC,用于求解云调度问题.该算法设计了跨世代精英选择、异构重组和大变异这3个算子,针对低维调度问题表现较好,但它存在两个瓶颈:结构化方案的搜索能力有限以及个体多样性保持不够.文献^[26]在上述工作的基础上提出了Pm-CHC;即,在子群们并行进行相关进化操作的同时引入一个局部随机搜索策略.研究应用在经典问题实例和一些新的云调度实例上,效果较好.但上述研究在面向大规模实时实例进行云调度求解时,运行算法的超计算机虽然能处理高峰需求,很多时候却效率不高.

2 数学建模

能效感知云调度模型可以设计成一个中间件,然后插入到云资源系统中,从而使云任务能够有效分配到目标性能达到最优的节点上执行.这样一方面有效降低了云任务调度长度,另一方面,尽可能地提高了任务执行的完全性和可靠性,较好地满足了云应用的服务质量需求.云资源任务调度的体系架构如图 1所示.

云资源任务调度体系架构的最底层为云资源层(包括节点局部调度器),第2层为云中间件层,第3层为任务全局调度器层,最上一层为云应用任务客户端.

在多目标优化云资源的任务调度框架下,云用户提交一个任务并被执行的具体过程如下:

1) 应用客户端将云应用提交到任务队列进行排队;

2) 任务调度器(全局)从任务队列中取出一个云应用中所有具有依赖关系的子任务,同时与调度顾问进行交互;

3) 调度顾问与云监视器及能效融合模型交互;

4) 云监视器将网络目前链路状态和可用资源信息反馈给调度顾问;

5) 模型通过分析云监视器反馈的可用资源信息,对资源节点的调度成功率及利用率进行分析获得行为能效性;同时,根据资源节点加密水平等获得固有安全性,然后将云资源的能效收益等信息反馈给调度顾问;

6) 调度顾问将云监视器和模型反馈的信息传递给任务全局调度器,通过云中间件将所有子任务分配到较优资源节点集执行;

7) 局部调度器对其控制范围内云资源节点上任务进行最优调度.

实时应用任务是由用户上传的若干子任务a={a_i}(i=1,2,…,m)组成,具体可由一组属性集合表述:a_i=(b_i,w_i,t_i,ν_i,V,l_i,S_i).其中,b_i,w_i及t_i表示子任务的到达、估计执行和结束时间;ν_i表任务截止时间;V_i表计算量(周期数目);l_i表示需保护的数据量(单位:KB);S_i→k(k是一个正实数集)表示实时任务对云资源节点的安全需求集合,这里通常是指保密、诚信和认证这3种.

云资源节点集合可表述为j={j_j}(j=1,2,…,n).其中,每个节点j_j有不同的属性值,见表 1.表 1中第1列表示属性变量名称,第2列显示该参数是否是输入参数,第3列说明了参数的数据类型,最后一列详细表述了变量的代表意义.

通常,云调度模型中的主机CPU可拥有不同工作频率.对于指定频率F_i,能耗模型定义为

$P\left( {{F}_{i}} \right)=a({{P}_{f}}\left( {{F}_{i}} \right)-{{P}_{d}}\left( {{F}_{i}} \right))+{{P}_{d}}\left( {{F}_{i}} \right)$

(1)

其中,a表示CPU负载,P_f(F_i)和P_d(F_i)表示集群中所有主机单位时间内100%CPU和0%CPU分别采用频率F_i的功耗.由于集群中每台主机的能耗总量与其总体运行时间($\Delta {{T}_{{{h}_{i}}}}$)成正比,因此能耗公式定义为

$\mathop{P}_{(F)}=\sum\nolimits_{i=1}^{{{n}_{H}}}{P{{({{F}_{i}})}^{{{h}_{i}}}}}\times \Delta {{T}_{{{h}_{i}}}}$

(2)

执行时间取决于要执行的需求任务复杂度.令虚拟机ν待执行指令数目k^v,需求任务执行时虚拟机ν的执行

力为$\omega _{*,*}^{v,h}$,则执行时间定义为

$T=\max ({{\kappa }^{v}}/\omega _{f,cpu}^{v,h})$

(3)

鲁棒性可解释为一台主机发生故障所导致的失联虚拟机数目,即,每台运行主机的虚拟机平均数目,具体定义为

$R={\sum\nolimits_{i=0}^{{{n}_{H}}}{n_{V}^{{{h}_{i}}}}}/{{{n}_{H}}}\;$

(4)

计算动力(或潜力)记作D,代表现运行所有主机可继续利用的计算能力,其可引导云计算提供商在计算峰值来临之前暂不新增虚拟机数目.如果主机可具动态电压频率缩放,计算动力依据所有主机CPU的最大计算能力和当前计算力可定义为

$D={\left( \sum\nolimits_{i=0}^{{{n}_{H}}}{\xi _{f,cpu}^{{{h}_{i}},k}-\omega _{f,cpu}^{{{h}_{i}},k}} \right)}/{{{n}_{H}}}\;$

(5)

其中,f是CPU的最高频率,n_H表正在运行的主机数目.

融合能效感知的云调度目标就是:在满足任务间依赖关系同时,寻找任务需求模型与资源拓扑结构之间的映射调度方案{(a_i,j_j)},i∈[1,m],j∈[1,n],使云计算任务的调度长度和系统节点能效收益达到最优,求尽可能多的(甚是是全部)的非劣解,可以描述为

$MinY=F\left( X \right)=\left( {{f}_{1}}\left( X \right),{{f}_{2}}\left( X \right),\ldots ,{{f}_{\kappa }}\left( X \right) \right)=\{{{P}_{(F)}},T,R,1/D\}$

(6)

其中,X∈Φ,Y∈W.X称为决策变量,Φ是决策空间;Y为目标函数值,W是目标函数空间.

3 多学科启发的协同进化多目标优化算法

在免疫学中,抗原是导致免疫系统产生抗体的物质.对于多目标优化问题,抗原被定义为目标函数(见公式(6)).

B细胞、T细胞及一些具抗原特异性的淋巴细胞通常称为抗体.人工免疫系统中抗体代表抗原的一个候选解.令X为抗体空间,抗体种群表示为N-维抗体集合(N是抗体种群规模);且抗体由基因组成,表示为x_i=(G₁,G₂,…,G_N).在实际应用中,给定优化问题具有N-维实数的目标搜索空间,一个候选解x_i(i∈[1,N])由N维实数组成,而每一维代表一个问题变量并被看作基因.这里,基因的基本单位是基因座.

认知心理学认为,模因是文化信息单位,是文化复制、传播和发展的基因.模因作为一种选择与建构的创新思维和科学方法,是社会进化原动力的一个表现形式.给定一个抗体A_β(A_β∈X),本文将抗体基因的实时进化信息看作模因,并形式化为M.矩阵中每一维数据都与相应的基因进化信息对应,Z,N表示模因空间的维数.

本文提出多学科启发的基因-模因协同进化调度算法(MCMC),即:首先,基于调度实际问题的离散空间特征进行抗体编码与解码;然后设计克隆、交叉、变异和选择等算子.算法框架如图 2所示.MCMC较人工免疫算法有4个方面改进:抗体基因亲和度值的细粒度评估、模因的数学表述、基因-模因协同进化过程的高效模拟以及结合孤岛模型和主从模型的多层次并行化设计.

3.1 基因-模因协同进化模拟

克隆算子在算法中对解的多样性分布和逼近性起着重要的作用,通常,其对抗体种群δ={δ₁,δ₂,…,δ_e,…,δ_q}的操作G_C可以定义为式(7).

$\begin{align} & {{\delta }^{*}}(\iota )={{\Gamma }_{C}}\{{{\delta }_{1}}(\iota ),{{\delta }_{2}}(\iota ),...,{{\delta }_{\varepsilon }}(\iota ),...,{{\delta }_{\theta (\iota )}}(\iota )\} \\ & \text{ }={{\Gamma }_{C}}({{\delta }_{1}}(\iota ))+{{\Gamma }_{C}}({{\delta }_{2}}(\iota ))+...+{{\Gamma }_{C}}({{\delta }_{\varepsilon }}(\iota ))+...+{{\Gamma }_{C}}({{\delta }_{\theta (\iota )}}(\iota )) \\ & \text{ }=\{\delta _{1}^{1}(\iota ),\delta _{1}^{2}(\iota ),...,\delta _{1}^{\varepsilon }(\iota ),...,\delta _{1}^{\backepsilon 1}(\iota )\}+...+\{\delta _{\theta (\iota )}^{1}(\iota ),\delta _{\theta (\iota )}^{2}(\iota ),...,\delta _{\theta (\iota )}^{\varepsilon }(\iota ),...,\delta _{\theta (\iota )}^{\backepsilon \theta (\iota )}(\iota )\} \\ \end{align}$

(7)

这里,${{\Gamma }_{C}}({{\delta }_{i}}(\iota ))=\{\delta _{i}^{1}(\iota ),\delta _{i}^{2}(\iota ),...,\delta _{i}^{\varepsilon }(\iota ),...,\delta _{i}^{\backepsilon i}(\iota )\}$,i=1,2,…,θ(i);∋i∈[1,m_c]是可调节参数,表示克隆概率;m_c是克隆概率上限;a'i=1代表不对d_i(i)进行克隆操作.由于多目标优化问题通常有非劣解集,因此通常对每个抗体d_i(i)的克隆概率上限都可设定为m_c.

在MCMC算法中,对每个抗体采用一致的克隆概率∋,使得优化过程中的可行非支配解集规模几乎成倍上升,保持个体多样性同时还可加速群体收敛.具体如式(8)所示.

${{\delta }^{*}}(\iota )=\{\delta _{1}^{1}(\iota ),\delta _{1}^{2}(\iota ),...,\delta _{1}^{\backepsilon }(\iota )\}+...+\{\delta _{\theta (\iota )}^{1}(\iota ),\delta _{\theta (\iota )}^{2}(\iota ),...,\delta _{\theta (\iota )}^{\backepsilon }(\iota )\}$

(8)

与此同时,在同一抗体的大量克隆个体上采用不同的基因交叉、变异策略,可有助于抗体间的协同和信息交换.这里,对抗体种群的基因操作Γ_G可定义为式(9).

$\begin{align} & {{\delta }^{**}}(\iota )={{\Gamma }_{G}}({{\delta }^{*}}(\iota )) \\ & \text{ }={{\Gamma }_{G}}(\{\delta _{1}^{1}(\iota ),\delta _{1}^{2}(\iota ),...,\delta _{1}^{\backepsilon }(\iota )\}+...+\{\delta _{\theta (\iota )}^{1}(\iota ),\delta _{\theta (\iota )}^{2}(\iota ),...,\delta _{\theta (\iota )}^{\backepsilon }(\iota )\}) \\ & \text{ }=\{{{\Gamma }_{G}}(\delta _{1}^{1}(\iota ))+{{\Gamma }_{G}}(\delta _{1}^{2}(\iota ))+...+{{\Gamma }_{G}}(\delta _{1}^{\backepsilon }(\iota ))\}+...+\{{{\Gamma }_{G}}(\delta _{\theta (\iota )}^{1}(\iota ))+{{\Gamma }_{G}}(\delta _{\theta (\iota )}^{2}(\iota ))+...+{{\Gamma }_{G}}(\delta _{\theta (\iota )}^{\backepsilon }(\iota ))\} \\ & \text{ }=\{\delta _{1}^{1\#}(\iota ),\delta _{1}^{2\#}(\iota ),...,\delta _{1}^{\backepsilon \#}(\iota )\}+...+\{\delta _{\theta (\iota )}^{1\#}(\iota ),\delta _{\theta (\iota )}^{2\#}(\iota ),...,\delta _{\theta (\iota )}^{\backepsilon \#}(\iota )\} \\ \end{align}$

(9)

其中,(i=1,2,…,θ(i),j=1,2,…,∋)表示抗体$\delta _{i}^{j}(\iota )$以概率P_m进行的基因操作(包括交叉和变异).通常,工免疫系统模拟二进交叉算子或多项式变异算子.在MCMC算法中,交叉点或变异点的选取依据模因信息矩阵.

与克隆相反,选择操作将种群个体划分为非劣解或劣解,且只有非劣解可进入下一代.对于任何抗体δ^#(i)∈δ^**(i),如果δ^#(i)满足公式(10),为非劣解,否则是劣解;而对抗体种群的选择操作Γ_S,定义为式(11).

$\neg \exists \delta _{\kappa }^{\varpi \#}(\iota )\ne {{\delta }^{\#}}(\iota )(\kappa =1,2,...,\theta ;\varpi =1,2,...,\backepsilon )\in {{\delta }^{**}}(\iota ):(\forall i\in \{1,...,m\}:\mathop{f}_{i}({{\delta }^{\#}}(\iota ))\ge \mathop{f}_{i}(\delta _{\kappa }^{\varpi \#}(\iota )))$

(10)

$\begin{align} & {{\delta }^{***}}(\iota )={{\Gamma }_{S}}({{\delta }^{**}}(\iota )) \\ & \text{ }={{\Gamma }_{S}}(\{\delta _{1}^{1\#}(\iota ),\delta _{1}^{2\#}(\iota ),...,\delta _{1}^{\backepsilon \#}(\iota )\}+...+\{\delta _{\theta (\iota )}^{1\#}(\iota ),\delta _{\theta (\iota )}^{2\#}(\iota ),...,\delta _{\theta (\iota )}^{\backepsilon \#}(\iota )\}) \\ & \text{ }={{\Gamma }_{S}}(\{\delta _{1}^{1\#}(\iota ),\delta _{1}^{2\#}(\iota ),...,\delta _{1}^{\backepsilon \#}(\iota ),...,\delta _{\theta (\iota )}^{1\#}(\iota ),\delta _{\theta (\iota )}^{2\#}(\iota ),...,\delta _{\theta (\iota )}^{\backepsilon \#}(\iota )\}) \\ & \text{ }=\{\delta _{1}^{\#}(\iota ),\delta _{2}^{\#}(\iota ),...,\delta _{\varepsilon }^{\#}(\iota ),...,\delta _{\theta s(\iota )}^{\#}(\iota )\} \\ \end{align}$

(11)

其中,(e=1,…,qs(i))表抗体群δ^**(i)中的非劣个体,qs(i)是非劣个体的数目.通常,人工免疫系统根据当代每

个个体的约束偏离值选取可行解集,然后,据每个个体的目标函数值选取可行非劣解集进行个体选择;而MCMC依据模因信息矩阵直接在种群中选取非劣抗体,有利于简化算法.

3.2 算法描述

MCMC算法.

1: Initialize the iteration (i) and the subpopulations {δ₁(i),δ₂(i),…,δ_e(i),…,δ_q(i)(i)},each of s individuals;

2: While (i<i_max) and (other termination criteria are not satisfied)

3: Do in parallel for each island /*Obtain the coarse-grained model (also named as island model),one of the parallel and distributed models*/

4: i=i+1;

5: Do in parallel /*Obtain the master-slave model*/

6: Evaluate the affinity between the antibody and antigens (Eq.(6)) in the current population:Φ(A_β)(A_β∈X);

7: For (every couple of antibodies denoted as A_U and A_W)

8: If (Φ(A_U)>Φ(A_W)

9: For (C=1; C<=N; C++)

10: For (K=1; K<=Z; K++)

11: If (${{{A}'}_{U}}$G_KC}<>${{{A}'}_{W}}$G_KC)

12: Update ${{{A}'}_{U}}$ meme vectors:

13: {M_KC(t)=(1-r)xM_KC(t-1)+ΔM_KC;

14: ΔM_KC=Q(t)/Φ(A_U);}

15: Update ${{{A}'}_{U}}$ other meme vectors M_JC(J<>K):M_JC(t)=(1-r)xM_JC(t-1);

16: EndIf

17: EndFor

18: EndFor

19: EndIf

20: EndFor

21: End Do in parallel

22: Perform clonal operation δ(i)=Γ_C{δ₁(i),δ₂(i),…,δ_e(i),…,δ_q(i)(i)};

23: Perform gene operations based on meme matrices δ^**(i)=Γ_G(δ(i));

24: Perform clonal selection operation δ^***(i)=Γ_S(δ^**(i));

25: Save the best solution in the generation;

26: If i=t (migration interval) then

27: Create ψ_δ for the current subpopulation;

28: Send ψ_δ to the neighboring subpopulation;

29: Receive ψ_δ from the neighboring subpopulation;

30: Construct the founding subpopulation σ_δ;

31: Select s individuals in σ_δ;

32: Replace the subpopulation ψ_δ with $\Psi _{\delta }^{\tau }$;

33: End If

34: End Do in parallel

35: End While

36: Output the best individual.

算法MCMC的第7步~第20步细粒度评估抗体基因的亲和度值,并有效模拟种群自组织的模因更新;而第22步~第24步定义了模因传播并影响基因进化的过程.

面向新近发展的混合多核CPU+GPU的高性能计算机集群体系结构,本文提出融合粗粒度模型和主从模型的层次并行模型.即:首先依据粗粒度模型将种群划分成若干子群,并把每个子群分配到一个节点上;而在每一个节点上,大量的个体适应度评估计算是适于GPU加速的主从式并行应用.这里,CPU可看作主服务器,而在GPU多核上执行的若干线程就是客户端.第26步~第33步具体描述了多层次模型之一的粗粒度模型(也称为孤岛模型)采用的基于模因库的并行迁移策略.

3.3 算法的复杂度分析

设在每一代进化中,种群FeaNonPop和ModNonPop的规模都为θ,克隆倍数为∋,变量的维数为£,约束维数为h,目标函数维数为m,则:

· 在每次克隆种群ModNonPop所用的复杂度为O(∋θ);

· 交叉操作所需复杂度为O(£∋θ/2);

· 变异操作所需复杂度为O(£∋θ);

· 计算种群Pop基因亲和度值的时间复杂度为O(£∋θ);

· 合并种群ModNonPop所需复杂度为O(£θ+hθ+mθ);

· 修正种群Pop中个体模因值所需复杂度为O(3m(∋+1)θ+2h(∋+1)θ);

· 选取并更新可行非支配解集所需复杂度为O((2∋+6+m∋+2m)θ+m(∋+2)²θ²+(∋+2)(m+1)θlog₂((∋+2)θ));

· 选取并更新非支配解集所需复杂度为O((m+1)(∋+1)θ+θ+m(∋+1)²θ²+(m+1)(∋+1)θlog₂((∋+1)θ)).

4 仿真实验及结果

实验在山东省高性能计算中心进行,采用浪潮天梭TS10000高性能集群系统,英特尔至强5600系列处理器(2.66GHz,12MB Cache),CPU+GPU混合结构,共有960个计算核数,计算峰值达每秒10万亿次双精度浮点运算,内连40Gb/s带宽1ms~2ms超低延迟的高速网络.算法的并行实现采用C-CUDA编程语言和MPICH-VMI(MPICH 1.2.7p1版本)^[27].表 2总结了实验集群的相关参数设置.

4.1 整体性能比较

文献^[25]提出了一些新的模拟中型规模云调度实例集,并可以通过网站http://www.fing.edu.uy/inco/grupos/ cecal/hpc/HCSP下载应用.这些测试集是依据文献^[28]所述的建模方法随机产生的,其目的是模拟复杂的异构计算环境.实例维数(任务x机器)包括1024x32,2048x64,4096x128及8192x256,规模远大于文献^[6]的经典的12个实例.

首先,针对高维异构依赖任务云调度问题,MCMC按实例的一致性、半一致性及不一致性分类与算法Min- Min^[11]和Sufferage^[11]进行性能比较.这里,一致性、半一致性及不一致性的定义依从文献^[25].

Min-Min和Sufferage是能在合理时间内求解低维异构调度问题的两种较好启发式算法.从图 3看:对于每维的一致性实例,算法MCMC相较Min-Min和Sufferage的时间性能改善约为9%;而对半一致性实例,时间性能改善上升为16%.另外,虽然对于低维的不一致性实例,MCMC相较Min-Min和Sufferage的时间性能改善不明显,但面向高维的不一致性实例,其时间性能改善超过15%.

然后,针对上述同样实例,MCMC与目前面向计算机集群体系结构设计的较好的3种元启发式算法(IM- dDE-CUDA^[24],pCHC^[25]和Pm-CHC^[26])进行性能比较.如图 4所示:随着云调度问题的规模增大,MCMC表现的性能改善越大.值得注意的是:对于高维实例4096x128,MCMC相较Pm-CHC,pCHC和IM-dDE-CUDA的性能改善分别达到8%,12%和14%.

4.2 融合能效感知模型的影响

数据中心内共有N=200台服务器,通常,每台服务器都有淘汰周期(一般为3年).可以假定服务器的最优值取决于机器的使用时长.简单起见,我们假设1/3的服务器的最优点为(0.8,0.9),即:其CPU和硬盘利用率分别为80%和90%时,其能源利用率最高.其他1/3的服务器的最优点为(0.65,0.7),剩余1/3的服务最优点为(0.5,0.5).

服务器的初始硬盘利用率是[0,0.3]范围内的随机数,初始CPU利用率为[0,0.35]范围内的随机数.为了更好地体现算法的有效性,我们设置了一组特殊的服务器,它们的CPU利用率分别如下:CS[5]=0.5,CS[25]=0.7, CS[45]=0.9,CS[75]=0.5,CS[95]=0.7,CS[115]=0.9,CS[145]=0.5,CS[165]=0.7,CS[195]=0.9;同样地,我们设置了另一组特殊的服务器,它们的硬盘利用率分别如下:HS[10]=0.5,HS[30]=0.65,HS[50]=0.8,HS[80]=0.5,HS[100]=0.65, HS[120]=0.8,HS[150]=0.5,HS[170]=0.65,HS[190]=0.8.我们将本文提出的算法MCMC与Pm-CHC调度算法进行了3组对比实验,每组实验每个算法独立运行30次,以获取并记录实验结果.

· 首先,本文提出的算法比Pm-CHC在提高服务器的能源利用率方面更加有效,因为本节提出的算法,其能源无效值低至0.496 3,而Pm-CHC获得的能源无效值高达13.638 3;

· 其次,MCMC算法可以达到任务10%数据本地化执行率,而Pm-CHC则不能.

· 再次,将服务器划分为3组,3组服务器的最优CPU利用率分别是0.9,0.7和0.5,最优硬盘利用率分别是0.8,0.65和0.5.实验数据表明,明显优于Pm-CHC.MCMC调度后,3组服务器的CPU利用率分别位于0.9,0.7和0.5左右,都接近于其最优值;同时,硬盘利用率分别位于0.8,0.65和0.5左右,也都接近其最优值.这是因为针对适量负载,Pm-CHC并没有考虑服务器的资源利用率:它为每台服务器只是按照负载均衡的方式分配数据和任务.

4.3 可扩展性

实验首先依从文献^[25],将调度算法运行的总体时间阈值定为90s;然后,针对每维的一致性、半一致性和不一致性实例,采用不同的子群个数(^{[2, 16]})进行实验,直到调度算法运行到时间阈值.这里,任务调度时间的标准化是采用n个子群实现时间与一个子群实现时间的比率.图 5显示出相关实验结果.

图 5表明:随着云调度问题维数的增加,算法MCMC求得的任务调度时间明显下降,时间性能优势明显.这主要是因为MCMC包含种群和智能的双重协同进化过程,可实现种群加速收敛及个体多样性保持.

5 结 论

本文对融合能效感知的云调度进行研究,有效降低数据密集应用的通信开销、兼顾提供者和消费者双方的利益,并保证系统双层负载均衡性.随着新应用(数据密集应用、计算密集应用)、新环境(计算网格、云计算)和新性能指标(能效)的出现,分布式计算资源管理核心技术之异构调度研究具有重大的理论和应用价值.