摘要
针对工作流作业调度问题，提出使用关键路径法进行工作流的执行时间预测和资源分配。工作流执行时间预测算法使用并行应用有向无环图描述工作流中子作业的执行顺序。基于此顺序，为子作业进行系统资源的逻辑分配。根据子作业的特征和资源分配信息，使用梯度提升决策树进行子作业执行时间预测，并计算工作流的关键路径。关键路径上所有子作业的完成时间之和即为工作流的执行时间。若预测的工作流执行时间满足用户要求，则根据子作业执行顺序和资源分配方案进行作业调度，执行工作流。对比实验表明，两个工作流的执行时间预测误差分别为5.72%和1.57%。与Spark默认调度算法相比，工作流调度算法将两个工作流的完成时间分别缩短了15.71%和15.44%。
Abstract
For the problem of workflow job scheduling, the critical path method was proposed to predict the execution time of the workflow and allocate resources. The parallel application directed acyclic graph was used to describe the relationships among the sub-jobs of a workflow in the workflow execution time prediction algorithm. Based on this order, the system resources were logically allocated to the sub-jobs. According to the characteristics and resource allocation information of sub-jobs, the gradient boosting decision tree-based algorithm was used to predict the execution time of sub-jobs, and the critical path of workflow was calculated. The sum of the completion time of all sub-jobs on the critical path is the execution time of the workflow. If the predicted workflow execution time satisfies the user′s requirements, job scheduling was executed according to the sub-job execution sequence and resource allocation scheme, and the workflow was executed. Comparative experiments show that the prediction errors of the execution time of two workflows are 5.72% and 1.57%, respectively. Compared with the default scheduling algorithm of Spark, the workflow scheduling algorithm reduces the completion time of the two workflows by 15.71% and 15.44%, respectively.
工作流作业由多个具有控制约束或数据约束的子作业构成，广泛存在于工业生产和科学计算领域。对工作流子作业执行约束的分析，有助于对子作业进行合理调度，从而缩短工作流的执行时间。由于分布式系统能够同时执行多个作业，因而被认为是处理工作流作业的理想选择[1]。
作业调度属于NP-Complete问题，其最主要的目标是缩短作业的完成时间。分布式异构系统中的作业调度要完成的任务有两种，其一是为作业安排最优的执行顺序，其二是为每个作业分配最适合的系统资源以进行任务的执行[2]。由于作业调度的特点，目前提出的调度算法多是启发式算法。为了提高异构系统性能，降低调度算法的复杂度，Topcuoglu等提出了异构最早完成时间（heterogeneous earliest finish time，HEFT）算法，该算法在每一步为向上等级最高的作业分配处理器[3]。Zhou等提出了一种基于列表的改进预测最早完成时间的静态作业调度算法，算法使用悲观费用表对作业的优先级进行评价[4]。为了能够缩短用户作业的完成时间，同时最小化能量消耗，Zhang等提出了基于模因算法的工作流调度算法[5]。该算法与同类算法相比，能够缩短4.9%的作业执行时间，能量则节省了24.3%。Kumar等提出使用混合模型的遗传算法作业调度方法以减少作业完成时间、提高分布式实时系统的可靠性[6]。在分析了基于队列的作业调度方法的不足后，Zheng等提出了基于计划的模拟退火算法以进行作业调度[7]。与基于队列的调度方法相比，该方法能够缩短40%的作业等待时间，减少30%的作业响应时间。Li等采用博弈论研究了并行环境下简单线性退化任务的调度问题[8]。对于Spark应用，Fu等采用二部图模型完成了位置感知的任务调度算法，有效减少了数据的网络传输和访问延迟[9]。高性能计算领域发展极快，高性能计算的应用已不仅为计算密集型，数据密集型应用也越来越多。Fan等提出了多目标优化遗传算法，综合考虑系统CPU、burstbuffer等多种资源的利用情况[10]。随着人工智能技术的发展，越来越多的机器学习算法被应用于任务的调度。Fan等搭建了一个层次化的神经网络，使用深度强化学习的方法让任务调度代理完成对目标环境的学习，从而做出满足优化目标的调度方案。实验表明，论文中提出的算法比传统的启发式优化算法性能提升45%[11]。
工作流一般使用有向无环图（directed acyclic graph，DAG）进行描述和分析[12]。Adhikari等详细介绍了使用DAG对工作流进行建模的方法[13]。Ilavarasan等提出的高效能任务调度算法（performance effective task scheduling，PETS）使用DAG对作业进行描述[14]。文中进行分析和实验使用的DAG一部分是随机生成的，另一部分则是根据实际应用产生的。Sulaiman等提出的使用复制方案的基于混合列表的任务调度（hybrid list-based task scheduling using duplication scheme，HLTSD）算法同样使用DAG作为作业表示的方法，算法能够得到最小费用的调度方案[15]。Martinez等使用DAG描述作业之间的串并行关系。提出使用特征矩阵以描述作业的信息，包括DAG中路径的数目、DAG的层数及每层中节点的数目、相邻层之间的边的条数等。DAG的第一条路径为关键路径，对它优先进行资源分配[16]。
准确进行作业执行时间预测能够为作业调度和资源分配提供依据。目前已有一些作业执行时间预测的研究工作。Yu等详细分析了Map/Reduce模式下，Map阶段和Reduce阶段具体任务的执行时间划分[17]。在每个核仅能执行特定类型任务的情况下，Han等分析了多核异构环境中并行DAG任务的最差响应时间（worst-case response time，WCRT），给出了两种WCRT的分析方法和有效的实现算法，提高了WCRT的计算精度[18]。针对包含有加速元件，如现场可编程门阵列（field programmable gate array， FPGA）、图形处理器（graphic processing unit， GPU）的并行异构硬件结构，Serrano等研究了DAG任务的响应时间分析[19]。为了提高在加速部件上所运行任务和在通用多核上所运行任务的并行程度，文献[19]提出了DAG的转换算法。基于同构系统中作业响应时间分析和DAG转换算法，进行了包含加速元件的异构系统中DAG任务的响应时间分析。Gao等设计了一个具有较高预测精度的两步预测框架[20]。预测模型采用背景梯度提升回归。具有相似性能表现的作业使用相同的性能预测模型。模型通过匹配资源利用特征和历史应用来进行执行时间的预测。如何在众多的时间预测方法中选择一种有效可行的预测方法，成为作业执行时间预测中首先要解决的问题。Kumbhare等建立了线性回归模型进行作业运行时间预测，并使用随机森林提供模型在不同输入数据时预测时间的转化系数[21]。很多研究工作通过减少高估作业运行时间来提高运行时间预测的准确性，Fan等则认为过低估计作业执行时间同样会引起很多问题。为解决低估作业执行时间的问题，他们提出了在线运行时间调整框架Tobit运行时间预测（Tobit runtime prediction，TRIP）[22]。
目前有关工作流作业执行时间预测领域的研究基本假定子作业的执行时间是已知的。本文的创新工作体现在将子作业执行时间预测与工作流执行时间预测及子作业调度有机结合在一起。即通过分析工作流中各子作业的依赖关系，确定子作业的执行顺序，并依此进行系统资源分配。在此基础上，完成子作业的执行时间预测。根据各子作业的执行时间，计算出工作流中的关键路径，从而预测出工作流作业的执行时间。
考虑这样一个应用场景：一家企业拥有自己的小型集群，并经常需要处理复杂的工作流作业。为了确保每一个用户的工作流能够在指定截止时间前完成，需要预测出工作流作业的执行时间。如果预测出的执行时间不能满足用户的要求，则需要及时将预测结果告知用户，方便用户选择是将作业转移到其他集群去执行，还是延长作业的截止时间。这样及时有效的信息沟通，能够提升用户的满意度。若预测出集群可以在用户期望的时间内完成作业，则按照进行时间预测时生成的最优资源分配方案进行资源的分配、作业的调度和执行。最优资源分配方案的使用可以有效缩短工作流的完成时间。
本文提出了基于子作业执行时间预测的工作流作业调度算法。在分析各个子作业间的执行约束后，为子作业进行资源的逻辑分配。根据资源分配方案使用梯度提升决策树（gradient boosting decision tree，GBDT）算法预测出子作业的执行时间后，计算工作流执行的关键路径，进而得到工作流作业的执行时间。对比正向和逆向资源分配方案下预测的工作流执行时间，按照时间较短的方案进行作业流中各子作业的资源物理分配，并运行工作流。
1 基于关键路径分析的工作流作业时间预测与调度算法
为了预测工作流作业的运行时间并进行工作流中各个子作业的合理调度，提出了基于关键路径分析的工作流作业时间预测与调度算法。算法流程如图1所示。
此算法的基本思想是分析工作流作业中各个子作业的约束关系，生成对应的有向无环图。为了强调本算法对子作业执行并行度的提升目标，工作流作业对应的有向无环图称为并行应用有向无环图（parallel application DAG，PAD）。算法通过广度优先搜索（breadth first search， BFS）找到子作业执行的串并行关系。将图中不同顶点作为广度优先搜索的起始点，会得到不同的搜索结果。结合PAD的特点，本算法采用了正向和逆向的两种搜索，即从第一个子任务或最后一个子任务开始进行广度优先搜索，得到两组子作业执行顺序的串并行关系。
根据子作业之间的关系，为各子作业进行集群资源的分配。将子作业的信息和资源分配信息作为单作业时间预测模型的输入，预测出各子作业的执行时间。根据子作业的执行时间和相互关系，找到PAD中的关键路径。此关键路径上各个子作业完成时间之和即为工作流作业的预计完成时间。
可以看出，进行单作业的执行时间预测是算法的核心，因此首先介绍这个算法。
2 单作业的时间预测算法
机器学习中常用的回归预测算法包括梯度提升（gradient boost）、线性回归（linear regression）[23]、决策树（decision tree）[24]、支持向量机（support vector machine，SVM）[25]、随机森林（random forest，RF）[26]和梯度提升决策树等。
图1基于关键路径分析的工作流作业时间预测与调度算法
Fig.1Critical path analysis-based workflow execution time prediction and scheduling algorithm
GBDT可以用于回归、分类、排序等各种任务，具有模型训练要求的数据量小、预测精度高、调参时间短、可解释性强、能够有效处理低维数据和非线性数据等优点，广泛应用于各个领域的预测，例如心脏疾病的预测[27]、短期电量负载的预测[28]、焊点质量预测[29]、遥控操作中的力反馈和对象位置[30]预测、金融指数数据预测[31]、道路交通拥堵情况预测[32-33]、作业执行时间预测等。文献[29]通过实验对比了GBDT与其他预测算法的性能。实验结果表明，与K最近邻算法（K-nearest neighbors，KNN）、SVM、决策树、朴素贝叶斯和RF等算法相比，GBDT的F1值最高。由于数据量的限制，文献[31]无法使用神经网络等需要大量训练集的预测方式。在实验对比中，文献[31]提出的基于GBDT的金融指数预测模型的预测效果优于SVM和RF。文献[32]指出使用GBDT预测道路交通拥堵的准确率能够达到94.46%。文献[33]得到的每日交通指数的预测准确度也超过90%。
本文的训练集较小，同时对作业运行时间进行预测的实时性要求高，因此选择GBDT作为时间预测算法。
2.1 GBDT算法描述
GBDT是gradient boost和decision tree两种算法的融合，它通过多轮迭代不断产生弱学习器，每个学习器在上一轮学习器的残差基础上进行训练，通过减低残差不断提高学习器的精度。
GBDT使用的损失函数L（yi，f（xi））是平方损失，使用式（1）计算得到。
(1)
式中，yi表示样本的输出，f（xi）表示学习器。
(2)
式中，yi-f（xi）表示残差。
GBDT算法的描述见算法1。将使用GBDT算法预测工作流中各个子作业的执行时间，进而计算出工作流的执行时间。
2.2 基于GBDT的时间预测模型
进行作业执行时间预测的目标是提高集群的资源使用率并最小化作业执行时间，从而提高集群性能。图2是基于GBDT的时间预测模型的总体架构。
构建用户作业执行时间预测模型包括以下步骤：
1）数据收集。分析作业的整体执行流程，结合已有的研究成果确定对作业性能影响较大的参数。根据这些作业参数，生成符合要求的作业并在集群中执行，收集作业执行时间等数据。
2）模型训练。使用收集的数据样本进行GBDT模型训练，得到作业执行时间的预测模型。
3）作业执行时间预测。当有新的作业进入集群时，利用作业执行时间预测模型得到相应的预测执行时间。在此过程中，将模型给出的配置作为作业的新配置参数，在集群中运行作业，记录结果，并将此次结果放入数据集中，以便进一步优化时间预测模型。
算法1 GBDT算法描述
Alg.1 Description of GBDT
图2基于GBDT的时间预测模型
Fig.2GBDT based time prediction model
2.3 GBDT模型的数据收集和训练
GBDT模型能够根据当前集群状态及作业的信息完成作业执行时间预测。下面介绍模型输入参数的选择、数据收集及模型训练。
模型参数的选择。Spark共有 180 多个配置参数，但对作业处理性能影响较大的参数为数不多。本文共选取了6个参数作为GBDT模型的输入参数，如表1所示。其中，前4个参数是 Spark 的配置参数，inputsize表示作业的输入数据大小，nodes表示作业使用的集群节点数。
表1Spark作业参数
Tab.1 Spark job parameters
GBDT模型的输入参数为表1中的6个参数，输出是作业在Spark集群中的运行时间。数据采集所用的作业为BigDataBench[34]的WordCount和Sort负载。数据样本的输入采用排列组合的方式确定，表1给出了一个输入参数组合。
确定输入参数后，将符合参数条件的作业提交到Spark集群，集群按输入参数的要求进行配置。每个输入组合在集群中运行10次，如果10次运行结果的误差在合理的范围内，则保留这组数据，否则将该数据舍弃。经过实验，最终确定了1 000组有效输入参数，结合对应的作业运行时间，共得到1 000条样本数据。这1 000组数据用于GBDT模型的训练和测试，其中80%为训练集，20%为测试集。训练完成后，使用测试集进行GBDT模型测试。
3 工作流作业执行时间预测算法
在预测得到工作流中每一个子作业的运行时间后，需要对工作流中子作业的相互关系进行分析，进而完成工作流的执行时间预测。建立图的模型来表示工作流的内部结构。
3.1 图模型的建立
为了处理含有内部数据依赖关系的工作流作业，建立了PAD模型。图中的节点ai表示子作业i完成的事件，节点a0是定义的一个空作业节点，表示整个工作流作业的开始事件，它没有前趋。图中的最后一个节点表示最后一个子作业的完成事件，它没有后继节点。PAD中的有向边＜ai，aj＞表示子作业i是子作业j的前趋作业，仅当子作业i执行结束，子作业j才可以开始运行。有向边上的权值Tj表示子作业j的执行时间，此时间由GBDT时间预测模型预测得到。
以“学生学业等级分析评价”工作流为例。此工作流可以分解为6个子作业，分别为:子作业1“学生学业数据预处理”，子作业2“根据课程考试成绩计算绩点”，子作业3“计算学生课外科技竞赛加分”，子作业4“计算学生参加志愿者等活动加分”，子作业5“学生学习成绩汇总”和子作业6“学生学业情况分析，给出学生学业等级”。各子作业间存在的数据依赖关系如表2所示。其中的子作业0是为了构建图模型增加的空作业，没有执行时间。此工作流对应的PAD如图3所示。
表2工作流作业中各子作业的依赖关系
Tab.2 Dependency among the sub jobs of a workflow
图3工作流作业PAD
Fig.3PAD of the workflow
3.2 子作业执行顺序的搜索
进行作业执行时间预测首先需要知道集群系统为作业分配的资源数量。因为工作流作业中各个子作业有执行顺序的约束，所以必须先查找出子作业可能的执行顺序，尤其是确定可以并行执行的子作业。本文使用BFS完成对工作流作业PAD的搜索。针对工作流作业的特点，进行了正向搜索和逆向搜索。
1）正向搜索：将PAD中节点a0作为起始点，运行BFS，确定每一个子作业i所在的层次，即从a0到ai的路径的长度。
2）逆向搜索：将PAD中最后一个节点作为起始点，运行BFS，确定每一个子作业i所在的层次。
表3给出了对图3中PAD分别进行正向搜索和逆向搜索得到的子作业层次关系。同一层次的子作业之间没有数据依赖关系，可以并行执行。因此根据正向和逆向搜索的结果，可以得到正向和逆向两组子作业串并行执行关系。
表3图3中工作流各子作业的正向和逆向串并行执行关系
Tab.3 Forward and reverse series-parallel execution relationship of each sub-job in the workflow in Fig.3
3.3 子作业逻辑资源的分配
当子作业的执行顺序确定后，就可以为它们进行集群资源的逻辑分配，方法见式（3）和式（4）。针对目前设定的应用场景，一个工作流可以使用集群中全部的资源。
(3)
(4)
为每个子作业分配的CPU核数Cpui和内存数目Memoryi是进行作业执行时间预测重要的输入参数。式（3）和式（4）中：TotalCPU和TotalMemory是集群中CPU的总核数和总的内存容量；Wi是子作业i所在层次的子作业的数目，即可以并行执行的子作业的数目，同一层次中的子作业平分集群中的CPU和内存资源； floor（）为向下取整函数。
针对正向和逆向两组子作业串并行执行关系，进行资源逻辑分配后，可以得到正向资源分配方案和逆向资源分配方案。
3.4 工作流作业关键路径的确定
得到子作业的资源分配方案后，使用时间预测算法可以得到每一个子作业的执行时间。基于工作流的PAD，使用关键路径算法，就可以找到PAD中的关键路径。工作流中关键路径上各子作业是工作流中最为重要的作业，任一关键作业的延期都会导致整个工作流无法按时完成。关键路径上所有子作业完成时间之和即为工作流的执行时间。
(5)
(6)
其中：est（ai，Rs）是资源分配方案Rs下事件ai的最早发生时间，作业k是作业i的前趋作业，Tk是子作业k在Rs下的预测执行时间，可以知道est（a0，Rs）=0。lst（ai，Rs）是Rs下事件ai的最晚发生时间，作业h是作业i的后继作业，PAD中最后一个事件的最晚发生时间与最早发生时间一致，即lst（afinal，Rs）=est（afinal，Rs）。
根据式（5）和式（6）可以计算出工作流PAD中每一个事件的最早发生时间est和最晚发生时间lst。对于事件ai，若有lst（ai，Rs）=est（ai，Rs），则事件ai为关键事件，子作业i为关键作业。所有的关键事件，构成PAD的关键路径。一个PAD中可能存在多条关键路径，但是关键路径上所有事件对应的子作业的执行时间之和是一样的。这个时间即为工作流作业在此资源分配方案Rs下的预测执行时间。
3.5 工作流作业的执行
在正向资源分配方案和逆向资源分配方案下可以分别预测得到工作流作业的执行时间，较小的预测时间作为工作流的预测执行时间。判断工作流的预测执行时间是否能够满足用户作业截止时间要求。若可以，则按照对应的资源分配方案进行资源的物理分配，开始工作流作业的执行。
3.6 算法复杂度分析
当作业时间预测模型GBDT训练完成后，输入作业参数就可以得到预测的作业运行时间。因此基于关键路径分析的工作流作业执行时间预测算法的复杂度决定于广度优先搜索算法和关键路径的求取算法。
假设工作流作业中包含n个子作业，其对应的PAD中有m条边时，确定各子作业所处层次的广度优先搜索算法的时间复杂度为O（n+m），寻找关键路径的算法的时间复杂度也为O（n+m）。因此本文算法的时间复杂度为O（n+m）。通常一个工作流中包含的子作业数量不会很多，子作业间相互具有的关系数量也不会很高，即n和m的数量级都不太大。因此相对于作业的运行时间，本文算法的执行时间数量级较低，执行代价很低。
4 实验及结果分析
本节通过实验进一步说明基于关键路径分析的工作流作业执行时间预测与调度算法的使用和性能。
4.1 实验环境
本实验构建了一个基于Spark Standalone模式的异构集群，集群包含6个节点（1个主节点、5个从节点），集群节点的系统配置如表4所示。
表4集群节点硬件配置
Tab.4 Hardware configuration for the cluster nodes
4.2 实验作业介绍
本小节进行了两个工作流的实验。工作流1包含6个WordCount子作业，子作业的执行顺序依赖关系如表2和图3所描述，其数据量见表5，其中子作业0是为了算法实现而添加的空作业，它的数据量为0，因而没有执行时间。工作流2包含10个Sort子作业，子作业的执行顺序依赖关系见图4，其数据量见表6。
表5工作流1各子作业的数据量
Tab.5 Data size of each sub-job in workflow 1
图4工作流作业2的PAD
Fig.4PAD of workflow 2
表6工作流2各子作业的数据量
Tab.6 Data size of each sub-job in workflow 2
4.3 工作流作业1的预测运行时间和实际运行时间
使用BFS从正向和逆向对图3所示的PAD进行搜索，各子作业所处的层次关系见表3。可以得到正向和逆向的工作流作业执行顺序。
正向搜索：子作业1→子作业2、3、4并行执行→子作业5→子作业6。
逆向搜索：子作业1 →子作业2和3并行执行→子作业4和5并行执行→子作业6。
基于上述搜索结果对子作业进行系统资源分配，并使用基于GBDT的时间预测算法进行各子作业在对应资源分配方案下的执行时间预测，结果如表7和表8所示。
表7工作流作业1的正向资源分配方案及子作业的预测执行时间
Tab.7 Resource allocation scheme under forward searching for workflow 1 and the predicted execution time of sub-jobs
表8工作流作业1的逆向资源分配方案及子作业预测的执行时间
Tab.8 Resource allocation scheme under backward searching for workflow 1 and the predicted execution time of sub-jobs
根据各子作业的执行时间预测结果，进行关键路径的计算，可以得到如表9所示的关键路径和工作流作业的预测执行时间。
表9工作流作业1的关键路径和预测执行时间
Tab.9 Critical path and the predicted execution time of workflow 1
从表9可看出，逆向搜索出的子作业执行顺序可以获得较短的工作流作业执行时间，因此这个工作流的预测执行时间为239 s。
表10列出了在逆向资源分配方案下工作流作业1中各个子作业的预测执行时间和实际运行时间，以方便进行对比。
表10工作流作业1的预测执行时间和实际运行时间对比
Tab.10 Comparison of the predicted running time and actual running time of workflow 1
从表10可以看出，各子作业的预测执行时间误差都在16%以内。造成误差的主要原因是目前用于GBDT模型训练的数据量不是很大，未能将模型的超参数调整到最优的状态。另外一个原因是当前的GBDT算法实现采用了传统的方式，因此限制了预测的精度，后续将采用XGBoost实现GBDT的算法。XGBoost对GBDT实现进行了深度优化，例如XGBoost支持多种类型的基分类器；能够对损失函数进行二阶泰勒展开，可以同时使用一阶和二阶导数；XGBoost的目标函数多了正则项，使得学习得到的模型不容易过拟合。
由于子作业执行时间预测有的高于实际运行时间，有的低于实际运行时间，总的工作流的运行时间预测误差为5.72%。
4.4 工作流作业2的预测运行时间和实际运行时间
使用广度优先搜索算法从正向和逆向对图4所示的PAD进行搜索，各子作业所处的层次关系见表11。
表11工作流作业2的子作业的正向和逆向串并行执行关系
Tab.11 Forward and reverse series-parallel execution relationship of the sub-jobs of workflow 2
可以得到正向和逆向的工作流作业2执行顺序。
正向搜索：子作业1和2并行执行→子作业3、4、5并行执行→子作业6和7并行执行→子作业8和9并行执行→子作业10。
逆向搜索：子作业1 →子作业2和3并行执行→子作业4、5、6 并行执行→子作业7、8、9 并行执行→子作业10。
基于上述搜索结果对子作业进行系统资源分配和执行时间预测，得到的结果如表12和表13所示。
表12工作流作业2的正向资源分配方案及子作业的预测执行时间
Tab.12 Resource allocation scheme under forward searching for workflow 2 and the predicted execution time of sub-jobs
表13工作流作业2的逆向资源分配方案及子作业预测的执行时间
Tab.13 Resource allocation scheme under backward searching for workflow 2 and the predicted execution time of sub-jobs
根据各子作业的执行时间预测结果，进行关键路径的计算，可以得到如表14所示的关键路径和工作流作业的预测执行时间。
表14工作流作业2的关键路径和预测执行时间
Tab.14 Critical path and the predicted execution time of workflow 2
从表14可看出，对于工作流作业2而言，正向搜索得到的资源分配方案较好，因此工作流作业2的预测执行时间为619 s。
表15列出了在正向资源分配方案下工作流作业2中各个子作业的预测执行时间和实际运行时间。可以看出，各子作业的预测执行时间误差都在15%以内，工作流的预测时间误差较小，为1.57%。
表15工作流作业2的预测执行时间和实际运行时间对比
Tab.15 Comparison of the predicted running time and actual running time of workflow 2
对包含6个子作业和10个子作业的工作流进行实验的结果表明，当工作流中子作业数量增加时，工作流执行时间预测算法能够保持一定的预测准确度，具有可扩展性。本文算法的单个作业运行时间预测的精度可以达到84%。误差产生的基本原因是GBDT模型中特征和正则化参数的选择没有达到最优，后续的研究工作将进行更多的实验，优化模型参数配置。
4.5 与Spark默认作业调度算法的对比
为了验证基于关键路径分析的工作流作业调度算法的有效性，将工作流作业1和2分别使用本文算法和Spark默认作业调度算法进行运行。为了减少实验误差，每组实验分别执行5次，取5次结果的平均值作为工作流作业的执行时间。实验结果如图5所示。
对比工作流作业的预测执行时间和实际运行时间，可以看到对于工作流作业1，采用基于关键路径分析的资源分配和作业调度算法，作业运行时间缩短了15.71%；工作流作业2的作业运行时间缩短了15.44%。可见，本文提出的算法能够根据工作流中各子作业的特点为其分配合适的资源，并进行有效的作业执行顺序调度，从而能够缩短工作流作业的完成时间。
图5工作流作业执行时间对比
Fig.5Workflow job execution time comparison
5 结论与展望
为了提高服务质量和用户的满意度，数据中心、超算中心等需要在规定的时间范围内完成用户作业。本文提出一个针对小规模集群的基于关键路径分析的工作流作业运行时间预测和作业调度算法。该算法通过预测工作流中每一个子作业的执行时间，结合关键路径的计算，预测出工作流作业的执行时间。使用本算法给出的资源分配和作业调度方案，能够缩短工作流的执行时间，提高系统性能。
下一步的研究工作将在以下几个方面开展：
1）目前的工作主要针对小规模集群进行，即认为每个工作流独占系统的全部资源。后面的工作将取消这个假设，考虑多个工作流并发和系统资源的争用问题。
2）缩短关键路径上作业的执行时间能够压缩工作流作业的完成时间。当前在进行资源分配时，同层次的作业均分系统资源，没有考虑如何减少关键作业的执行时间。下一步，将为关键作业进行优先资源分配，在可能的范围内缩短其运行时间。
3）作业的执行时间与作业的类型关系密切，需要作为时间预测算法的输入。将选取不同类型的作业进行更多的实验，确定更为合适的GBDT模型参数配置，提高时间预测算法对不同类型作业的预测精度。
4）目前的实验较为简单，仅以二个实例说明本文提出的算法是可行的。下一步将扩大实验数据的来源。一方面，采用随机算法生成DAG；另一方面寻找更多的应用实例。更多的实验将进一步说明算法的有效性和可扩展性。
