基於灰預測之分散式系統的負載平衡機制

A Grey Prediction Based Load Balancing Mechanism for Distributed Computing Systems

陳幸祿(Hsing-Lu Chen)

指導教授 ： 李良德

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

摘要

由於電腦硬體快速發展，使得個人電腦及工作站之性能大幅提昇，加上網際網路普遍架設，且傳輸頻寬快速成長，形成以低價的個人電腦採取平行或分散處理式計算來取代傳統昂貴的超級電腦，降低建立資訊系統所需花費，以及節省因提高資訊系統功能，所需再投入之成本。
把分散的節點結合成一個叢集系統，在一個控制台下控制，並達成平衡負載之要求，有賴代理人程式(中間軟體)的建置和控制。當然代理人程式要具有負載平衡機制，利用灰色理論，就很少的資料(最少4個數據)以得到負載模式，並對負載數據建立灰色模型（GM：Grey Dynamic Model ) 進行灰色預測，依據所預測局部群組內節點負載來做新工作的指派，以防止某節點太忙或太閒，消除系統瓶頸，提高系統效能。本論文所提出之機制Grey dynamic Model - based Load Balancing Mechanism (GMLBM)首先藉GM預測各節點CPU之使用率，嗣後安排到達的工作由預測CPU使用率最低者執行。
本項建議已建立一個模式，模擬實際運作情形，用來評估系統效能，GMLBM建置在代理人處，代理人監控局部群組內各節點負載，並記錄及預測其負載，依據預測負載為最小值的節點做為下一個工作的執行點，實驗分別以灰色理論預測法、輪廻法及外插預測法所得到結果做比較，實驗結果顯示GMLBM比輪廻法及外插預測法得到較好的效能。

關鍵字

灰色理論

並列摘要

For the rapid growth of the hardware technology, personal computers and workstations are more powerful than before. Instead of using the expensive supercomputer, many personal computers can be connected by a high speed network to form a distributed computing system, so as to decrease the cost of building a high performance computing system.
To link all of the disperse nodes to a cluster under one console and achieve load balancing, the setup and control of the agent is of great importance. Of course, the agent has to be provided with a Load Balancing Mechanism (LBM) and a GM (GM: Grey Dynamic Model). It will produce grey prediction for the load data, according to the grey theory, by applying a few data to get the load model for assigning new task according to the load in the predicted group, to avoid the overloading or vacancy of some nodes, eliminate system bottleneck and increase system performance. The grey dynamic model-based Load Balancing Mechanism (GMLBM) proposed in this thesis, first predicts the utilization of each node then distributes the task to the node with the lowest load.
The GMLBM is installed at the agent. The agent detects, records and predicts the load of each node in a local group, and selects the node with lowest load predicted as the node for executing the next task. A simulation has been made to evaluate the performance of the proposed system. By comparing with other load balancing methods, the experimental results show that the method of GMLBM can achieve a better performance than that of round robin and linear extrapolation.

並列關鍵字

GMLBM ； Grey theory

參考文獻

[2] Dazhang Gu, Lin Yang, Lonnie R. Welch, “A Predictive, Decentralized Load Balancing Approach,” Proceedings of 19th IEEE International Symposium on Parallel and Distributed Processing, April 2005 pp. 131b-131b.

[3] Liang-Teh Lee, Der-Fu Tao, Chia-Ying Tseng and Ming-Tsung Wu,” An Extenics-based Load Balancing Mechanism for Distributed Computing Systems,” Proceedings of 2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering, Volume 1, Oct. 2002, pp. 371 – 374.

[6] Fran Berman, Geoffrey Fox, and Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons Inc., Publication, 2003, pp. 70-85.

[7] Sathish S. Vadhiyar, Jack J. Dongarra, “GrADSolve -- a grid-based RPC system for parallel computing with application-level scheduling,” Journal of Parallel and Distributed Computing, Vol. 64, 2004, pp. 774-783.

[8] Kaiquan Shi, Guo-Cheng Wu, and Yo-Ping Huang, Grey Message relational, Chwa books Taiwan inc. Sep 1994, pp.11-21.