地理分布式云中基于最短路径算法的工作流任务调度方法

摘要

本发明公开了一种地理分布式云中基于最短路径算法的工作流任务调度方法，该方法能使所有部分的工作流任务的执行时间和执行能耗最少，从而使整个工作流任务的执行时间和执行能耗最优。本发明结合工作流任务的特点和地理分布式云资源的特点提出来基于斐波拉契堆的最短路径工作流任务调度方法。本调度方法适用于地理分布式云中的工作流任务调度，它通过将工作流任务的有向无环图转换为超图，对超图进行划分之后，对每个划分使用Dijkstra算法得出任务执行时间和执行能耗最小的调度方法。这一优化调度方法充分利用了系统资源，缩短了工作流任务的执行时间，最小化了工作流任务的执行能耗。

权利要求

1.一种地理分布式云中基于最短路径算法的工作流任务调度方法，其特征在于：包括如下步骤：

1)根据任务数量和任务的执行顺序将有向无环图工作流任务图转化为超图的形式；

m

2)将超图通过m次粗化之后转化为一个充分小的超图H ，并多级递归平分方法将粗化后m m

的超图H划分为K个部分，得到超图H的K‑路初始划分m

3)通过选择超图H 顶点的移动增益最大的部分移动K个顶点分区中的顶点来细化分区l 0 0

∏，尽量最小化切割大小同时维持平衡约束，获得具有分区∏的平面超图H；

0

4)依次对平面超图H中的每条路径的任务调度建立任务调度模型，并计算每条路径中所有划分的工作流任务的完成时间T和执行能耗E，使用T+E作为调度模型中的边的权值；

5)对每条路径按照Dijkstra算法选择最短路径的工作流任务调度策略，具体包括：

5.1)初始化路径v中每个顶点的最短路径估计d(vi)，其中除了源点s的最短路径估计d(vs)初始化为0外，与源点s直接相连的顶点的最短路径估计初始化为边的长度，其他点的最短路径估计均被初始化为正无穷；

5.2)创建一个空斐波拉契堆Q，按照5.1)中初始化顺序和最短路径估计依次将顶点插入到斐波拉契堆Q中；

5.3)选取斐波拉契堆Q中的最小值点u，计算(s,u)的最短路径，并将u添加到顶点集合S；

5.4)对Q中的每个顶点vi，若经过u后，源点s到顶点vi的最短路径变短，则更改d(vi)为经过u后的路径长度d(u)加边(u,vi)的长度，并删除Q中顶点u，调整斐波拉契堆Q；

5.5)重复步骤5.3)和5.4)直至斐波拉契堆为空，找出所有顶点的最短路径；

6)重复步骤4)和步骤5)，找出基于所有路径的最优任务调度方案。

2.根据权利要求1所述的地理分布式云中基于最短路径算法的工作流任务调度方法，其特征在于：所述步骤2)中每个初始划分Vk∈Π(k＝1,2,...,K)满足的平衡准则：Wk≤Wavg(1+ε)

其中ε为所允许的最大不平衡率，Wk为划分Vk中所有顶点的权重之和，Wavg为所有顶点权重均匀分布时各个划分的权重，已知w[v]为顶点的权重，Wk和Wavg的计算方式为：Wavg＝∑v∈Vw[v]/K。

3.根据权利要求1所述的地理分布式云中基于最短路径算法的工作流任务调度方法，其特征在于：所述步骤3)中超图顶点移动增益计算的具体步骤包括：

3.1)通过迭代所有与顶点vi连接的边来计算顶点vi的离开增益leave‑gain；

3.2)若没有正的离开增益，则返回，否则执行步骤3.3)；

3.3)通过迭代所有与顶点vi连接的边来计算顶点vi的最大到达损失；

3.4)计算每个至少连通一条包含顶点vi的切割边的划分的移动增量，返回顶点vi的最大移动增量和对应移动到的划分。

说明书

地理分布式云中基于最短路径算法的工作流任务调度方法

技术领域

[0001] 本发明涉及计算机云存储技术领域，特别涉及一种地理分布式云中基于最短路径算法的工作流任务调度方法。

背景技术

[0002] 云计算的诞生是信息技术革命的产物。云计算应用了成熟的虚拟化技术，可以将大量的分布在不同区域位置的服务器、存储设备、网络设施和软件系统等IT资源整合成逻
辑上统一的虚拟资源池，为大量用户提供各类安全可靠、成本低廉、交付简单、高可扩展的
计算或存储服务。用户则基于“按量付费”的原则，通过互联网从云计算系统获取相应服务。
随着信息技术的快速发展以及网络带宽的日益提高，人们对于计算和存储的要求越来越
高，传统的计算模式已经不能有效满足人们对于高性能计算能力或海量数据存储空间的迫
切需求，地理分布式云的概念应运而生。地理分布式云由许多位于不同地理位置的云构成，
例如Google拥有分布在8个不同国家的13个云数据中心。地理分布式云比传统的云计算模
式具有更大的存储能力和更快的处理速度，能为用户提供更好的服务。如今越来越多的应
用依赖于地理分布式云，比如媒体流应用、传感器网络和在线社交网络等。

[0003] 地理分布式云中的任务调度问题是当前重要的研究，研究地理分布式云中的工作流任务调度方法具有重要的意义。在地理分布式云中选择合适的任务调度方法，可以有效
提高任务执行效率的同时降低任务执行能耗。近年来，地理分布式云中的任务调度问题得
到了许多学者们的广泛关注，并提出了多种任务调度方法。当前的地理分布式云中的任务
调度方法通常将计算任务迁移到数据所在数据中心，通过传输处理后的中间结果减少数据
量的传输成本，但是这些设计都是在假设数据中心之间的链接不会发生瓶颈的前提下进行
设计的。设计离线最优任务调度算法可以使作业完成时间全局最小化。然而，这种离线优化
不可避免地依赖于中间结果的任务执行时间和传送时间的先验知识，如果没有复杂的预测
算法，这两者都不是现成的。即使有这样的知识，地理分布式云中的大数据处理工作也可能
涉及一个包含数百个任务的有向无环图而对于这样一个有向无环图进行调度的最优解决
方案通常是NP‑难问题。

发明内容

[0004] 本发明的目的是针对现有技术的不足，提出一种地理分布式云中基于最短路径算法的工作流任务调度方法，通过充分利用系统资源，能提高任务执行效率的同时减少任务
执行能耗。

[0005] 为实现上述目的，本发明所设计的地理分布式云中基于最短路径算法的工作流任务调度方法，其特殊之处在于，包括如下步骤：

[0006] 1)根据任务数量和任务的执行顺序将有向无环图工作流任务图转化为超图的形式；

[0007] 2)将超图通过m次粗化之后转化为一个充分小的超图Hm，并多级递归平分方法将m m
粗化后的超图H划分为K个部分，得到超图H的K‑路初始划分

[0008] 3)通过选择超图Hm顶点的移动增益最大的部分移动K个顶点分区中的顶点来细化0 0
分区 尽量最小化切割大小同时维持平衡约束，获得具有分区Π的平面超图H ；

[0009] 4)依次对平面超图H0中的每条路径的任务调度建立任务调度模型，并计算每条路径中所有划分的工作流任务的完成时间T和执行能耗E，使用T+E作为调度模型中的边的权值；

[0010] 5)对每条路径按照Dijkstra算法选择最短路径的工作流任务调度策略，具体包括：

[0011] 5.1)初始化路径v中每个顶点的最短路径估计d(vi)，其中除了源点s的最短路径估计d(vs)初始化为0外，与源点s直接相连的顶点的最短路径估计初始化为边的长度，其他
点的最短路径估计均被初始化为正无穷；

[0012] 5.2)创建一个空斐波拉契堆Q，按照5.1)中初始化顺序和最短路径估计依次将顶点插入到斐波拉契堆Q中；

[0013] 5.3)选取斐波拉契堆Q中的最小值点u，计算(s,u)的最短路径，并将u添加到顶点集合S；

[0014] 5.4)对Q中的每个顶点vi，若经过u后，源点s到顶点vi的最短路径变短，则更改d(vi)为经过u后的路径长度d(u)加边(u,vi)的长度，并删除Q中顶点u，调整斐波拉契堆Q；

[0015] 5.5)重复步骤5.3)和5.4)直至斐波拉契堆为空，找出所有顶点的最短路径；

[0016] 6)重复步骤4)和步骤5)，找出基于所有路径的最优任务调度方案。

[0017] 优选地，所述步骤2)中每个初始划分Vk∈Π(k＝1,2,...,K)满足的平衡准则：

[0018] Wk≤Wavg(1+ε)

[0019] 其中ε为所允许的最大不平衡率，Wk为划分Vk中所有顶点的权重之和，Wavg为所有顶点权重均匀分布时各个划分的权重，已知w[v]为顶点的权重，Wk和Wavg的计算方式为：

[0020]

[0021] Wavg＝∑v∈Vw[v]/K。

[0022] 优选地，所述步骤3)中超图顶点移动增益计算的具体步骤包括：

[0023] 3.1)通过迭代所有与顶点vi连接的边来计算顶点vi的离开增益leave‑gain；

[0024] 3.2)若没有正的离开增益，则返回，否则执行步骤3.3)；

[0025] 3.3)通过迭代所有与顶点vi连接的边来计算顶点vi的最大到达损失；

[0026] 3.4)计算每个至少连通一条包含顶点vi的切割边的划分的移动增量，返回顶点vi的最大移动增量和对应移动到的划分。

[0027] 优选地，所述步骤4)中工作流任务的完成时间T的计算方法为：

[0028]

[0029] 其中workload为一条路径中某个划分的工作负载，mj为数据中心j中当前活跃的物理机的数量，数据中心j中每台物理机的平均服速率为μj，该划分中所有数据的平均传输
距离为distance。

[0030] 优选地，所述步骤4)中工作流任务执行能耗E的计算方法为：

[0031] E＝Ej(t)＝PUEj·mj(t)[αjμj+βj]

[0032] 已知活跃的服务器的数量mj，参数αj、βj和vj，并且给定数据中心j的功率使用效率度量PUEj。

[0033] 优选地，所述步骤2)中切割尺寸度量定义x(Π)的计算方式为：

[0034]

[0035] 目前广泛使用并被证明可以精确模拟并行稀疏矩阵向量乘法的超图划分尺寸为连通度‑1度量。在这个度量中，每条切割边n对切割尺寸的影响为c[n](λn‑1)。

[0036] 传统的工作流任务调度方法都是直接对工作流任务的有向无环图进行调度，但是简单的有向无环图只能体现两个任务的先后执行关系，无法从全局的角度考虑系统资源的
利用和任务执行的能耗问题。在地理分布式云环境中，考虑到系统资源的利用和任务执行
效率以及任务执行的能耗是为用户提供更好服务的关键因素。在任务调度过程中，将工作
流任务的有向无环图通过任务的执行关系和任务量的大小转化为工作流任务超图，然后对
工作流任务超图进行K‑路划分，转化为更小的超图。通过对划分后的每个部分建立任务调
度模型，求解任务执行时间和执行能耗最低的任务调度方法，使任务调度达到最优。本发明
提出基于斐波拉契堆的最短路径工作流任务调度方法，该方法能使所有部分的工作流任务
的执行时间和执行能耗最少，从而使整个工作流任务的执行时间和执行能耗最优。

[0037] 本发明结合工作流任务的特点和地理分布式云资源的特点提出来基于斐波拉契堆的最短路径工作流任务调度方法。本调度方法适用于地理分布式云中的工作流任务调
度，它通过将工作流任务的有向无环图转换为超图，对超图进行划分之后，对每个划分使用
Dijkstra算法得出任务执行时间和执行能耗最小的调度方法。这一优化调度方法充分利用
了系统资源，缩短了工作流任务的执行时间，最小化了工作流任务的执行能耗。

附图说明

[0038] 图1为本发明地理分布式云中基于最短路径算法的工作流任务调度方法的流程图。

[0039] 图2为地理分布式云中基于最短路径算法的工作流任务调度模型。

具体实施方式

[0040] 以下结合附图和具体实施例对本发明作进一步的详细描述。

[0041] 本发明提出的地理分布式云中基于最短路径算法的工作流任务调度方法，是以当前地理分布式云中的任务调度方法为基础，结合工作流任务的特点而提出来的。如图1所
示，本算法包括如下步骤：

[0042] 1)根据任务数量和任务的执行顺序将有向无环图工作流任务图转化为超图的形式；

[0043] 2)将超图通过m次粗化之后转化为一个充分小的超图Hm，并多级递归平分方法将m m
粗化后的超图H划分为K个部分，得到超图H的K‑路初始划分

[0044] 切割尺寸度量定义x(Π)的计算方式为：

[0045]

[0046] 每个初始划分Vk∈Π(k＝1,2,...,K)满足的平衡准则：

[0047] Wk≤Wavg(1+ε)

[0048] 其中ε为所允许的最大不平衡率，Wk为划分Vk中所有顶点的权重之和，Wavg为所有顶点权重均匀分布时各个划分的权重，已知w[v]为顶点的权重，Wk和Wavg的计算方式为：

[0049]

[0050] Wavg＝∑v∈Vw[v]/K。

[0051] 3)通过选择超图Hm顶点的移动增益最大的部分移动K个顶点分区中的顶点来细化0 0
分区 尽量最小化切割大小同时维持平衡约束，获得具有分区Π的平面超图H。

[0052] 超图顶点移动增益计算的具体步骤包括：

[0053] 3.1)通过迭代所有与顶点vi连接的边来计算顶点vi的离开增益leave‑gain；

[0054] 3.2)若没有正的离开增益，则返回，否则执行步骤3.3)；

[0055] 3.3)通过迭代所有与顶点vi连接的边来计算顶点vi的最大到达损失；

[0056] 3.4)计算每个至少连通一条包含顶点vi的切割边的划分的移动增量，返回顶点vi的最大移动增量和对应移动到的划分。

[0057] 4)依次对平面超图H0中的每条路径的任务调度建立任务调度模型，并计算每条路径中所有划分的工作流任务的完成时间T和执行能耗E，使用T+E作为调度模型中的边的权值。

[0058] 工作流任务的完成时间T的计算方法为：

[0059]

[0060] 其中 为一条路径中一个划分的工作负载，mj为数据中心j中当前活跃的物理机的数量，数据中心j中每台物理机的平均服速率为μj，该划分中所有数据的平均传输
距离为distance。

[0061] 工作流任务执行能耗E的计算方法为：

[0062] E＝Ej(t)＝PUEj·mj(t)[αjμj+βj]

[0063] 已知活跃的服务器的数量mj，参数αj、βj和vj，并且给定数据中心j的功率使用效率度量PUEj。

[0064] 5)对每条路径按照Dijkstra算法选择最短路径的工作流任务调度策略，具体包括：

[0065] 5.1)初始化路径v中每个顶点的最短路径估计d(vi)，其中除了源点s的最短路径估计d(vs)初始化为0外，与源点s直接相连的顶点的最短路径估计初始化为边的长度，其他
点的最短路径估计均被初始化为正无穷；

[0066] 5.2)创建一个空斐波拉契堆Q，按照5.1)中初始化顺序和最短路径估计依次将顶点插入到斐波拉契堆Q中；

[0067] 5.3)选取斐波拉契堆Q中的最小值点u，计算(s,u)的最短路径，并将u添加到顶点集合S；

[0068] 5.4)对Q中的每个顶点vi，若经过u后，源点s到顶点vi的最短路径变短，则更改d(vi)为经过u后的路径长度d(u)加边(u,vi)的长度，并删除Q中顶点u，调整斐波拉契堆Q；

[0069] 5.5)重复步骤5.3)和5.4)直至斐波拉契堆为空，找出所有顶点的最短路径；

[0070] 6)重复步骤4)和步骤5)，找出基于所有路径的最优任务调度方案。

[0071] 下面详述本发明的研究过程：

[0072] 在地理分布式云中进行工作流任务调度之前，需要对工作流任务的特征进行分析，从而合理资源分配，提高任务执行效率，减少任务执行能耗。对于有向无环图的工作流
任务调度问题已有学者研究，但目前的研究中少有考虑工作流任务每条路径之间的关联性
对任务执行造成的影响。常见的地理分布式云中的工作流任务调度方法将计算任务迁移到
数据所在数据中心，通过传输处理后的中间结果减少数据量的传输成本，但是这些设计都
是在假设数据中心之间的链接不会发生瓶颈的前提下进行设计的。虽然设计离线最优任务
调度算法可以使作业完成时间全局最小化，但是这种离线优化不可避免地依赖于中间结果
的任务执行时间和传送时间的先验知识，如果没有复杂的预测算法，这两者都不是现成的。
即使有这样的知识，地理分布式云中的大数据处理工作也可能涉及一个包含数百个任务的
有向无环图而对于这样一个有向无环图进行调度的最优解决方案通常是NP‑难问题。超图
不仅可以表示任务之间的先后执行关系，还可以表示不同执行路径间的关系。如果根据任
务的执行特征将工作流任务转化为超图，根据超图中每个子任务的执行时间和执行能耗对
超图进行划分，对每个划分按照最短路径算法找出任务调度策略，保证每个划分的最短执
行时间和执行能耗最小，则最终可使整个工作流任务的执行时间和执行能耗最小。

[0073] 本发明提出的地理分布式云中基于最短路径算法的工作流任务调度方法模型由两部分组成：(1)将工作流任务的有向无环图转化为超图，对超图进行K‑路划分。首先根据
任务的数量和任务的执行顺序将工作流任务的有向无环图表示转化为超图表示，然后在满
足超图平衡的前提下对超图进行K‑路划分。(2)对划分后的超图的每个部分进行任务调度。
为了提高任务执行效率的同时减少任务执行能耗，对每个部分建立任务到云数据中心的调
度模型之后，采用Dijkstra最短路径算法寻找执行时间和执行能耗最小的调度方法。其调
度模型如图2所示。

[0074] 调度方法中的相关参数定义

[0075] (1)云数据中心之间的通信时间 地理分布式云中云之间的数据传输时间不可忽略，本发明中任务传输时间随地理距离线性增长，已知区域i和区域j之间的距离Li,j和线
性函数的斜率为0.02，则可计算两个云之间的通信时间。

[0076]

[0077] (2)云数据中心j的功率消耗Ej(t)：能耗是当前研究中的热点问题，本发明中认为v
每个云数据中心都完全由电网供电。已知运行速度为μ的服务器消耗的功率量可以用αμ+β
表示，其中α是正因子，β为空闲状态下的功耗，指数参数v是经验值，一般v＞1。根据云数据
中心中活跃的服务器的数量mj和云数据中心j的功率使用效率度量PUEj，以及参数αj、βj和
vj，则可以计算云数据中心j的功率消耗。

[0078]

[0079] (3)划分Vk中所有顶点的权重之和Wk：w[v]为顶点的权重，则可计算划分Vk中所有顶点的权重之和Wk。同时可计算当所有顶点权重均匀分布时各个划分的权重Wavg。

[0080]

[0081] Wavg＝∑v∈Vw[v]/K  (4)

[0082] 如果超图划分Π满足ε平衡，其中ε为所允许的最大不平衡率，则每个划分Vk∈Π(k＝1,2,...,K)满足平衡准则：

[0083] Wk≤Wavg(1+ε)  (5)

[0084] (4)切割尺寸度量定义x(Π)：目前广泛使用并被证明可以精确模拟并行稀疏矩阵向量乘法的超图划分尺寸为连通度‑1度量。在这个度量中，每条切割边n对切割尺寸的影响
为c[n](λn‑1)。

[0085]

[0086] (5)工作流任务的完成时间T(u,v)：

[0087]

[0088] 其中workload为一条路径中某个划分的工作负载，mj为数据中心j中当前活跃的物理机的数量，数据中心j中每台物理机的平均服速率为μj，该划分中所有数据的平均传输
距离为distance,则D＝0.02·distance+5。

[0089] 本专利提出的地理分布式云中基于最短路径算法的工作流任务调度方法，是以超图的划分为基础结合地理分布云中的最短路径算法而提出来的。本方法首先根据工作流任
务的执行顺序和子任务数的数量将工作流作业转化为超图表示，然后按照公式(5)的约束
对超图进行划分。通过对超图划分后的每个部分建立任务调度模型，按照公式(2)计算任务
的执行能耗，公式(7)计算任务的执行时间，任务的执行时间和执行能耗之和为调度模型中
边的长度。然后利用基于斐波拉契堆的最短路径算法寻找最优的任务调度方法。本方法具
体描述如下：

[0090] (1)根据任务数量和任务的执行顺序将工作流任务的有向无环图转化为超图H0的形式；

[0091] (2)将超图H0通过m次粗化之后转化为一个充分小的超图Hm，并多级递归平分方法m m
将粗化后的超图H划分为K个部分，得到超图H的一个K‑路初始划分

[0092] (3)计算超图中所有顶点的最大移动增量和对应移动到的划分。

[0093] (4)通过选择超图顶点的移动增益最大的部分移动K个顶点分区中的顶点来细化0 0
分区 尽量最小化切割大小同时维持平衡约束，获得具有分区Π的平面超图H；

[0094] (5)对超图中的某条路径的任务建立任务调度模型，并计算该路径中所有划分的工作流任务的完成时间T(u,v)和执行能耗E(u,v)，使用T(u,v)+E(u,v)作为调度模型中的边的权值；

[0095] (6)对每条路径按照基于斐波拉契堆的Dijkstra算法选择最短路径工作流任务调度策略

[0096] 调度方法的伪代码描述

[0097]

[0098]

[0099]

[0100] 由算法的伪代码描述可以得到，第1行将工作流任务的有向无环图转化为超图工1
作流任务；第2到10行，将工作流任务对应的超图进行m次粗化，得到m个粗化超图序列H ,
2 m
H ,...,H ；第11到18行通过计算超图中每个顶点的最大移动增益对粗化后的超图进行细
化，最终得到划分后的超图。第19到38行对划分后的超图的每个部分进行基于最短路径算
法的工作流任务调度。其中第20到22行通过计算任务在每个云数据中心的执行时间和执行
能耗来表示任务调度模型中边的权重。第23行到27行使用基于斐波拉契堆的最短路径算法
寻找执行时间和执行能耗最小的工作流任务调度顺序。通过保证超图中每个划分的任务执
行时间和执行能耗最小化使得整个工作流任务的执行时间和执行能耗最小，到达提高任务
执行效率的同时降低执行能耗。

[0101] 本领域的技术人员应当理解，此处所述的具体实施方案仅用解释本发明专利，并不用于限制本发明专利。在本发明专利的精神和原则之内作出的任何修改、等同替换和改
进等，均应包含在本发明专利的保护范围之中。