1.一种工作流调度方法,其特征在于,包括步骤:
S1、构建工作流有向无环图DAG;其中,DAG=(V,E),V={v1,v2,...,vi}表示工作流中i个计算任务的集合,E={e1,e2,...,ek}表示工作流中k个通信任务的集合,ek=e(i,j)∈E表示一个通信任务,反映计算任务之间的依赖关系;
S2、根据所述工作流有向无环图DAG,采用基于中心点的DAG聚类方法,得到聚类簇集合;具体包括:S21、构建中心点集合C;
S22、初始化所述DAG中的每个节点所对应的簇
S23、遍历所述中心点集合C,在每次遍历中,计算将节点添加到 的阈值Θi,并将中心点所对应的 赋值为该中心点ci,再调用函数clustering进行递归地节点添加,最终得到聚类簇集合;
S3、基于所述聚类簇集合,基于预分配模型,得到每个聚类簇的CPU分配方案;具体包括:S31、计算每个聚类簇 的优先级 基于所述优先级,将所有聚类簇进行降序排序;
S32、将每个处理器Pm的已占用时间Ωm初始化为0;
S33、对每个聚类簇 计算其在任意处理器Pr上的预估最早完成时间 将其分配到最小化 的处理器并依此更新相应处理器Pm的Ωm;
S4、根据所述工作流有向无环图DAG以及每个聚类簇的CPU分配方案,基于虚拟最早结束时间的调度模型,得到最终的工作流调度方案;具体包括:S41、生成一个按照任务优先级rank非递增排序的任务列表S42、将所有资源的可用时间初始化为0;
S43、在每次迭代中,从所述任务列表中选择第一个任务节点进行调度,并同步调度其前驱通信任务,当该任务节点调度完成时,将其从任务列表中删除;
每次迭代的步骤为:为任务vi生成一个包含其所有直接前驱通信任务的优先级列表并按照rank进行非递增排序;如果当前节点已经被预分配,则更新预留时间τm,否则,将vi临时分配到每个处理器Pr∈P上;
对于每次这样的临时分配,同时将每个前驱通信任务ek按照优先级临时分配到总线Bk∈B,使得通信任务ek的完成时间t.(ek)最小;
基于这些通信任务的分配结果,计算所有处理器Pm上的虚拟最早结束时间vi被实际分配到使其 最小的处理器上;
在vi的处理器确定后,将其前驱通信任务分配到使通信任务最早结束的总线上,并更新相应总线,以最小化它们的结束时间。
2.根据权利要求1所述的方法,其特征在于,步骤S21中,所述中心点集合C定义如下:其中, 表示vi的相邻边集合,参数α用于调节选择条件的严格程度,B表示总线,P表示处理器,CCR表示计算通信比。
3.根据权利要求1所述的方法,其特征在于,步骤S23中,所述计算将节点添加到 的阈值Θi,具体包括:通过计算 在所有总线上的平均权重,确定将节点加入到 的阈值Θi,Θi的计算方式如下:其中, 表示vi的相邻边集合, 表示ek在总线上的平均权重。
4.根据权利要求1所述的方法,其特征在于,步骤S23中,所述调用函数clustering进行递归地节点添加,最终得到聚类簇集合,具体为:在所述函数clustering中,遍历节点node的所有前驱节点 如果该前驱节点已经被访问过,则跳过该节点;计算节点node和对应前驱的平均边权重 如果其大于阈值Θ,则将该前驱节点pred所对应的 赋值为 随后通过该节点继续递归调用;否则,将该前驱节点所对应的 赋值为‑1,表示该节点不会被聚类到任何一个cluster中;
遍历节点node的所有后继节点 如果该后继节点已经被访问过,则跳过该节点;
计算节点node和对应后继的平均边权重,如果其大于阈值Θ,则将该后继节点succ所对应的 赋值为 随后通过该节点继续递归调用;否则,将该后继节点所对应的 赋值为‑1,表示该节点不会被聚类到任何一个cluster中;
每个节点vi的 属性都已被赋值;具有相同 值属于同一个cluster;若值为‑1,则表示该节点未被分配到任何cluster。
5.根据权利要求1所述的方法,其特征在于,步骤S31中,计算每个聚类簇 的优先级的具体步骤为:首先,OCT(vi,Pm,Bn)计算公式如下:
其中, 表示节点vi的后继节点集合,OCT(vi,Pm,Bn)表示, 表示节点vj分配到处理器Px,并和后继节点的通信通过By进行时,其子节点的最大乐观执行时间, 表示通信任务ei,j在总线Bn上的通信开销;当vi和vj映射到相同的处理器上时,即Pm=Px,则 OCT(vi,Pm,Bn)代表节点vi的子节点的最大的乐观执行时间;
通过平均OCT反应任务的优先程度,每个节点的优先级定义如下:聚类簇 的优先级定义如下:
6.根据权利要求1所述的方法,其特征在于,步骤S33中,最早完成时间 的计算公式如下:其中, 表示节点vj在处理器上的平均权重。
7.根据权利要求1所述的方法,其特征在于,步骤S43中,具体包括:将含有已经得到实际分配节点的聚类簇 中尚未被实际分配的节点集合记为W,假设预分配的处理器为Pm,则处理器Pm所预留时间τm,i通过如下公式进行表示:其中, 表示节点vi在处理器Pm上执行所需的时间;
对于处理器Pm,其总预留时间τm为:
通过引入τm,虚拟最早结束时间 计算公式如下:
其中,t.(vi,Pm)表示节点vi在处理器Pm上执行的实际结束时间。
8.一种工作流调度系统,其特征在于,所述工作流调度系统执行如权利要求1所述的工作流调度方法,包括:工作流DAG构建模块、聚类簇集合生成模块、聚类簇CPU预分配方案生成模块以及工作流调度方案生成模块;
所述工作流DAG构建模块,构建工作流有向无环图DAG;
所述聚类簇集合生成模块,根据所述工作流有向无环图DAG,采用基于中心点的DAG聚类方法,得到聚类簇集合;
所述聚类簇CPU预分配方案生成模块,基于所述聚类簇集合,基于预分配模型,得到每个聚类簇的CPU分配方案;
所述工作流调度方案生成模块,根据所述工作流有向无环图DAG以及每个聚类簇的CPU分配方案,基于虚拟最早结束时间的调度模型,得到最终的工作流调度方案。
9.一种计算机设备,其特征在于,所述设备包括存储器及处理器,所述存储器上存储有计算机程序,所述处理器执行所述计算机程序时实现如权利要求1至7中任一项所述的方法。