支援網格計算之高效能適應性預測排程機制

An Efficient Prediction-Based Adaptive Scheduling Scheme for Grid Computing

張鴻源(Hung-Yuan Chang)

指導教授 ： 李良德

大同大學/電機資訊學院/資訊工程學系所/博士(2012年)

摘要

多核心處理器和網際網路的技術持續的發展，此新技術的投入使得相關之應用得以在網格計算中實現。
網格計算的實現包含網路服務以及隨處可得且數量龐大的計算資源繫於一個稱做格子的範疇裡。此計算環境能夠很簡單的經由如大量的公用方式而取得計算能力，此方式就如同電力系統對人類社會提供每日所需的電力一般。與此相似的公用系統所成之形式，網格計算運用公開尋求的方式以添加系統環境內無窮盡的計算節點，供應普遍和無處不在的網格基礎設施來解決使用者的應用方案。網格計算亦屬平行與分散式計算的一環，其具有聚集、選擇和分享在地理上屬於分離的自主性計算節點之能力且能夠以適應性的方式去執行使用者所提交的應用問題所要考慮到的環境需求、成本、利用率以及效能之特性。
實際上網格計算的這些關鍵性服務，例如計算資源的尋找、監控與排程本來就很複雜，因為在此環境中所建立起來的計算資源池具有浩瀚性、動態性以及多樣性的特質。故，例如合作工程、資料探索、高效能計算應用…等具有粗顆粒性質的分散式和並行之應用便可於此網格計算內得到益處。因此，網格計算被用來收集廣泛且分離的自主性計算節點之計算能力並為使用者提供有價值性的服務。
為達此概念，網格計算環境內便需要一個高效能的排程器作為其核心成員。網格計算中的排程問題具有動態性質，例如：工作和資源在整個時間軸上皆隨時變化。因此，此排程器其演算法便直接影響到網格計算操作的效能。一種替代方案是為網格計算選擇一個適合的排程演算法來滿足環境內這些工作、節點和網路的特質。以適應性為基礎的排程演算法在網格計算的排程中屬新的趨勢其適合於網格計算的動態環境，於此使用者所提交的應用是根據權重機制考慮其優先順序和分派資源。排程的目地則盡可能達成較高的效能以滿足使用者提交的應用能獲得可用之計算資源。
此博士論文的研究動機是發展更具效率的排程演算法使之成為運用於網格計算環境中的核心，為此提出支援網格計算之高效能適應性預測排程機制。本文所提的機制從邏輯觀點可分為兩個主要部分。一部分為排程系統。此適應性的排程系統用以表示網格節點的效能、工作的負載量以及排程。此排程系統則採納依預測系統提供的準確度並選擇適合的排程策略且能夠適應網格計算環境。另一部分則為預測系統。為提供較精確的預測值，所提出的預測系統會為排程系統選擇一個有較佳預測值的預測器。根據預測系統之準確性，提供適當的排程策略以完成排程任務。本文所提的機制從模擬的實驗結果顯示，此系統能在網格計算環境中提供有效的排程活動。

關鍵字

網格計算 ； 適應性排程 ； 預測資訊

並列摘要

The technologies of multi-core processors and networks have been continuously growing in recent years. It is such a provider that the applications can be operated on Grid.
Grid computing practice includes the internet services and connections of a boundless number of ubiquitous computational resources. The computational scheme can be easiest through of as a massively utility computing power, such as whatever provides energy power to human society for each product every day. In the similar utility style, Grid openly explores and is capable of adding an infinite number of computation nodes and applications resolutions within any pervasive and ubiquitous Grid infrastructure. Grid also is a fashion of parallel and distributed system that possesses the aggregation, selection, and sharing of geographically separateness autonomous computation nodes for adaptive execution relationship to applications requirement, cost, utilization, and performance.
In fact, key services in Grid computing such as resource discovery, monitoring and scheduling are inherently much more complicated in a Grid computing environment where the resource pool is vast, dynamic and architecturally diverse. So, many coarse-grained distributed and parallel applications can gain benefit from the Grid infrastructure, such as collaborative engineering, data exploration, high-performance computing, etc. Therefore, Grid is used to collect the power of widely separateness autonomous computational nodes, so as to provide valuable services to users.
An efficient Grid scheduling system is an essential nucleus in Grid environment in achieving said motion. The scheduling problems in Grid are dynamic as the jobs and resources in this environment vary over time. Hence, the scheduling system is the key issue of Grid computing, and the associated algorithm has a direct effect on the performance of the Grid operation. An alternative is to choose an appropriate scheduling algorithm to be used in a given Grid environment subject to the characteristics of the jobs, nodes and networks. The Adaptive feature based scheduling algorithms is a new trend in Grid scheduling which are applicable in dynamic Grid environments, and the submitting jobs is ordered and dispatched according to a priority methodology. The goal of scheduling is to achieve a highest possible throughput and to satisfy the application requirement equipped with the available computing resources.
In this dissertation, the motivation from the survey is utilized to develop a more efficient scheduling algorithm where a nucleus in Grid computing environment plays the initial role, an efficient prediction-based adaptive scheduling scheme for Grid computing is then proposed. The scheme can logically be divided into two mainly phases. The one hand is scheduling system. The adaptive scheduling system is adopted to represent the performance of Grid nodes, the task workloads, and the schedules. The scheduling strategy dose adopt dependent on accuracy of the prediction system and can adapt to the Grid computing environment. The other hand is prediction system. In order to provide higher accuracy, the prediction system selects a good predictor for the scheduling system. According to the accuracy of the proposed prediction system, the system selects a proper strategy so as to schedule tasks. The scheme can be used with a suitable scheduling algorithm that needs the prediction information if necessary. The experimental results of the simulation show that the proposed scheme is able to perform scheduling well in the Grid computing.

並列關鍵字

adaptive scheduling ； prediction information ； Grid computing

參考文獻

[2] J. Anderson, V. Bud, and U. C. Devi, “An edf-based scheduling algorithm for multiprocessor soft real-time systems,” Proceedings of 17th Euromicro Conference on Real-Time Systems 2005 (ECRTS '05), Jul. 6-8, 2005, Pages 199-208.

[3] A. K. Aggarwal and R. D. Kent, “An Adaptive Generalized Scheduling system for Grid Applications,” 19th International Symposium on High Performance Computing Systems and Applications, 2005 (HPCS '05), May 15-18, 2005, Pages 188-194.

[6] M. Baker, R. Buyya and D. Laforenza, “Grids and Grid technologies for wide-area Distributed Computing,” Journal of Software: Practice and Experience, vol. 32, issue 15, Dec., 2002, Pages 1437-1466.

[8] J. M. Banus, A. Arenas and J. Labarta, “Dual Priority Algorithm to Schedule Real-Time Tasks in a Shared Memory Multiprocessor,” Proceedings of International Parallel and Distributed Processing Symposium 2003, Apr. 22-26, 2003, Pages 2-12.

[9] E. Bini and G. C. Buttazzo, “Schedulability analysis of periodic fixed priority systems,” IEEE Transactions on Computers, vol. 53, issue 11, Nov., 2004, Pages 1462-1473.