一個混合式平行工作流程線上排程架構之研究

Abstract

隨著雲端運算平台以及服務導向架構相關技術的逐漸成熟，工作流程逐漸變成許多現代大型應用軟體系統的底層架構。平行系統中的工作流程排程議題長久以來一直吸引許多研究的目光，因為它屬於NP-complete的問題。而在現今的網格與雲端平台中，由於多叢集與異質性的架構，更使得工作排程的問題變得更為複雜。雖然先前陸續有許多排程方法被提出，但大多不能有效處理混合平行式工作流程及多叢集架構的問題。在此計畫中我們提出了一個混合式平行工作流程線上排程架構，它將整個工作流程程序化分成四個階段，分別是排定工作優先順序、貯列內工作排程、工作執行順序調整、計算資源配置。基於此工作排程架構，我們將在此計畫中依據較小工作流程優先、以優先權為基礎之工作回填、可打斷式工作執行、及最早完成時間優先之資源配置等四項原則來發展一系列新的工作排程機制。我們也將開發一個實驗模擬平台，用來評估這些新方法的效能，並和先前文獻中已發表的方法進行分析比較。

Workflow has become an important underlying structure for modern large scale software applications as the cloud computing platforms and SOA technologies getting mature. 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 project, 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 plan to develop four new mechanisms, according to the shortest-workflow-first, priority-based backfilling, preemptive task execution and All-EFT task allocation respectively, for scheduling online mixed-parallel workflows on multi-cluster cloud platform. To evaluate the performance of MOWS, we plan to develop a simulation environment for conducting a series of simulation studies to compare it with previously proposed approaches in the literature.