網格環境中支援工作流程應用程式之線上即時排程方法

在網格環境中對工作流程應用程式排程是個很大的挑戰，因為這類型的問題是屬於NP-complete。對於這類型問題，現今已經有許多探索式的方法被提出，然而大部份都著重在排程單一個工作流程應用程式。近幾年來，有許多的研究致力於處理並行或線上的工作流程，但在每個工作需要多顆處理器的情況這些研究沒辦法處理，本文中，我們提出了一個OWM方法，OWM對線上工作流程可以有效的做排程。為了解決當工作需要多顆處理器所面臨的問題，我們加入解決這類問題的一些有名方法到OWM中，如：first fit，conservative backfilling，easy backfilling。根據模擬實驗，數據顯示我們所提出的OWM表現的比其他方法還要傑出；而在工作需要多顆處理器的情況下，OWM(FCFS)表現的幾乎和 OWM(conservative)一樣並且OWM(FCFS)表現的比OWM(easy)和OWM(first fit) 還要來的好。

關鍵字

線上工作流程；不循環有向圖；工作圖；工作流程排程；工作排程；異質系統；網格計算；工作配置；資料平行；回填機制

並列摘要

Scheduling workflow applications in a Grid environment is a great challenge, because it is NP-complete problem. Many heuristic methods are presented, but most of them work in the domain of single workflow application. In recent years, there are several heuristic methods presented to deal with concurrent workflows or online workflows, but they do not work with workflows composed of data-parallel tasks. In the thesis, we present an approach for dealing with online workflows, which is named Online Workflow Management (OWM). For dealing with data-parallel problems, well-known approaches, e.g., first fit, conservative backfilling and easy backfilling are added into OWM. The experiments show that OWM outperforms other two methods in various workloads. For workflows composed of data-parallel tasks, the experiments show that OWM(FCFS) is almost equal OWM(conservative), and outperforms OWM(easy) and OWM(first fit).

並列關鍵字

Online Workflows ； DAG ； Task Graph ； Workflow Scheduling ； Task Scheduling ； Heterogeneous Systems ； Grid Computing ； Task Allocation ； Data Parallel Task ； Backfilling

參考文獻

Scheduling and Rescheduling Methods in the GrADS Project”, in Proc. of the

18th International Parallel and Distributed Processing Symposium (IPDPS'04),

pp.199--206, Santa Fe, New Mexico USA, April 2004.

R.F. Freund, “A Comparison of Eleven Static Heuristics for Mapping a Class

2001 , pp. 810-837(28).

國際替代計量

網格環境中支援工作流程應用程式之線上即時排程方法

全文下載

主題瀏覽