Distributed Double-Level Workflow Scheduling Algorithms for Grid Computing

Fang-Peng Dong ； Selim G. Akl

《Journal of Information Technology and Applications(資訊科技與應用期刊)》 1卷4期 (2007/03) Pp. 261-273

https://doi.org/10.6302/JITA.200703_1(4).0004

並列摘要

Resources in computational Grids nowadays are usually owned by multiple administrative domains which are connected by WANs. Unlike resource management patterns in traditional parallel and distributed systems, Grid resources usually have their own local management policies and a Grid scheduler cannot control resources beyond its own domain. Additionally, the performance of Grid resources is dynamically changing due to the shared nature of resources in the Grid. In this paper, a novel distributed double-layer scheduling approach for DAG-based Grid workflows is proposed. At the global Grid level, the task graph is partitioned according to the status of selected available resource clusters by an algorithm called AWS. At the resource cluster level, the PFAS algorithm is used to map tasks to resources within a resource cluster. The contributions of our approach lie in: 1) It does not require detailed status information or control privilege on every Grid resource for Grid schedulers at the global Grid level, so that the dependence on Grid information services is reduced and, at the same time, the higher priority of local resource management policies is respected. 2) It is the first static DAG scheduling algorithm taking the resource performance fluctuation into account explicitly to our knowledge.

並列關鍵字

Scheduling ； Grid Computing ； DAG ； Workflow ； Graph Partition ； List Heuristic