可調適之網格資源使用預測機制

An Adaptive Scheme for Predicting the Usage of Grid Resources

曹傑(Chieh Tsao)

指導教授 ： 李良德

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

摘要

為了能更有效地管理網格環境資源，以及提供更適當的工作排程，如高效能計算、分享計算資源等等的網格計算應用，都需要預知網格資源的使用狀況。此篇論文提出一預測系統，此系統能用來預測網格環境大部分的系統資訊，無論該資訊的時間序列是否存在重複的模式，此系統都可以持續地提供預測資訊。本預測系統將網格資源資訊進行前處理，並使用一動態週期性偵測器以發現重複的模式，最後再利用這些被偵測出來的模式來產生未來數個預測數值，在重複的模式被發覺之前，本預測系統使用一個簡單的方法提供預測值，此方法祇用到極少的系統資源。本論文提出的模組已利用數個模擬試驗進行測試，模擬結果顯示本預測系統能為網格環境找出不同種類的時間序列模式，並能提供準確的環境資源預測資訊。

關鍵字

網格 ； 預測系統 ； 時間序列

並列摘要

In order to manage the grid resources more effectively and provide a more suitable job scheduling strategy, the prediction information is needed for applications in the grid computing system, such as the high performance computing and sharing computational resources, etc. In this thesis, we propose a prediction system that can predict most information in the grid environment. Whether the repetitive time series pattern of the information exists or not, the proposed system can provide prediction results. We label the environment information in the grid and use the periodicity detector to detect the iterative patterns. The detected patterns can be used to predict several future values. Before the repetitive patterns have been found, a simple scheme that does not require a lot of resource has been used to generate prediction values. A prototype of this model is developed and tested with several test cases. The experimental results of the simulation show that our prediction system is able to capture different kinds of time series patterns and provide accurate prediction for the grid environment.

並列關鍵字

grid ； prediction system ； time series

參考文獻

[3]D. A. Menasc´e, D. Saha, S. C. D. S. Porto, V.A. F. Almeida, and S. K. Tripathi, "Static and Dynamic Processor Scheduling Disciplines in Heterogeneous Parallel Architectures," Journal of Parallel and Distributed Computing, 28:1-18, 1995.

[4]D. Paranhos, W. Cirne, and F. Brasileiro, "Trading Cycles for Information: Using Replication to Schedule Bag-of-tasks Applications on Computational Grids," In International Conference on Parallel and Distributed Computing (Euro-Par), Lecture Notes in Computer Science, volume 2790, pages 169-180, 2003.

[5]M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. Freund, "Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems," In the 8th IEEE Heterogeneous Computing Workshop (HCW'99), pages 30-44, 1999.

[6]H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman, "Heuristics for Scheduling Parameter Sweep Applications in Grid Environments," In 9th Heterogeneous Computing Workshop (HCW), pages 349-363, 2000.

[7]O. H. Ibarra and C. E. Kim, "Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors," Journal of the ACM, 24(2):280-289, 1977.