應用線上排程於複合平行工作流程之研究

A study to Online Scheduling for Mixed-Parallel Workflow

王乙融(Yi-Rong Wang)

指導教授 ： 王豐堅

國立交通大學/資訊學院/網路工程研究所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.01049

摘要

在平行系統中對工作流程應用程式排程是一個已知的 NP-Complete 問題。當在異質執行速度的多群集環境中排程複合平行工作流程時，問題變得更有挑戰性。現今已有許多演算法被提出，但大多不適合複合平行工作流程與多群集環境，因此他們不能有效地處理排程問題。本文中，我們提出了一個 MOWS 排程框架可以有效的排程複合平行工作流程。MOWS 框架將排程程序分為四個步驟：task prioritizing，waiting queue scheduling，task rearrangement，task allocation。我們並提出了四個新方法套用在 MOWS 框架下：shortest-workflow-first，priority-based backfilling，preemptive task execution，All-EFT task allocation。我們建立了一連串的模擬實驗來評估 MOWS 的效能，實驗數據表示，我們所提出的四個新方法都較先前的方法要傑出。而最後的 MOWS 框架和先前的方法相比效能要進步 16%。

關鍵字

工作流程排程 ； 複合平行應用程式 ； 異質多群集環境

並列摘要

Workflow scheduling on parallel systems has long been known to be a NP-complete problem. The issues become even more challenging when scheduling mixed-parallel workflows in an online manner in a speed-heterogeneous multi-cluster environment, which is indispensable for modern grid and cloud computing applications. However, most existing algorithms were not developed for mixed-parallel workflows and multi-cluster environments, therefore they can’t handle the scheduling issues efficiently. In this thesis, 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. 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 under the MOWS framework. To evaluate the performance of MOWS, we conducted a series of simulation studies and compared it with a previously proposed approach in the literature called OWM. The experimental results indicate that each of the four proposed methods outperforms existing approaches significantly. In average, MOWS can achieve around 16% performance improvement over OWM in terms of average makespan and SLR.

並列關鍵字

workflow scheduling ； mixed-parallel applications ； heterogeneous multi-cluster environments

參考文獻

[1]. M. L. Pinedo, “Scheduling: Theory, Algorithms, and Systems”, Springer Publishing Company, 2008.

[2]. H. Topcuoglu, S. Hariri and M. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing”, IEEE Trans. on Parallel and Distributed Systems, vol. 13, pp. 260-274, 2002.

[3]. L.F. Bittencourt, R. Sakellariou and E.R.M. Madeira, “DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm”, Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, pp.27-34, 2010.

[4]. Y. Kwok and I. Ahmad. “Dynamic Critical-Path Scheduling: An Effective Technique for Allocation Task Graphs to Multi-processors”, IEEE Trans. Parallel and Distributed Systems, vol. 7, pp. 506-521, 1996.

[5]. Z. Yu and W. Shi, “An Adaptive Rescheduling Strategy for Grid Workflow Applications”, Parallel and Distributed Processing Symposium, 2007. IEEE International, pp. 1-8, 2007.