Gaia系统中的面向图迭代作业的运行时间预测系统及方法

1.一种Gaia系统中的面向图迭代作业的运行时间预测系统，其特征在于，包括相似度管理模块、作业匹配模块和运行时间预测模块；所述相似度管理模块包括抽样执行单元、静态相似度计算单元和动态相似度计算单元；所述抽样执行单元通过偏向随机跳转方法对图数据集进行抽样，获得样本图数据，在样本图数据集上执行迭代算法用于捕获样本图迭代作业的离线特征；所述静态相似度计算单元通过抽样执行单元捕获的离线特征来计算当前图迭代作业和历史图迭代作业间静态相似度；所述动态相似度计算单元通过对图迭代作业真正执行中捕获到的统计信息来计算当前图迭代作业和历史图迭代作业间的动态相似度；相似度管理模块将计算得到的静态相似度和动态相似度送入所述作业匹配模块；所述作业匹配模块包括相似度评估单元、训练点收集单元和参数训练单元；所述相似度评估单元构建相似度评估函数，对相似度管理模块送来的静态相似度和动态相似度进行有效性评估，根据有效性评估的结果选出匹配的历史图迭代作业送入所述运行时间预测模块；所述训练点收集单元用于收集训练相似度评估函数中参数的训练数据点；所述参数训练单元利用所述训练数据点训练得到相似度评估函数的参数送入所述相似度评估单元；所述运行时间预测模块通过作业匹配模块所匹配的历史图迭代作业预测当前图迭代作业的剩余运行时间；所述静态相似度计算单元，采用如下方法计算当前图迭代作业Job run 和历史图迭代作业Job comp 间的静态相似度，包括静态计算相似度和静态消息传递相似度；所述静态计算相似度为：其中，S 1 为当前图迭代作业Job run 和历史图迭代作业Job comp 间的静态计算相似度，图迭代作业Job在第i次迭代时的活跃节点比例 ActVert i (Job)表示图迭代作业Job在第i次迭代时的活跃结点数，TotVert i (Job)表示图迭代作业Job在第i次迭代时的总结点数，N表示抽样执行过程中的总迭代次数；图迭代作业Job包括当前图迭代作业Job run 和历史图迭代作业Job comp ；所述静态消息传递相似度为其中，S 2 表示当前图迭代作业Job run 和历史图迭代作业Job comp 之间的静态消息传递相似度；图迭代作业Job在第i次迭代时传递的消息总量为 其中RemMsg i (Job)表示图迭代作业Job在第i次迭代时传递的消息数量， 表示图迭代作业Job在第i次迭代时的消息平均大小，N表示抽样执行过程中的总迭代数；所述动态相似度计算当前图迭代作业Job run 和历史图迭代作业Job comp 间的动态相似度，包括运行时间相似度S 3 、资源分配相似度S 4 、收敛相似度S 5 以及资源利用相似度S 6 ；所述运行时间相似度S 3 为其中，Step表示作业当前的迭代次数，runtime(Job,i)表示图迭代作业Job在第i次迭代时的运行时间；图迭代作业Job包括当前图迭代作业Job run 和历史图迭代作业Job comp ；所述资源分配相似度为：其中，Step表示作业当前的迭代次数，cons avg (Job,Step)表示图迭代作业Job从开始到当前执行的所有迭代使用的容器数量的平均值；图迭代作业Job包括当前图迭代作业Job run 和历史图迭代作业Job comp ；所述收敛相似度为：其中，workSet(Job,i)代表图迭代作业Job在第i次迭代时主动处理的数据数；所述资源利用相似度为其中，cons是图迭代作业所使用的容器数量；RsUtil job [hw,Step,i]表示图迭代作业执行到第Step次迭代时在容器i中的硬件设备hw的平均利用率。 2.如权利要求1所述的系统，其特征在于，所述相似度评估单元构建的相似度评估函数具体为：平均最优精度函数h(t)和最优相似度占比函数n(t)；h(t):＝avg{acc|(DoS,acc)∈P,DoS≥t}；n(t):＝|{acc|(DoS,acc)∈P,DoS≥t}|/|P|；其中acc为所述运行时间预测系统的预测精度；DoS为两个图迭代作业的整体相似度，为所有单项相似度的加权平均值，所有单项相似度的权重值组成权重向量；t为相似度阈值；P为由一组模拟点(DoS,acc)组成的模拟点集；其中权重向量和相似度阈值即为相似度评估函数的参数。 3.如权利要求2所述的系统，其特征在于，所述训练点收集单元首先对历史图迭代作业集进行n次有序且不重复地抽取，每次从中抽取2个图迭代作业，分别为第一图迭代作业J i 和第二图迭代作业K i ，i＝1,2,3,...,n；抽取的第一图迭代作业J i 正在运行且刚执行完第M∈[1,m i ]次迭代，m i 是图迭代作业J i 的最大迭代次数；抽取的第二图迭代作业K i 是与J i 相匹配的历史作业，基于抽取的2个图迭代作业间的相似度通过运行时间预测模块预测出正在运行的图迭代作业J i 的剩余运行时间，而第一图迭代作业J i 真实的剩余运行时间是已知的，通过使用不同的当前图迭代作业和匹配的历史图迭代作业并假设当前图迭代作业处于不同的迭代次序，则计算得到一系列元素形式为(predict(w),actual)的集合P(w)来作为训练数据点；其中predict(w)是以w作为权重向量后预测出的剩余执行时间，actual是当前图迭代作业的真实剩余执行时间；所述参数训练单元为当前正在运行的图迭代作业找到一个合适的相似度阈值t和一个相似度权重向量w＝(w 1 ,...,w 6 )，使得相似度评估单元中的相似度评估函数h(t)和n(t)的值都大于设定的阈值，以保证当前图迭代作业的匹配结果数量大于设定阈值。 4.如权利要求3所述的系统，其特征在于，所述运行时间预测模块包括单个预测单元和最终预测单元；所述单个预测单元基于匹配的单个历史作业的来对当前图迭代作业的运行时间进行预测，得到一系列单个预测估计值，组成预测时间估计集合并输出至最终预测单元；所述最终预测单元基于预测估计集，通过对预测估计集中的所有估计值进行加权平均合并成一个最终预测值；权重则使用匹配执行时每个历史图迭代作业对应的整体相似度值。 5.基于权利要求1所述系统的一种Gaia系统中面向图迭代作业的运行时间预测方法，其特征在于，预测过程如下：步骤1：获取历史图迭代作业集、初始输入的数据集、待预测图迭代作业及其作业参数和迭代终止条件；步骤2：抽样执行单元对输入数据集进行抽样，抽样比为10％，然后按抽样比对待预测的图迭代作业的收敛参数进行缩放，缩放后对参数进行初始化；步骤3：将待预测图迭代作业的数据源设置为抽样后的样本集，将初始迭代次数设置为0，然后执行该预测图迭代作业，并将每次迭代过程中捕获到的统计信息存储到内存数据库中；步骤4：根据步骤3中捕获的统计信息计算待预测图迭代作业和历史图迭代作业集中每一个作业间的静态相似度；步骤5：重新获取待预测图迭代作业的作业参数以及迭代终止条件，并将参数、静态相似度和动态相似度初始化；将待预测图迭代作业的数据源设置为初始输入的数据集，将迭代次数设置为0；步骤6：迭代次数为0时，则根据步骤4中计算的静态相似度输出与待预测图迭代作业相匹配的历史图迭代作业，然后运行时间预测模块根据匹配出的历史图迭代作业计算出待预测图迭代作业运行时间的静态预测值；步骤7：运行待预测图迭代作业，对输入的数据进行迭代计算，得到待预测图迭代作业和历史图迭代作业集中每一个图迭代作业间的动态相似度；步骤8：作业匹配模块根据步骤4中计算出的静态相似度和步骤7中计算出的动态相似度，输出与待预测图迭代作业相匹配的历史图迭代作业，然后根据匹配出的历史图迭代作业计算出待预测图迭代作业运行时间的动态预测值；步骤9：判断迭代次数或者迭代输出结果是否满足迭代终止条件，如果不满足重复执行步骤7，如果满足则执行步骤10；步骤10：计算不同迭代下对待预测图迭代作业运行时间的预测偏差，预测偏差最小的那个动态预测值即为待预测图迭代作业的运行时间最终预测值。 6.如权利要求5所述的方法，其特征在于，所述步骤7采用如下步骤7.1～步骤7.4执行：步骤7.1：迭代次数加1；步骤7.2：在Gaia集群的每个节点上并行执行迭代步函数，每个节点执行完毕后采用广播的方式将每个节点上进行数据同步，保证不同节点上数据的一致性；步骤7.3：数据同步完成后，将本次迭代过程中捕获的统计信息追加到内存数据库中进行更新；步骤7.4：根据步骤7.3中更新后的统计信息计算待预测图迭代作业和历史图迭代作业集中每一个图迭代作业间的动态相似度。