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

Abstract

在網格環境中對工作流程應用程式排程是個很大的挑戰，因為這類型的問題 是屬於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).