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

Abstract

在平行系統中對工作流程應用程式排程是一個已知的 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.