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

SCIENTIFIC WORKFLOW SCHEDULING ALGORITHM BASED ON MULTIPLE CONSTRAINTS GRAPH DIVISION MECHANISM

为了解决数据密集型环境下的科学工作流应用调度问题,提出一种基于多约束图分割的工作流调度算法。解决标准图分割方法中顶点维度单一而无法反映任务并行性的问题;设计多维度的顶点权重矢量机制,通过有向边的修剪,在所有维度上实现权重和的均衡;得到最小化的任务间数据传输量,降低通信代价。以Montage工作流结构为例进行仿真实验,结果表明,该算法仅以较小的图分割时间代价使得工作流调度过程中的访问量降低了14%,调度时间降低了31%。

To solve the scientific workflow application scheduling problem in data-intensive environment,this paper proposed a workflow scheduling algorithm based on multiple constraints graph divison.Our algorithm solved the problem that the standard graph partitioning only had a single vertex dimension and could not response tasks parallelism.We designed a vertex weight vector mechanism with multi-dimension to achieve the balance of the weight sum in all dimensions.The we got the minimum amount of data transmission between tasks to reduce the communication costs.Taking Montage workflow structure as an example,we carried out simulation experiments.The results show that our algorithm can reduce the data access about 14% with the cost of the small graph partitioning time in the workflow scheduling and reduce about 31% of the scheduling time.