作为多种技术混合演进发展的云计算,如今已能够给用户提供更加可靠、一致、无处不在并廉价访问高端计算资源的能力,也能支持各种类型的科学应用数据流.为了规划大规模的基础设施,比如混合云,作为传统软件组件的松耦合协调模型的数据流^[1]已经出现,并作为科学界最成功的编程范式之一.

研究人员试图解决的最具挑战性的NP完全问题之一^[2]就是怎样将大规模的科学应用以任务数据流形式调度至分布式和异构资源云环境中,并针对某些目标函数进行优化,比如总执行时间或者在商业及市场化中的经济成本,考虑和实现某些执行约束比如通信成本和存储需求.从最终用户角度来看,最小化成本或者执行时间应当是被优先考虑的功能,然而从云系统的角度看,系统级别的效率和公平则是优先考虑的优化动机,这样有更多计算量的应用能够被分配到更多的资源.目前,仅有少数方案可以同时处理以上这两种角度,比如优化用户目标(完工时间、经济成本)的同时满足其他约束,并且能够给所有用户提供良好的效率和公平.另一方面,在数据流调度中,考虑合适的调度带宽和存储约束已经是亟待处理的问题,因为在大数据环境下,许多应用能够在相对短的时间产生大量的数据集,比如大型强子对撞机^[3],预计每年能够产生约7PB的数据.

因为在云中会有许多不同类型的应用或者任务,其对可用资源的使用互为竞争.那么一些问题出现了,比如针对不同应用的有效资源配置,考虑它们各自的性能、成本、带宽、存储和其他潜在的约束条件,并从系统角度来考虑资源的最大公平使用.对于公共云,谷歌2012年推出了谷歌计算引擎云(GCE),其提供托管的Linux虚拟机.谷歌为开发者开放其基础设施并且成为了亚马逊弹性计算云(EC2) 的一个强有力的竞争对手.表 1显示了亚马逊和谷歌不同云服务的带宽,可以看到:谷歌云存储(GCS)比亚马逊简单存储服务(S3) 速度慢,GCS比EC2的传输速度慢.有趣的发现是,从S3到GCS的传输速度大约是GCS到GCE的2.2倍.因此,预计随着更多的云服务被使用,多目标云优化将会成为一项越来越复杂和有前景的事业.

本文针对云环境中的数据流应用提出了通信和存储约束的多目标调度计划,其特征为大量独立和同质的任务包,通过数据流依赖互联.

1) 多目标调度基于一个连续的合作博弈算法,最小化云应用的期望执行时间和经济成本;

2) 调度算法能够快速收敛,算法执行时间能比相关算法有明显提升;

3) 在传输产生数据时,该调度方法能够考虑它们的带宽和存储约束,同时最小化应用的完工时间和成本,并保证系统资源的最大公平使用.

本文提出的MOG调度算法的主要优势是使用竞争者和环境信息来快速收敛,并通过创建合理运动来最小化有关问题定制的需求等决定最有效的搜索方向.本文将MOG方法和5个相关启发式方法进行了性能比较,结果表明:针对大量任务包的云数据流应用,MOG算法在复杂度(改进数量级)、结果质量(一些情况下最佳)、系统级别公平性上具有优越性.MOG算法可能不适合于在任务包间具有复杂依赖关系的应用(比如水文invmod、气象MeteoAG或者生物信息测试^[4]等任务流),因为这些调度问题不能够被正确配置成为典型的可解博弈.

本文首先介绍相关工作.抽象数据流模型在第2节中描述.第3节具体阐述本文设计的MOG多目标调度算法.第4节中进行具体的实验验证算法的效率和有效性.最后,第5节总结并讨论未来工作.

1 相关工作

调度大型数据流应用是云计算中重要且困难的研究课题之一,其发展了很多不同的方法和算法.本节总结了相关领域的重要工作:启发式调度、博弈调度和多目标调度.

1.1 启发式调度

启发式方法通常属于那种没有详尽地搜索整个解空间的方法,该方法依赖于一个特定问题域的信息学习.每一个基于启发式的方法一般被设计用来仅适合一个特定类型的问题.所有方法都采用一组特定的应用规则来增加得到一个较好解的概率.算法通常能花费较少的时间得到一个较优的解.在任务调度问题领域,一般的基于启发式的方法可以被划分为3个类别:独立任务调度、列表调度以及基于集群和复制的调度.

最简单的就是独立任务调度,但是它仅仅适合有简单结构的任务流,比如管道类型.它不断地将每个独立就绪任务映射至能够提供其最早完成时间的资源,而不考虑其他任务和它们之间的依赖关系.列表调度算法特别适合有很多任务竞争有限数量资源的工作流.它给每个任务分配一个优先级,然后基于分配的优先级创建一个调度.目前有两种模式的列表调度:批处理模式^[5]和依赖模式^[6].批处理模式基于任务的执行时间设置其优先级,依赖模式基于关键路径的权重设置优先级.使用列表调度算法的好处是总的执行时间通常是最小化的.然而,该算法不能够处理资源优化问题,其中的任务流包含很多相等关键路径长度的并行任务.另一个缺点是需要反复地计算优先级,尤其在调度大规模任务流时会显著增加计算时间.

基于集群和复制的调度算法^[7]聚焦于最小化完工时间.该算法试图通过将通信密集型任务集中映射至相同资源来减少依赖任务之间的通信时间.一些任务也被复制以避免资源之间的数据传输.

尽管上述调度方法都是有效的,但是它们仅仅满足单一的调度目标.例如,它们能够给出一个调度,提供最小的完工时间,但是执行的成本很高.为了修改算法处理多目标问题,计算调度计划所需的时间会大幅度地增加.此外,基于这些启发式方法设计针对多种数据流类型的调度框架是困难的.

1.2 博弈调度

就博弈算法而言,一些注重性能的分布式计算领域的研究人员聚焦在系统级的负载均衡上^[8],或者资源分配^[9],目标在于引入经济和博弈论方法至计算问题中.Siar^[8]制订了调度问题作为合作博弈,这里,网格试图最小化任务的期望响应时间.Srinivasa等人^[9]通过考虑不合作机器因素,调查了单个机器自私行为的影响,Ghosh等人^[10]提出了一种策略,制订一种不完全信息,在两个变量上进行交流议价博弈:每资源单元价格和分配带宽百分比.与其工作相比,本文采用了更加实际的定价模型,类似于云资源提供商亚马逊弹性计算云所采用的计价模式.ICENI项目^[11]使用了博弈论算法解决调度问题,采用严格淘汰的支配策略.这里,末位最优解不断被丢弃.由于高时间复杂度,该算法的可行性是存疑的.除了博弈论算法,ICENI采用了随机、N-随机最佳和模拟退火方法提供了调度方案.

1.3 多目标优化调度

许多真实世界的调度问题是多目标性质,比较常见的是,这些问题中有多个目标同时存在,比如最小化调度时间、最小化经济成本、满足存储限制和网络资源等.这些年来,有一些方法先后被用来处理这些多目标问题.

传统上,最普遍的方法是解析并结合多重目标至单一的总和目标函数,并给不同的目标分配权重^[12].然而,在很多涉及多目标调度的真实场景下,最好是展示各种折衷方案给用户,以使得最合适的调度被选择.此外,聚合目标函数在目标中通常是非线性的,并且获得的解决方案将取决于指定权重的相关值.由于加权法需要用户喜好的先验信息,因此其本质是主观的.那么,如何寻找一组折衷方案来表现良好的近似帕累托最优前沿,则成为了探索帕累托优化方法的新课题.比如,Fard等人^[12]提出了基于帕累托支配约束向量的方法,并应用至4个目标中,作为目标函数的部分(完工时间、成本、能耗和可靠性),本文的方法与之相比有着更低的时间复杂度,并考虑进两个不同的目标(完工时间和成本)和两种约束(带宽和存储资源).

许多元启发式方法原本被用来解决单目标优化问题,现在被推广到生成多目标优化变型.其中,多目标进化算法已经得到了特别的关注,因为一些研究人员认为这些方法特别适合于处理多目标优化问题.此外,一些多目标的元启发式方法比如模拟退火^[13]、遗传算法^[14]、禁忌搜索和粒子群优化(PSO)^[15]被提出来解决调度问题.我们在此方向也做了一些努力,试着解决更小更简易的问题版本^[14].Buyya等人^[16]介绍了新的遗传算法以解决在大规模异构环境中现有遗传算法无法直接应用的情况,由于它们的高时间复杂度,遗传算法在大规模应用中不实际.Arabnejad等人^[17]以经济成本作为数据来计算调度中的部分目标函数,但是其没有考虑存储约束,也不能全局解决性能和成本优化问题.Pandey等人^[15]提出了PSO启发式方法来调度应用至云资源中,并考虑进了计算成本和传输成本.蚁群优化(ACO)^[18]和人工蜂群(ABC)^[19]方法基于蚂蚁和蜜蜂觅食的行为,在代理的子群内做出集体决策,其在搜索过程中可能陷入局部最优解而不一定得到全局最优解.进化算法和以上算法的主要缺点是收敛速度慢而导致的高计算成本^{[20, 21]}.本文提出的MOG方法与此相反,由于全局资源信息的有效利用,而有着更快的收敛速率.

本文介绍的方法成功应用了博弈论概念,能调度多个大规模应用至云环境中.本文建模了一种现实可行的云系统模型,其特征为大量均匀独立的任务通过简单数据流依赖互联,并将调度问题制订为一种多个应用管理者之间的连续合作的博弈,设计快速收敛的高效MOG多目标调度算法,优化完工时间和经济成本,在满足通信和存储约束的同时,保证了系统资源的公平度.

2 数据流模型

本节描述文中使用的抽象数据流模型,设计原则来自于现实世界的应用和真实的云计算平台.本文研究的大规模数据流,以大量(数千到数百万)同质并行且独立的任务为特征.这些任务决定性能,并通过控制和数据流之间的依赖而互连.

定义1. 采用w=(BS,DD)定义一种数据流应用,并建模为DAG.这里,$BS=\bigcup\nolimits_{k=1}^{K}{{{T}_{k}}}$是K个异构任务包的集合,DD=(T_s＜T_d|{T_s,T_d}⊂BS)是数据流的依赖集.这里称T_s为T_d的前继,并且写做T_s=pred(T_d).任务包T_k定义为${{T}_{k}}=\bigcup\nolimits_{j=1}^{{{K}_{k}}}{{{t}_{kj}}},k\in [1,2,...,K]$,且作为一组同质的并行原子序列任务,它们有着相同任务类型并且可以同时执行,这里的K_k是任务包的基数.

大规模应用中的数据流类型一般有4种:Montage(如图 1(a)所示)^[22],Ligo(如图 1(b)所示)^[23],Cybershake(如图 1(c)所示)^[24]和Lattice(如图 2所示).前3个是在实际应用中所使用的真实数据流的抽象:Montage被NASA用来产生自定义天空马赛克,Ligo被激光干涉引力波观测站用来分析星系的双星系统,Cybershake被南加州地震中心用来描述地震.

通过观察负载的时间特性,可以识别出并行阶段的高低.并行性降低的情况有两种:(1) 当操作从大量的其他操作收集或者分发数据时;(2) 有大量增加的数据将要被转移时.Montage任务流出现一个并行量最高的阶段,同时它也有一些瓶颈操作.Ligo具有并行性更加均匀分布的阶段以及适中的瓶颈操作数量.Cybershake有两个高并行阶段并仅有4个瓶颈操作,同时,它传输了大量数据.而Lattice被设计为可以自定义并行度和瓶颈数. Lattice是一个纯粹的数据流合成系列并被设计成为云环境中典型的Mapreduce模型的数据流(如图 2所示).特定的Lattice流有一个确定的高(H)和分支因子(B)并被定义为(H-B)Lattice.例如,图 2(b)中表示(5-2) Lattice.

在这些数据流类型中,性能瓶颈的来源都是同质的大规模任务包,连续任务在大规模的应用中相对琐碎,并可以按需调度至最快或者最便宜的可用处理器上.因此,这给优化提供了方向,也带来了空间.

3 多目标博弈调度方法

本文的目标是设计一种新算法来调度一组定义1中表示的应用以及在第2节中定义的环境模型中调度大量的任务,表 2描述了本文使用的关键符号列表.本文算法的目标是优化两个目标函数:累计完工时间和经济成本,同时还能够满足带宽和存储约束.

3.1 问题定义

定义2. 假定有一系列的N个工作流应用(如定义1中建模并且忽略他们的到达时间),其由K个子任务包组成,运行在M个站点的云环境中.在应用A_i,i∈[1,n]中,完工时间由其中任务包的最大完成时间决定.因此,多目标调度问题的目标是寻找一种解决方案,能够分配所有的任务至站点,使得所有应用的完工时间和经济成本的F(x)最小,并且满足带宽和存储需求,公式表达如下 :

$\begin{align} & \text{Minimize}F(x)\text{=}(f(x),c(x)\text{)};并且有 \\ & hi(x)\le {{\lambda }_{x,i}},i=\left[ 1,M \right],{{g}_{i}}\left( x \right)\le s{{l}_{i}},i\in \left[ 1,M \right],x\in S \\ \end{align}$

(1)

这里,x作为一个解,S作为一套可行的解决方法,F(x)是解x在多目标空间中的像,f(x)是性能目标,c(x)是经济成本目标,g(x)是存储函数,h(x)是带宽函数,λ_x,i是云站点S_i的输入数据带宽,sl_i是云站点S_i的存储限制.

预期计算时间矩阵(ETC)最初由Braun等人^[25]提出并应用于分布式环境中的调度问题,随后,大量研究采用ETC矩阵这一概念并应用在云环境中的任务、资源等调度问题中^{[26, 27]},其表示每个云站点S_i,i∈[1,M]的每个任务包k∈[1,K]中子任务包的预期执行时间p_ki.通信开销是异构云环境中的关键问题,在很多情况下是最为重要的因素.对于大规模且有大量任务的云应用,通信和计算可以同时运行和叠加,造成了运行时间可以由通信或者计算决定.因此,基于计算时间pc_ki和通信时间po_ki,可以定义预期执行时间p_ki.它们之间的关系如下所示:

${{p}_{ki}}=\left\{ \begin{array}{*{35}{l}} p{{c}_{ki}},\text{ }p{{c}_{ki}}\ge p{{o}_{ki}} \\ p{{c}_{ki}}+(p{{o}_{ki}}-p{{c}_{ki}})=p{{o}_{ki}},\text{ }p{{c}_{ki}}＜p{{o}_{ki}} \\ \end{array} \right.$

(2)

其中,通信时间po_ki表示如下:

$p{{o}_{ki}}=\frac{{{d}_{ki}}}{{{b}_{ki}}}.$

d_ki表示任务的数据大小,b_ki表示云站点S_i中分配给任务包K的带宽.那么,云站点的输入数据带宽S_i(λ_x,i)可以表示为云站点S_i中的所有b_ki之和,公式表示如下:

${{\lambda }_{x,i}}=\sum\limits_{k=1}^{K}{{{\theta }_{ki}}\cdot {{b}_{ki}}}=\sum\limits_{k=1}^{K}{\frac{{{\theta }_{ki}}\cdot {{d}_{ki}}}{p{{o}_{ki}}}}$

(3)

公式(3) 中的θ_ki表示云站点S_i中分配给任务包T_k的处理器数量.θ_ki是实数,任务对少量的资源进行请求,使得我们更加精细地调整资源的分配.在调度的最后,对θ_ki取整.基于以上的分析,能够发现针对数据密集型应用,预期执行时间p_ki由计算时间和通信时间决定.通信时间是由分配到每个任务包的带宽决定.

3.2 调度系统架构

多目标调度问题可以归结为应用管理器之间的合作博弈,理论上可以产生最优解,尽管由于问题的高复杂度而并不容易实现.因此,本文将多目标调度问题作为连续的合作博弈来进一步制定和解决,其中需要3个重要参数的正确定义:博弈参与者、策略和规范的收益.

科学数据流系统往往采取简单的计算模型,特别在数据流模型中,任务流模块执行顺序是由数据流来决定的.有向无环图的任务流构成了云应用,其中,每个节点代表任务,边表示应用节点之间的依赖关系.在基于DAG的任务流中,图为G{V,E},点V={t₁,…,t_n}表示任务流的每个任务,图中的边表示节点之间的任务依赖关系.

图 3描述了数据流类型可以作为数据流解析器的输入.然后,调度映射器将DAG文件格式化为XML和其他元数据信息,比如文件大小等.映射完成以后,任务流调度器创建一个任务列表,并且将任务分配至执行站点.一个任务即为用户将要执行的一个程序.

数据流引擎基于任务之间的依赖来管理任务,以确保一项任务只有在其父任务成功完成的情况下才被释放.数据流引擎只会释放自由的任务至调度器.在调度器中,配置博弈多目标调度功能.该博弈多目标调度将会应用博弈规则,并以一种优化的方式来调度任务至虚拟机.在本节提出的算法中,将调度所有的任务至虚拟机,并以公式(1) 中描述的约束来完成最终的调度.

3.3 博弈调度方案

考虑有K个参与者的合作博弈,每个应用管理器(作为参与者)试图在一定时间内最小化一个任务包T_k的执行时间t_k,基于每个云站点S_i的任务总数δ_k和任务处理速率β_ki.为清楚起见,假定每个应用管理器处理一个任务包的执行.每个管理器的目标是最小化执行时间和任务包的经济成本,同时满足存储和带宽的约束,目标函数的公式表示为

${{f}_{k}}(\Delta )=\frac{{{\delta }_{k}}}{{{\beta }_{k}}}=\frac{{{\delta }_{k}}}{\sum\nolimits_{i=1}^{M}{\frac{{{\theta }_{ki}}}{{{p}_{ki}}}}}$

(4)

${{c}_{k}}(\Delta )=\sum\limits_{i=1}^{M}{{{p}_{ki}}\cdot {{\delta }_{ki}}\cdot {{\eta }_{i}}}$

(5)

${{h}_{i}}(\Delta ,\Gamma )=\sum\limits_{k=1}^{K}{\frac{{{\theta }_{ki}}\cdot {{d}_{ki}}}{{{p}_{ki}}}}\le {{\lambda }_{x,i}}$

(6)

$g(\Delta )=\sum\limits_{k=1}^{K}{s{{r}_{k}}\cdot {{\theta }_{ki}}\le s{{l}_{i}}}$

(7)

其中,Δ是任务分布矩阵(δ_ki)_K×_M,sr_k是任务包T_k的存储需求,sl_i是云站点S_i的存储限制,η_i是云站点的价格,Γ是带宽分布矩阵(b_ki)_K×_M.在公式(5) 中,假定用户仅仅支付有用的计算,并且价格都独立于使用的处理器数量.Δ和Γ都将策略表示为合作博弈中收益的体现.

合作博弈考虑的是参与群体能够协调自身行为的情况,而这作为算法中最重要的机制,使得博弈具有可转移的效用.换句话说,一个有着增加效用的参与者,具有补偿其他有着减少效用参与者的能力.当设计具有可转移效用的博弈时,主要的考虑是开发针对形式化共享资源公平方法的解决方案.例如,以下定义的项_θki表示云站点S_i上任务包k的资源分配情况,其中体现了共享资源的公平性.公式(8) 将其定义为S_i上任务包T_k加权汇总执行时间与S_i上所有任务包总执行时间的比值和S_i上处理器数量m_i之间的乘积:

${{\theta }_{ki}}={{m}_{i}}\cdot \frac{{{\delta }_{ki}}\cdot {{p}_{ki}}\cdot {{w}_{ki}}}{\sum\nolimits_{k=1}^{K}{{{\delta }_{ki}}\cdot {{p}_{ki}}\cdot {{w}_{ki}}}}$

(8)

其中,w_ki表示云站点S_i的任务包T_k中对性能(pw_ki)、成本(cw_ki)、带宽(bw_ki)和存储(sw_ki)优化的不同定义的权重,公式表示如下:

$p{{w}_{ki}}=\frac{\frac{\underset{i\in [1,M]}{\mathop{\min }}\,\{{{p}_{ki}}\}}{{{p}_{ki}}}}{\sum\nolimits_{i=1}^{M}{\frac{\underset{i\in [1,M]}{\mathop{\min }}\,\{{{p}_{ki}}\}}{{{p}_{ki}}}}}=\frac{\frac{1}{{{p}_{ki}}}}{\sum\nolimits_{i=1}^{M}{\frac{1}{{{p}_{ki}}}}}$

(9)

$c{{w}_{ki}}=\left\{ \begin{array}{*{35}{l}} \frac{\frac{1}{{{\eta }_{i}}{{p}_{ki}}}}{\sum\nolimits_{i=1}^{M}{\frac{1}{{{\eta }_{i}}{{p}_{ki}}}}},\text{ }{{\eta }_{i}}\ne 0 \\ \frac{\frac{1}{{{p}_{ki}}}}{\sum\nolimits_{i=1}^{M}{\frac{1}{{{\eta }_{i}}{{p}_{ki}}}}}\to 0,\text{ }{{\eta }_{i}}\to 0 \\ \end{array} \right.$

(10)

$b{{w}_{i}}=\frac{\frac{{{p}_{ki}}}{{{d}_{ki}}}}{\sum\nolimits_{k=1}^{K}{\frac{{{p}_{ki}}}{{{d}_{k}}}}}$

(11)

$s{{w}_{i}}=\frac{\frac{1}{s{{r}_{k}}}}{\sum\nolimits_{k=1}^{K}{\frac{1}{s{{r}_{k}}}}}$

(12)

必须仔细考虑如何写权重函数的问题,以便能够实现更好的性能和成本,并且针对给定问题可以真正地改善调度.如果权重函数选择不佳或者定义不准确,算法有可能找不到解决问题的方案.例如,采用性能权重pw_ki在性能方面提高分配的公平性.因为一个站点对不同的任务可能因为不同的原因而产生不同的适应性,比如数据局部性、内存大小、CPU频率或者I/O速率等.举例来说,如果站点S_i对任务包T_k的执行时间t_ki比在其他站点上低很多,那么就将该任务在该站点上设置较高优先级,并且分配更多的资源.当目标偏离用户期望或者违反一些约束的时候,MOG算法动态选择不同的权重.再者,必须保证每个任务包的权重和为1,那么一个站点的子博弈胜利者必定是其他站点的失败者,否则不能够保证全部合适的分配.在介绍顺序博弈的概念时,本文将解释不同权重的利用.

基于资源的分布以及云站点S_i的处理速率和任务包的总处理速率的比值,将任务分布定义为任务包T_k中的任务数量与站点S_i的任务T_k处理速率和任务包总处理率比值之间的乘积.

${{\delta }_{ki}}={{\delta }_{k}}\cdot \frac{\frac{{{\theta }_{ki}}}{{{p}_{ki}}}}{\sum\nolimits_{i=1}^{M}{\frac{{{\theta }_{ki}}}{{{p}_{ki}}}}}$

(13)

定义3. 以下构成了多目标优化博弈的定义.

(1) K个任务包的管理者作为博弈参与者;

(2) 一套策略D和G由如下的一组约束定义:① δ_ki≥0;② b_ki≥0;③ θ_ki≤δ_ki;④ b_ki≤λ_x,i;⑤ sr_ki≤sl_x,i;⑥ δ_ki=0,if θ_ki<1;⑦ $\sum\nolimits_{k=1}^{K}{{{\theta }_{ki}}}={{m}_{i}}$;⑧ $\sum\nolimits_{k=1}^{K}{{{b}_{ki}}}={{\lambda }_{x,i}}$;⑨$\sum\nolimits_{k=1}^{K}{s{{r}_{ki}}}=i$;⑩ $\sum\nolimits_{k=1}^{K}{{{\delta }_{ki}}}={{\delta }_{k}}$;

(3) 对于每个博弈参与者k∈[1,K],目标函数为f_k(Δ)和c_k(Δ).目标是同时最小化所有的f_k和c_k,并且满足g_k和h_k;

(4) 对于每个博弈参与者k∈[1,K],目标函数的初始值为f_k(Δ⁰,Γ⁰),其中,${{\Delta }^{0}}=({{\delta }_{ki}})_{K\times M}^{0}$是充满了初始任务分布的K×M矩阵,${{\Gamma }^{0}}=({{b}_{ki}})_{K\times M}^{0}$是含有初始化带宽分布的矩阵.Γ⁰计算基于Δ⁰,(Δ,Γ)表示博弈的最优解.一个最初的分布基于Δ⁰和Γ⁰产生,起初,其并不需要是一个能够实现所有约束的可行方案.

对于包含任务包的大规模应用来说,整体完工时间几乎等于总执行时间除以处理器数量.因此,本文的协同优化博弈的性能目标可以近似为最小化总的完工时间.

$\underset{\mathit{\Delta }}{\mathop{\arg \min }}\,(\sum\nolimits_{k=1}^{K}{{{f}_{k}}(\mathit{\Delta })})$

(14)

公式(14) 受到定义3里的10种约束.对于寻找受到一些约束的函数极值问题,典型的方法是通过定义拉格朗日函数.

$\begin{align} & \Theta (\delta ,\xi ,\theta ,\mu ,b,\sigma )=\sum\nolimits_{k=1}^{K}{({{f}_{k}}+{{c}_{k}}+{{g}_{k}}+{{h}_{k}})}+\xi \cdot (\sum\nolimits_{k=1}^{K}{{{\theta }_{ki}}-{{m}_{i}}})+\sigma \cdot (\sum\nolimits_{k=1}^{K}{{{b}_{ki}}-{{\lambda }_{x,i}}})+ \\ & \text{ }\nu \cdot (\sum\nolimits_{k=1}^{K}{{{\delta }_{ki}}-{{\delta }_{k}}})+\sum\nolimits_{k=1}^{K}{\mu _{i}^{k}\cdot {{\delta }_{ki}}}+... \\ \end{align}$

(15)

这里的 Γ,σ,ν,μ表示的是拉格朗日乘子.通常来说,这种问题的准确最优解是难以获得的,因为该问题有着高复杂度和3·K·M个变量.解决方案取决于不同站点上相同任务包中的任务分布、相同站点中不同任务包中的任务分布以及处理器和带宽的分配.换句话说,一个变量的改变,影响了所有其他变量的值.为了克服这种困难,本文将该问题进一步制定为一个连续博弈来近似解决.这里,博弈参与者选择一种策略,其遵循预定义的顺序,并观察在他们前面的参与者的动作.虽然最优的解决方案不会直接从公式(15) 中获取,但可以在一组博弈阶段中获得中间的解决方案,基于以下的不平等序列.

$\sum\nolimits_{k=1}^{K}{F_{k}^{S(1)}({{\Delta }^{0}},{{\Gamma }^{0}})}\ge \sum\nolimits_{k=1}^{K}{F_{k}^{S(2)}}({{\Delta }^{S(1)}},{{\Gamma }^{S(1)}})\ge ...\ge \sum\nolimits_{k=1}^{K}{F_{k}^{S(n)}}({{\Delta }^{S(n-1)}},{{\Gamma }^{S(n-1)}})\ge \sum\nolimits_{k=1}^{K}{{{F}_{k}}}({{\Delta }^{*}},{{\Gamma }^{*}})$

(16)

这里,S表示顺序博弈的阶段,S(n)表示博弈的第n个阶段.在每个阶段,博弈参与者(任务包的管理者)基于上一个阶段的资源分布来提供一系列的策略(任务分布),并且使用公式(8) 来产生新的分布.

博弈中的第1步是初始化任务分配Δ^S(0) 和带宽分配Γ^S(0) ,每个任务包基于每个站点的处理速度分配到一定量的处理器,在最初阶段S(0) ,每个任务包假定所有的处理器和带宽都是可用的.

改写公式(13) ,得到:

${{\delta }_{ki}}={{\delta }_{k}}\cdot \frac{\frac{{{m}_{i}}}{{{p}_{ki}}}}{\sum\nolimits_{i=1}^{M}{\frac{{{m}_{i}}}{{{p}_{ki}}}}}$

(17)

对于云站点S_i中分配给任务包K的带宽b_ki,有:

${{b}_{ki}}={{\lambda }_{x,i}}\cdot \frac{{{d}_{ki}}}{\sum\nolimits_{i=1}^{K}{{{d}_{ki}}}}$

(18)

从公式(17) 、公式(18) 中,得到最初的任务分布Δ^S(0) 和带宽分配Γ^S(0) .

第n阶段资源分配为Π^S(n),资源分配矩阵为Π=(θ_ki)_K×_M,基于上一步的任务分配Δ^S(n-1) 计算得到的.相应地,计算第n步的任务分配Δ^S(n)是通过第n步的资源分配Π^S(n)计算得来的,即:

${{\mathit{\Pi }}^{S}}^{\left( n \right)}=\mathit{\Pi }({{\mathit{\Delta }}^{S}}^{(n-1)});{{\mathit{\Delta }}^{S}}^{\left( n \right)}=\mathit{\Delta }({{\mathit{\Pi }}^{S}}^{\left( n \right)})$

(19)

公式(19) 描述的过程可以通过使用公式(8) 和公式(13) 计算得到.

3.4 多目标博弈算法MOG

本节提出多目标博弈MOG算法,实现了上一节中形式化的博弈调度方法.我们之前的工作^[14]提出了针对性能以及经济成本的双目标优化算法.在如何拓展双目标调度算法至多QoS约束下的多目标情况的思路中,需要解决如何选择一个或多个目标来引导搜索,最终面向一整套的潜在解决方案.最常用的方法是将多目标问题转化成单目标,可以通过给每个标准分配权重来形成一个目标的线性组合,并且汇总成为一个聚集函数.该技术的主要缺点是没有应用程序、基础设施等相关的先验信息来确定权重,这有可能导致现实非线性问题的不可解.另一种经典的方法是在以下3种方法切换:所有目标、每次单个目标和选定作为下一次博弈的权重w_ki.本文这里采用了交替并结合目标的混合型方法.MOG算法首先同时优化性能和通信标准,并附加经济成本的约束.在确定了性能范围后,MOG开始优化成本和通信标准.这里的困难是怎样建立标准应该被优化的顺序,因为这能够影响搜索是否成功.

MOG算法首先需要构建期望执行时间矩阵(ETC矩阵).ETC矩阵由云任务和云站点组成,可以由公式(2) 计算得到.图 4为ETC矩阵的一个示例,其表示了4种任务{t₀,t₁,t₂,t₃}在4个云站点{s₁,s₂,s₃,s₄}的期望执行时间.为了清晰起见,在示例中限制每个站点的规模仅包含一个处理器.

博弈调度算法的伪代码形式共包含3个阶段,见算法1.

阶段1:在获得有关任务和资源的信息以后(例如图 4中的ETC矩阵),生成任务的最初分配Δ⁰和权重矩阵(见算法1中的第3行~第11行).为了便于说明和方便比较,在这个简单的例子中,只考虑任务完成时间的优化.该阶段中,用户可以设置性能约束或者通过简单设置应用的权重为0来过滤掉不需要的站点,即可以阻止将任务映射至那些站点.为了保证所有的约束都满足,可以在第3阶段再次进行验证.

阶段2:重复循环的每次迭代(算法1中的第12行~第15行)都是一次博弈阶段,每阶段由M次子博弈组成(即,每个站点一次).在每个子博弈中,所有的任务包争夺资源分配,并且那些有较大权重的赢得每个站点的子博弈并能够在下一步中获得更多的资源.然而,这些任务由于权重的定义而并不能在每个站点中都保持博弈胜利(即,每个任务包的权重和为1) .因此,在一个站点的子博弈胜利者必定是其他站点的失败者.重复该过程,直到最优.该算法的进一步处理方式取决于算法1中第15行的性能和成本的评估结果,这里的w用来控制博弈次数和优化的程度.在算法1中的第13行,采用不同的权重定义来产生新的资源分配矩阵Π^S(1) .算法2描述了多目标优化算法,即,根据多种目标而进行的权重调整,这是博弈参与者在下一博弈阶段的策略的改变.基本来说,博弈参与者的策略需要随时做出改变,尤其在一些约束没有满足的时候,或者完工时间、经济成本偏离了用户的期望.例如,当存储约束在某个站点不能被满足的 时候,也就是存储资源的平衡条件首先被有最大存储需求sr的用户打破,那么有最大sr的参与者将首先被要求改变策略.因此,已知所有参与者的全局信息,一次权重改变能够通过降序排列用户的sr来简单计算,然后使用存储权重来代替旧的权重.基于Π^S(1) ,采用公式(19) (算法1第14行)来产生第1个任务分布Δ^S(1) .然后重复迭代,直到达到预期优化的上限.

阶段3:最后,最早完成的任务包被删除.为了利用释放的资源,重复以上两步来重新计算剩余任务包的分布,直到所有的应用完成.

  算法1. 博弈调度算法.

  输入:一组应用$\mathbb{R}$;任务包数量K;站点数量M;站点S_i(i∈[1,m])的处理器数量m_i;ETC矩阵(p_ki)_K×_M;任务包k(k∈[1,K])的任务数量δ_k;优化阈值w;站点S_i(i∈[1,m])的带宽限制bl_i;任务包T_k(k∈[1,K])的带宽需求br_k;

  输出:任务分布矩阵Δ^S(n);资源分配矩阵Π^S(n).

  1. Gamer←∅ //初始化参与博弈组

  2. Repeat //阶段1:初始化任务分布Δ⁰和任务包权重,并选择性应用约束条件

  3.  for all v∈$\mathbb{R}$ do

  4.   for all T_k∈w∧T_k not yet scheduled∧(pred(T_k)=∅∨(T_j is completed,∀T_j∈pred(T_k))) do

  5.   Gamer←Gamer∪T_k

  6.   for all i∈[1;M] do

  7.    Calculate pw_ki,cw_ki,sw_ki,通过公式(9) 、公式(10) 、公式(12)

  8.    Calculate _δki,通过公式(13) ,产生Δ⁰

  9.    end for

  10.   end for

  11.  end for

  12.  Repeat //阶段2:搜索最终的任务分布和资源分配

  13.   Π^S(n)←Multiobjective-Schedule(Π,Δ,m,b,λ,p) //见算法2

  14.   计算Δ^S(n)=(δ_ki)_|Gamer|×_M,由公式(19)

  15. until $\sum\nolimits_{k=1}^{|Gamer|}{({{f}_{k}}({{\Delta }^{S(n-1)}})-{{f}_{k}}({{\Delta }^{S(n)}}))}\le \omega \wedge \sum\nolimits_{k=1}^{K}{({{c}_{k}}({{\Delta }^{S(n-1)}})-{{c}_{k}}({{\Delta }^{S(n)}}))}\le \omega $

  16. wait for 任务包完成

  17. //阶段3:移出完成的任务包,释放资源,通过重复阶段1和阶段2来开始一轮新的博弈.

  18. Gamer←Gamer\T,∀T∈Gamer∧T completed

  19. until "∀∈$\mathbb{R}$ 完成

  算法2. 多目标优化算法.

  输入:一组应用;任务包数量K;站点数量M;站点S_i(i∈[1,m])的处理器数量m_i;ETC矩阵(p_ki)_K×_M;任务包k(k∈[1,K])的任务数量δ_k;优化阈值w;站点S_i(i∈[1,m])的存储限制sl_i;任务包T_k(k∈[1,K])的存储需求sr_k;云站点上任务包k的资源分配情况θ_ki;

  输出:资源分配矩阵Π^S(n).

  1. for all T_k∈w do

  2.  Caculate all bw_k,通过应用公式(11) 计算

  3. end for

  4. for all T_k∈v do

  5.  for all S_i∈[1,M] do

  6.   if $\sum\nolimits_{k=1}^{K}{{{b}_{ki}}\cdot {{\theta }_{ki}}>{{\lambda }_{x,i}}\vee }\sum\nolimits_{k=1}^{K}{s{{r}_{ki}}\cdot {{\theta }_{ki}}}>s{{l}_{i}}$then

  7.    重新计算${{{\theta }'}_{ki}}$,通过公式(8) 和公式(11) 或者公式(12) 计算的权重

  8.   end if

  9.   重新计算${{{\theta }''}_{ki}}$,通过公式(8) 和公式(9) 或者公式(10) 计算的权重

  10.  end for

  11. end for

  12. 评估不同权重下不同资源分布Π的收益

  13. return 最佳收益的资源分布Π

3.5 算法分析

图 5(a)和5(b)描绘了MOG算法在总的执行时间和成本随着博弈步骤的收敛性.该实验中,随机产生一些测试用例,分配了10²×10⁴个任务至10²×10²个处理器中.在30~40次博弈内,大多数例子完成了优化过程.最初,任务基于每个站点的处理速率和性价比分布.因此,开始的成本总是很低并且完成时间较长.最初的成本和性能对应于初始化阶段.快速收敛的原因是:某种程度上来说,每个任务包从自身利益出发去争夺最有效的资源.在竞争最有效资源完成以后,算法机制会让博弈参与者将工作负载移至较弱的站点.换句话说,这一机制使得博弈参与者对每个资源的私有已知偏好逐渐汇总成为一个社会性的选择.该机制确保了当参与者个体行为自私的情况下能产生一个全局最优解.最终,所有的任务包能够达到平衡状态,即,不能获得进一步的改善.

4 实 验

本节首先将MOG算法与基于经典的两类调度启发式方法修改的5种贪婪算法进行比较.运行所有测试机器的配置为Intel i7-2640M 2.8GHz处理器和4GB内存,并基于Cloudsim平台^[28]和数据流生成器Pegasus^[1].

4.1 相关算法分析

· 复杂度为O(n×N)的算法^[29].

在任务列表中迭代一次,并按如下方式调度:贪婪最小执行时间(GMET),分配每个任务至提供最快执行速度的机器,同等条件下,则分配至花费成本最小的机器.贪婪最小完成时间(GMCT)分配每个任务至提供最小完成时间或者成本的机器.

· 复杂度为O(n×N²)的算法^[30].

根据以下标准,在选择一个调度之前遍历所有任务:贪婪min-min(Gmin-min)算法首先映射小的任务,并且映射到执行快的机器上;贪婪max-min(Gmax-min)算法首先调度大任务,任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上;贪婪suffrage算法计算每个任务的最小完成时间和次小完成时间的差值,选取所有任务中差值最大的任务和计算资源.

MOG方法的时间复杂度为O(l×K×M),对应于算法的4个嵌套循环,即,算法1第1阶段中的第2行~第4行、第6行.这里的l表示连续博弈的阶段数量,K为全部输入任务流$\varpi \in \mathbb{R}$中的任务包总数,M是云站点数量(每个阶段中的运行工作为常量).算法第2阶段并不会影响复杂度,因为每个阶段中的工作是常量,并且仅仅线性取决于站点的数量和少数的博弈参与者.更重要的是复杂度独立于任务总数,与其他相关方法相比,这是巨大的优势.

图 6为实验结果,体现了MOG算法在不同的计算环境下运行在相同机器上的性能表现.不同计算环境的设置表现为不同的云站点数量,例如10×10表示为有10个云站点,每个站点1个处理器;不同的任务包数量,例如10×10表示为有10个任务包,每个任务包有10个子任务.可以观察到:MOG具有良好的可拓展性,因为博弈阶段数量增长并不会和处理器与任务的数量增加一样快.即使对于10⁶个任务、10⁴个处理器的计算环境,MOG算法也仅仅需要593个博弈阶段和0.36s就完成了调度优化.与Gmin-min之类的算法需要高达1h的优化调度时间形成了鲜明的对比.基于这些分析,在以后的实验中,对MOG方法的最大迭代数量设置为1 000,认为就可以得到足够的收敛.

通过图 7得到了更多的实证结果,即,MOG方法和经典贪婪算法在调度10⁵个任务和10³个处理器情况下的结果比较.MOG的执行时间少于0.3s,显著快于其他算法.例外是GMET的执行时间少于1s,其时间复杂度为O(m+N),这里的m是处理器数量,N是任务数量,N远大于M.然而,GMET有着严重的问题,因为它序列化了大量的任务至最快的站点上.GMCT的时间复杂度为O(m×N),但是它的结果比MOG相差太多.Gmin-min,Gmax-min和Gsuffrage算法的时间复杂度都是O(m·N²),平均执行时间约200s~300s.文献[31]提到了异构的最早完成时间(HEFT)算法,其最初是为工作流设计,在确定重点的阶段中基于升秩排序任务,因此可以通过首先调度小任务而降级成Gmin-min算法.GA算法^{[16, 21]}或者A星算法^[32]随着任务和处理器数量的增加而可拓展性差,并且有可能需要较长时间来生成类似完工时间或成本等的解决方案.针对该原因,考虑GA方法并不适合这里的问题,也不去进一步研究它(即使它可以比Gmin-min的完工时间降低5~10个百分点^[21]).其他算法都和本文以上讨论的类似,或者并不适用于这里的问题,比如,工作队列^[32]适合均匀集群.

4.2 实验验证

为了实验的完整性,将MOG方法和相关算法进行对比,并根据ETC矩阵来模拟评估MOG的性能.不同的ETC矩阵是根据资源和异构任务的不同程度产生的,其在特定范围内的均匀分布中选出.表 3给出了模拟环境的细节.

在范围[1,100]的高异构资源引起了站点之间在任务执行时间和成本上的显著差异,而范围在[1,1000]高异构任务表示了不同任务的预期执行时间变化很大.假设每个任务包中的任务数量基于一个均匀分布的范围[1000, 2000]内随机产生,每个站点的处理器数量在[64,128]范围变化.任务包在工作流中每对任务包之间有 10%的非循环依赖概率.这里不选择模拟大量应用和站点的原因基于两点:(1) Gmin-min一类的算法复杂度需要几小时来运行,这使得整个模拟不便;(2) 扩大仿真规模只会增加本文提出的MOG算法与相关启发式算法相比中的优势.在该模拟环境中,我们设计了4个场景中对算法进行了评估:高任务高资源异构(HtHr);高任务异构低资源异构(HtLr);低任务异构,高资源异构(LtHr);低资源低任务异构(LtLr).为了量化用户或者应用是否收到系统资源的公平的份额,本文使用了Jain的公平度指数^[33].

$Fairness=\frac{{{\left( \sum\nolimits_{k=1}^{K}{{{T}_{k}}} \right)}^{2}}}{K\cdot \sum\nolimits_{k=1}^{K}{T_{k}^{2}}}$

(20)

这里,K表示应用的数量,T_i是应用${{\mathbb{R}}_{i}}$的执行时间.公平度范围为[0,1],其中,0表示最坏的情况,1表示最好的情况(如图 8所示).

表 3介绍了4种场景下的输入,图 9、图 10为考虑到完工时间和公平性目标的相应模拟结果.GMET总是给出最坏的结果,因为它映射所有的任务至最快的机器.Gmax-min给出了较差的结果,因为它只适合当少量任务比其余任务大得多的情况下,而因为模拟环境采用均匀分布生成,所以不会遇到这一情况.此外,Gmax-min对小任务缺乏公平,因此,它比大部分算法表现较差.GMCT对于高度异构机器来说表现非常好,是因为它有更高的可能性来选择最快的机器,尤其针对大的任务.对于低机器异构性表现欠佳,是因为它仅考虑了完成时间但是忽略了任务的执行时间.在高异构机器中,GSuffrage表现和GMCT类似,低异构机器情况下,其优于GMCT约5~10个百分点,因为它通过考虑任务执行时间,做出更多的智能决策.Gmin-min在每种情况下给出了第二佳的结果,归因于其均匀的任务执行时间分布,但是因为首先处理最小的任务而导致缺乏公平性.

在图 11中,展示了各种算法所产生的skyline结果.Gmin-min在开始仅仅处理最小的任务而忽视了更大的任务.然而,最小的任务并非有着最佳的性能/价格比,因此,Gmin-min不能够很好地执行.GSufferage表现非常类似Gmin-min,因为类似的原因.与Gmin-min相反,Gmax-min给出更好的结果,因为其在开始的时候调度大的任务,这使得大任务在站点中更多获得最佳的性价比.G-MCT给出了第二佳的结果,因为其无意识地选择了具有平均大小的任务,在统计学上有着更大的可能性,具有最佳性能价格比.MOG在大多数情况下给出了最佳的调度,然而对于任务间具有复杂依赖关系的工作流来说,它可能无法提供最佳结果,因为这里的调度问题不能够被归结为一种典型的可解博弈.

MOG在这4种计算场景下都提供了最佳的性能,因为其采取了最佳的全局决策.它在LtHr情况下优于Gmin-min算法10个百分点,其余3种情况皆优于5个百分点.可以看到:在确保公平的同时,效率也能得到改善.进一步观察在图 10中,平均来说,MOG总是获得较好的公平度0.95以上.

4.2.1 通信存储约束

表 4给出了模拟计算环境,这里的真实值是在特定范围内,从均匀分布中随机产生.

正如预期的那样,如图 12所示,从最好到最坏的相对顺序是:MOG,Gmin-min,GSufferage,GMCT,Gmax-min,GMET.

当站点中没有带宽或者存储约束时,MOG表现比Gmin-min好5%~10%,比其他算法低至少26%的成本.在有约束的情况下,MOG提高了多数据流性能至少33%,并且降低了至少70%的成本.如图 13所示.MOG提供了最佳的性能,因为其在性能和带宽同时优化方面做出了最佳的全局决策,而其余的启发式算法仅仅找到一种两个目标之间简单的妥协,带宽要求也不能够满足,导致了计算能力的潜在浪费.在成本方面,图 13说明了所有的算法需要约两倍于MOG的成本.

5 结 论

随着混合云中的大规模应用得到越来越多的关注,数据流管理服务如何高效并且有效地调度和动态地引导应用执行显得越来越重要.本文分析了一类以大量同质任务为特征应用的主要瓶颈,提出了一种能够满足通信和存储约束的多目标调度MOG解决方案,其中包括4种重要指标:完工时间、成本、存储资源和网络带宽.基于模拟的实验结果,表明了本文提出的MOG方法在完工时间、经济成本和公平性等方面提供了更好的解决方案,与其他的Gmin-min,Gmax-min或者GSufferage贪婪方法相比,算法执行时间更少.这些都表明本文成功地克服了其他启发式方法的收敛速度慢和随机结构的缺点.

在未来的研究中,着重研究本文提出的算法如何适应其他指标,如内存、安全性、资源可用性等.以后将从两方面来扩展我们的方法:(1) 寻找新的合适的权重,使得任务包能够更快或者更慢地完成;(2) 对任务包指定截止期限,并根据分配的期限将其划分为子任务,在每个子任务中应用我们的方法.最后,本文设计的用任务处理率来表达任务分配的方法(见公式(13) ),可以很容易地扩展到处理动态任务的在线调度问题.