基于多约束图分割机制的科学工作流调度

王柳婧 蒋一翔 徐元根

(浙江中烟工业有限责任公司宁波卷烟厂 浙江 宁波 315504)

0 引 言

天文学、粒子物理学和生命科学等诸多科学领域的数据量正成爆炸式增长。这种数据密集型科学应用需要高性能的系统以科学工作流的形式最大化吞吐量[1]。而科学工作流系统的最关键问题即是工作流调度，其目标是决定资源与任务间的匹配与执行。常见的调度算法如Min-Min算法[2]和HEFT算法[3]均以优化工作流完成时间makespan为目标的，而makespan则取决于工作流任务的计算代价和通信代价。

文献[4]提出一种基于图割的调度算法，充分考虑了减少各个数据中心间数据的传输量，但没有考虑各个数据中心的计算能力和负载情况。实际情况中，即使各个数据中心的计算能力相同，由于工作流任务的不同，其负载也可能不同。文献[5]提出一种云工作流中间数据存储算法，以降低工作流执行开销。该算法首先根据中间数据的起源生成中间数据关系图，然后得出生成代价，再将生成代价和存储代价对比作出是否存储该数据的决策。文献[6]将常规的图分割方法应用于工作流调度中，算法赋予图的顶点权值，并以此为根据进行边的切割，得到权值最小的图划分情况。但算法仅考虑了一维权值，与实际的工作流任务调度场景并不符合。

本文重点关注于利用图分割方法优化工作流执行过程中的数据传输量[7]。图论是表示计算数据依赖性的常用模型，给定图G=(V,E)，V表示顶点集合，V={v1,v2,…,vn}，E表示边集，E=V×V。如果(vi,vj)∈E，则顶点vi和vj是邻居节点。通常，可基于工作流中任务间的依赖性把工作流表示为有向无循环图DAG，图的顶点表示计算单元，边表示任务依赖性。图分割的目标是为了有效地并行计算决定计算与数据的分割，即通过将顶点集划分为n个子集并均分至n个计算节点上，同时通过分区间的边修剪最小化节点间的通信量。为了解决以上问题，本文设计了一种多约束图分割的工作流调度算法，实现工作流中通信代价的最小化，并有效降低工作流执行时间。

1 工作流中的数据传输

1.1 工作流调度及数据传输

工作流示例讨论数据传输问题如图1所示。该工作流请求一个存储节点中存储的四个输入文档数据，并由两个阶段组成：任务A和任务B。在任务A阶段，每个任务接收一个输入文档。在任务B阶段，每个任务接收来自于任务A阶段的两个输入。所有任务执行于包括两个计算节点的分布式系统中。对于该工作流的调度，作如下两个假设：(1) 分布式系统为同质的，且两个计算节点拥有相同性能；(2) 每个阶段中的所有任务需要相同的计算代价，且在每个阶段中的所有数据传输拥有相同的通信代价。以HEFT作为调度算法进行该工作流的调度，首先计算任务的升秩值ranku，由于任务A1～A4的计算代价相同，故4个任务的ranku是相同的，此时，从任务A1～A4中随机选择一个进行调度。假设首先选择任务A1。接下来基于最早完成时间EFT选择执行任务A1的计算节点。然而，由于只有输入数据量均是相同的，无论节点如何分配EFT均是相同的，故任务A1的计算节点也是随机选择的。然后，其他节点被选择执行接下来被选择的任务。最终，在HEFT算法下，任务A1～A2被随机分配至计算节点。因此，图1(a)和图1(b)中任务分配的概率是相同的。同时，HEFT算法的目标函数执行跨度makespan对于图1(a)和图1(b)也具有相同的值，如图2所示。

(a) 低效任务分配

(b) 高效任务分配图1 任务分配与数据传输

(a) 对应图1(a)的调度

(b) 对应图1(b)的调度图2 调度结果

然而，图1(a)和图1(b)中的数据传输量是不同的。图1(a)中数据传输有三次，而图1(b)仅有一次。该示例表明先前阶段中任务A的节点分配对于接下来的依赖性中(即A1,A2→B1)的通信代价拥有重要影响。

1.2 Montage科学工作流的数据传输

以下以更为复杂的科学工作流结构Montage[8]作为示例进行说明，其结构如图3所示。Montage工作流由包括若干任务的8个阶段组成。例如：第一阶段为mProjectPP，即在目标飞行器上设计一个任务代表一个镜像。在每个阶段中的任务数量取决于输入文档的数量(或数以万计)。图3中两个并行阶段拥有与图1中相似的依赖模式，即单个任务接收前任任务的多个输入，如mProjectPP→mDiff和mBackground→mAdd1(前一mAdd)。这些阶段通过任务依赖性进行分布，并构建为单个工作流DAG。为了最小化这种复杂工作流结构中的数据传输，需要基于DAG的所有依赖性决定如何将节点分配至任务。

图3 Montage工作流的DAG结构

1.3 标准图分割

图分割是复杂工作流中为了最小化数据传输分配任务至计算节点的常用方法[9]。给定图G=(V,E)，V为顶点集，E为边集，将V平均划分为n组，V1,V2,…,Vn，即|V1|=|V2|=…=|Vn|，使得在尾节点属于不同子集的同时其边的数量达到最小。以上的图分割问题为NP-完全问题，可扩展为图中每个顶点或边拥有一个权重的情形。如果顶点拥有权重，则每个子集中顶点的权重之和是相等的；如果边拥有权重，则其尾节点属于不同子集的边的权重之和是最小化的。定义以上分割为标准图分割。

对于工作流DAG，顶点和边分别代表任务和数据依赖，本文以最小化数据传输为目标，等同于最小化边的剪切数。当应用标准图分割方法至Montage工作流的DAG结构时，其结果如图4所示。图中显示出前任任务被分派为右侧的两组，终端任务被分派为左侧的一组，这是由于所有顶点被平均划分，而未考虑任务阶段，即标准图分割无法反映任务的并行性。图5是本文设计的分割结果，其顶点在每个阶段是均衡的。因此，工作流DAG的分割算法需要考虑每个并行阶段中任务的均分要求，使得边修剪最小化。

图4 标准图分割

图5 均衡图分割

2 基于MCGP的工作流调度

2.1 多约束图分割机理

比较标准图分割中顶点权重为单一的一维数值，多约束图分割MCGP中的顶点权重为包括多个值的矢量。MCGP的目标是均衡每一维度中的权重值之和。图6为MCGP的实现范例。范例中，图中的顶点被赋予二维权重矢量，图6(a)是边修剪数为4得到的分割，然而，此时第二维的权重和分别为26和14，这是一种不均衡分割。图6(b)是边修剪数为5(在于图6(a)中的4)得到的分割。然而，两个维度上的权重之和是均衡的，这即为MCGP的分割方法，其目标是使所有维度上的权重矢量被同步得均衡。

为了最小化复杂工作流结构中的数据传输，需要基于DAG中所有任务间的依赖性决定如何将节点分配至任务。本文以最小化数据传输为目标，等同于最小化边的剪切数。相比传统图分割方法的不均衡分割，MCGP算法可以通过所有维度上权重矢量的同步均衡，使得代表任务的顶点间的数据传输量是所有可能边修剪情形中最小化的，更加准确地描述工作流结构中任务的并行性并将任务并行扩展至最优，从而降低任务间的通信代价(边权重即代表通信代价)。

图6 多约束图分割示例

2.2 决定任务阶段

在利用MCGP对工作流DAG进行分割前，需要定义任务阶段，在任务阶段中任务可基于工作流的依赖性并行执行。该过程等同于工作流DAG的顶点集V被划分为子集P1,P2,…,Pl。任务阶段的具体定义方式如下：不存在前驱任务的任务定义为第一阶段，表示为P1={vk|(vj,vk)∉E，vj∈V}。紧邻第一阶段的任务定义为第二阶段任务。因此，第i阶段Pi可通过遍历任务依赖性得到。如果一个任务依赖于不同阶段的多个任务，则其阶段定义为最大阶段的下一阶段。该算法可表示为Pi={vk|(vj,vk)∈E，vj∈Pi-1且不存在vj∈Pi′，i′≥i，i≥2}。图7是Montage工作流的任务阶段定义结果。

图7 工作流DAG的权重矢量

2.3 权重矢量

以上定义权重矢量wi。权重矢量的长度为Q中阶段的数量，即|Q|=max{di}。则于第i阶段Pi∈Q，wi的di维度设置为1，wi的其他所有维度设置为0。对于其他阶段Pi∉Q，权重矢量wi设置为0矢量。例如：如果|P1|≥n，|P2|

以下分析算法在每个阶段中的工作机制。考虑一个权重DAG，每个顶点权重以权重矢量的第di维度的值代替，那么，第i阶段的顶点权重为1，其他阶段为0。如果应用标准图分割进行划分，顶点均分仅在第i阶段可完成，且其他阶段的划分不存在约束，其权重为0。同时，最小化边修剪的目标可应用于整个DAG。而MCGP算法可在所有阶段同步实现均分，并最小化边修剪量。该算法中，权重矢量的维度在任务阶段中未被分配，且顶点数量小于分割量，即|Pi|

3 仿真实验

本节利用一个集群系统以Montage工作流作为测试源进行实验分析，工作流的输入数据为2MASS影像数据集的子集[10]，表1给出了该数据集的具体参数[11]。表2给出了集群环境的相关性能配置，共使用8个计算节点进行工作流执行，因此，工作流DAG可分割为8个分组。在初始状态下，所有输入文档存储于单个节点上。

表1 输入数据集

表2 集群系统配置

实验通过以下三种算法进行工作流的任务分配：轮转调度算法[12]、异构最早完成时间算法HEFT以及本文提出的MCGP算法。轮转调度算法是一种最简单最公开的任务调度方法，该算法将所有的就绪任务按照先来先服务的原则组织成一个队列，然后为所有任务分配一个时间段(即时间片)，依次在时间片结束前进行相应任务的调度与执行。HEFT算法主要是通过赋予任务不同的秩值，定义任务的优先级，决定任务最优的调度次序，然后以最早完成时间为标准选择执行任务的节点，可以以较低的时间复杂度得到更少的任务执行时间。选择两种算法的依据在于：前者是任务调度系统最为公平的算法，尤其适合于调度串型结构的任务；后者是任务调度效率较高的经典算法，但仅考虑了任务执行的代价问题，未考虑任务结构间的通信问题。由于所测试的工作流结构为Montage工作流，其结构中混合具有串型和并型任务，利用这两种算法执行工作流可以观察算法对相应工作流结构的适应情况，进而得出本文算法的优势所在。

此外，本文研究了可产生相同结果影像数据的两种不同模式的Montage工作流，区别在于mAdd1阶段。该阶段中，目标区域被划分为n×m个子区域，重叠部分的输入影像在mAdd程序中被联立为子影像。子区域的大小配置为工作流的一个参数。实验中，分别研究4×4和8×4两种模式的工作流。由于实验配置部分在集群系统中执行工作流的节点数量设置为8，为了使单个节点上分配的子区域数量为整数，工作流模式需要设置为8的倍数，则以上两种模式下分配于每个节点上的子区域数量分别为2和4。可进一步增加8×8模式的工作流，但此时单个节点上的子区域数增加至8，子区域的增多可能带来远程数据访问的增多，这对于算法而言，在降低数据传输量上是不利的。

实验1观察在每种算法进行工作流调度时所访问的文档数据量的变化。每种情况下，所有数据访问的总量为24 GB。工作流执行过程中远程数据访问的比率如图8所示。在4×4模式中，远程数据访问比率为：1) RR算法为87.9%；2) HEFT算法为47.4%；3) MCGP算法为14.0%。结果表明MCGP算法可以极大地降低节点间的数据访问比率。HEFT算法的性能差于MCGP，这是由于MCGP拥有更好的初始节点分配模式。在8×4模式中，MCGP算法的远程数据访问比率为15.4%，大于4×4模式，这是由于区域的扩大本身会带来最多的远程数据访问，但仍然小于另种两种算法。综合来看，MCGP在降低工作流执行过程的数据访问量是有效可行的。

图8 远程数据访问比率

实验2观察每种算法进行工作流调度的时间变化，结果如图9所示。对于MCGP算法，调度时间中包括约0.03 s的图分割时间，该时间远小于整个工作流的调度时间。在4×4模式中，MCGP算法比较RR算法和HEFT算法在调度时间上分别降低了31%(53 s)和22%(34 s)，表明MCGP在调度效率性能是更优的。调度时间的降低比率31%小于远程数据访问比率74%，这是由于调度时间包括数据读、写和计算等时间，而远程数据访问比率的降低仅影响数据读取时间。从4×4模式到8×4模式下MCGP的调度时间增加较小是由于分割执行较差，但调度效率仍然可以得到提高。同时，MCGP算法中53 s的调度时间降低仅通过0.03 s的图分割代价得到。综合分析，MCGP在改进工作流执行效率的性能也是有效可行的。

图9 工作流调度时间

4 结 语

为了降低工作流应用中节点间的数据通信开销，本文设计了一种基于多约束图分割的工作流调度算法。算法通过多维度的顶点权重矢量机制和有向边的修剪机制，在所有维度上实现了权重和的均衡，进而得到了最小化的任务间数据传输量，降低通信代价。利用Montage工作流进行实验，结果表明，算法在降低数据通信量和工作流调度效率方面是有效可行的。