標題: Scheduling online mixed-parallel workflows of rigid tasks in heterogeneous multi-cluster environments
作者: Wang, Yi-Rong
Huang, Kuo-Chan
Wang, Feng-Jian
資訊工程學系
Department of Computer Science
關鍵字: Workflow scheduling;Mixed-parallel applications;Heterogeneous multi-cluster environment
公開日期: 七月-2016
摘要: Workflow scheduling on parallel systems has long been known to be a NP-complete problem. As modern grid and cloud computing platforms emerge, it becomes indispensable to schedule mixed-parallel workflows in an online manner in a speed-heterogeneous multi-cluster environment. However, most existing scheduling algorithms were not developed for online mixed-parallel workflows of rigid data parallel tasks and multi-cluster environments, therefore they cannot handle the problem efficiently. In this paper, we propose a scheduling framework, named Mixed-Parallel Online Workflow Scheduling (MOWS), which divides the entire scheduling process into four phases: task prioritizing, waiting queue scheduling, task rearrangement, and task allocation. Based on this framework, we developed four new methods: shortest-workflow-first, priority-based backfilling, preemptive task execution and All-EFT task allocation, for scheduling online mixed-parallel workflows of rigid tasks in speed-heterogeneous multi cluster environments. To evaluate the proposed scheduling methods, we conducted a series of simulation studies and made comparisons with previously proposed approaches in the literature. The experimental results indicate that each of the four proposed methods outperforms existing approaches significantly and all these approaches in MOWS together can achieve more than 20% performance improvement in terms of average turnaround time. (C) 2016 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.future.2016.01.013
http://hdl.handle.net/11536/133729
ISSN: 0167-739X
DOI: 10.1016/j.future.2016.01.013
期刊: FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
Volume: 60
起始頁: 35
結束頁: 47
顯示於類別:期刊論文