網格運算系統之資源配置最佳化設計

Optimal Design of Resource Allocation in Grid Computing System

林晉安(Chin-an Lin)

指導教授 ： 洪士程

朝陽科技大學/資訊學院/資訊工程系/碩士(2011年)

摘要

在本篇文章中，我們提出以序優化(OO)為基礎的演算法解決網格運算系統的資源配置最佳化問題，使服務可靠度達到最大化。首先提出一個近似模型在一個合理的時間內計算出資源配置的服務可靠度。接著利用所提出的演算法來解決資源配置最佳化問題。以序優化為基礎的演算法分為兩階段，在第一階段使用基因演算法(GA)搭配近似模型來評估適應值並且選擇足夠好的解之子集合。然後在第二階段使用更精緻的近似模型進行目標搜索找出一個足夠好的解。本研究以一個16節點為架構的網格運算系統作為模擬與測試範例，包含二個資源管理節點以及25條連結，所獲得足夠好的解在品質以及計算效能方面都有出色的表現。而利用Pentium IV電腦進行模擬，所提出的演算法僅花費2.35分鐘就可獲得足夠好的資源配置。

關鍵字

基因演算法 ； 序優化 ； 網格運算系統 ； 服務可靠度 ； 資源配置

並列摘要

In this paper, we propose an ordinal optimization (OO) based algorithm for solving the resource allocation optimization problem of grid computing system to maximize the service reliability. An approximate model is firstly proposed to estimate the service reliability of a resource allocation design within a tolerable computation time. Next, we employ the proposed algorithm to solve the resource allocation optimization problem. The OO based algorithm consists of two stages. Genetic algorithm (GA) is employed in the first stage using the approximate model for fitness evaluation and selects a subset of good enough solutions. Then, we proceed with the goal softening searching procedure in the second stage using more refined approximate models to search for a good enough solution. We have demonstrated the test results by simulating on an 16-node and 25-link grid computing system including one resource-managing node. The good enough solution obtained by the proposed algorithm is promising in the aspects of solution quality and computational efficiency. In addition, the proposed algorithm spends only 2.35 minutes in a Pentium IV PC to obtain the good enough resource allocation design.

並列關鍵字

grid computing system ； ordinal optimization ； genetic algorithm ； service reliability ； resource allocation

參考文獻

[1] I. Foster, C. Kesselman and S. Tuecke, “The anatomy of the grid: enabling scalable virtual organizations,” Int J High Perform Comput Appl, 2001, pp. 200-222.

[2] S.- K. Das, D.J. Harvey and R. Biswas, “MinEX: a latency-tolerant dynamic partitioner for grid computing applications,” Future Generation Computer Systems, 2002, Vol. 18, No. 4, pp. 477-489.

[4] I. Foster, C. Kesselman, The Grid 2: Blueprint for a new computing infrastructure, 2nd ed., Morgan Kaufmann, 2003.

[5] Y.- S. Dai, M. Xie, and K.- L. Poh, “Availability modeling and cost optimization for the grid resource management system,” IEEE Trans. Syst. Man Cybern. Part A-Syst. Hum., 2008, Vol. 38, No. 1, pp. 170-179.

[6] J. P. Sweeney and S. P. Ahuja, “Heuristic solutions to resource allocation in grid computing: a natural approach,” J. Supercomput., 2008, Vol. 44, No. 2, pp. 179-198.