標題: 應用線上排程於複合平行工作流程之研究
A study to Online Scheduling for Mixed-Parallel Workflow
作者: 王乙融
Wang, Yi-Rong
王豐堅
Wang, Feng-Jian
網路工程研究所
關鍵字: 工作流程排程;複合平行應用程式;異質多群集環境;workflow scheduling;mixed-parallel applications;heterogeneous multi-cluster environments
公開日期: 2011
摘要: 在平行系統中對工作流程應用程式排程是一個已知的 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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079856537
http://hdl.handle.net/11536/48416
Appears in Collections:Thesis


Files in This Item:

  1. 653701.pdf