Paper Info
Title
Workflow Scheduling to Minimize Data Movement Using Multi-constraint Graph Partitioning
Abstract
Among scheduling algorithms of scientific workflows, the graph partitioning is a technique to minimize data transfer between nodes or clusters. However, when the graph partitioning is simply applied to a complex workflow DAG, tasks in each parallel phase are not always evenly assigned to computation nodes since the graph partitioning algorithm is not aware of edge directions that represent task dependencies. Thus, we propose a new method of task assignment based on Multi-Constraint Graph Partitioning. This method relates the dimension of weight vectors to the rank of a task phase defined by traversing the task graph. Our algorithm is implemented in the Pwrake workflow system and evaluated the performance of the Montage workflow using a computer cluster. The result shows that the file size accessed from remote nodes is reduced from 88% to 14% of the total file size accessed during the workflow and that the elapsed time is reduced by 31%.
Year
DOI
Venue
2012
10.1109/CCGrid.2012.134
CCGrid
Keywords
Field
DocType
task dependency,file size,montage workflow,complex workflow,task graph,graph partitioning,multi-constraint graph partitioning,minimize data movement,new method,task phase,task assignment,pwrake workflow system,scheduling algorithm,task analysis,vectors,scheduling,computer cluster,directed acyclic graph,directed graphs,data transfer
Graph database,Computer science,Constraint graph,Parallel computing,Directed graph,Real-time computing,File size,Graph bandwidth,Graph partition,Random geometric graph,Workflow,Distributed computing
Conference
Citations 
PageRank 
References 
26
1.01
14
Authors
2
Name
Order
Citations
PageRank
Masahiro Tanaka1567.00
Osamu Tatebe230942.94