線性相關工作與非相關工作的探索式排程策略

由於網際網路的發展和計算機的取得越來越容易，分散式計算已經變成新一代計算機科學上主要的研究領域。分散式計算其中一個主要的動機是期望它能夠整合分散在各地的計算資源並且提供強大的計算服務給使用者。為了達到這樣的目的，在分散式計算系統中一種有效率的排程演算法是不可或缺的一部分。因為最佳化排程已經被證明是屬於NP-Hard，所以這篇論文主要的研究目標是探索式的排程演算法。探索式演算法能避免為了追求最佳解所需的大量運算的時間，而以近似的解來取代最佳解並且省去了大量的計算時間。在這篇論文中我們會先介紹一些常用於排程的探索式的方法，包括優點、缺點以及它們的虛擬碼。然後利用網格模擬器GridSim[1]去模擬在工作間具有線性相依性和不具有相依性的情況下各個探索式的方法的效能表現，並討論其模擬的結果。最後在根據各個探索式方法模擬出來的結果整合出一個混合式的方法。這個混合式的方法可以避免單一探索式的方法在特定情況下所遇到的問題。我們也會去檢驗混合式的方法在job間具有相依性、job間不具有相依性和job間具有隨機的相依性的情況下表現出來的效能。

關鍵字

工作排程；網格計算；探索式方法；工作相依性

並列摘要

Thanks to advances in wide-area network technologies and the low cost of computing resources, grid computing came into being an active research area. One motivation of grid computing is to aggregate the power of widely distributed resources, and to provide non-trivial services to the users. To minimize the total completion time (makespan), an efficient grid scheduling mechanism must be used in a grid system to dispatch computing tasks to computing resources effectively. However, it has been proved that the optimal scheduling algorithm is NP-hard. Therefore, many people turn to use heuristic approaches for grid scheduling. In this thesis, we introduce eleven common scheduling heuristics to schedule a combination of linear dependent jobs and independent jobs. Then, we use a grid simulator, namely GridSim[1], to evaluate the performance of these heuristic approaches. According to the simulation results, we propose a novel hybrid heuristic approach that can avoid the drawbacks of the eleven heuristic approaches under different situations. Further simulation results confirm that the proposed hybrid approach is among the best heuristic approaches under most circumstances.

並列關鍵字

Job scheduling ； Grid computing ； Heuristics ； Job dependency.

參考文獻

[1] A. Sulistio, U. Cibej, S. Venugopal, B. Robic, and R. Buyya, “A toolkit for modelling and simulating data Grids: an extension to GridSim,” Concurr. Comput. : Pract. Exper., vol. 20, Sep. 2008, pp. 1591–1609.

[2] D. Jewitt., “Project Pan-STARRS and the Outer Solar System.,” Earth, Moon and Planets., 2004.

[5] R. Armstrong, D. Hensgen, and T. Kidd, “The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions,” IN 7TH IEEE HETEROGENEOUS COMPUTING WORKSHOP (HCW ’98, vol. 79, 1998, p. 79--87.

[7] J.D. Ullman, “NP-complete scheduling problems,” Journal of Computer and System Sciences, vol. 10, Jun. 1975, pp. 384–393.

[8] Garey, M. and Johnson, D., “A Guide to the Theory of NP-Completeness,” WH Freeman and Co, New York, 1979.

國際替代計量

線性相關工作與非相關工作的探索式排程策略

未授權

主題瀏覽