異質網路及運算資源下之雲端運算問題初步研究

在這篇論文中，我們專注研究於一個較新奇的雲端運算系統，我們稱之為無線隨意計算雲。這是由許多的異質性高的機器透過不同的網路型態組合而成。這篇論文的主要目標就是找到有效率使用這些異質機器的方法。首先，透過許多的量測我們指出這個新系統潛在的問題─這個無線隨意計算雲並不適用傳統的平行運算估計速度的方法。因此，我們提出一個新的評估方式能夠準確評估這些異質性很高的機器。這個評估方法啟發我們設計一套新的分配演算法(HE)，使得我們可以依藉不同的機器的能力有效分配。然而，使用高傳輸量的應用卻會降低這個方法的改進效能。這是歸因於機器彼此競爭網路頻寬，使得原本估測的參數不準確。我們因此提出第二個演算法(MRT)，使用少量多重傳輸能夠有效避免網路競爭的問題。不同於HE，MRT不需要量測網路參數而可去除評估的誤差。本論文將這兩個演算法實作在MPI裡面，並且在我們設定的實作環境中逐步比較這兩者各自的增益。舉一組數據為例，傳統的平行運算因為異質性影響只能得到2.78的加速，而當我們使用HE演算法可以得到4.72的加速，若是用了MRT演算法則可以提升至5.35倍的加速。然而，在網路高度遲緩的狀況下，MRT演算法會因不必要的通訊成本而使效能下滑了16.5%。相較之下，HE演算法有比較高的網路遲緩抵抗性。一般使用者可以根據他們實作的環境，選擇我們提供的這兩個異質環境中改進的演算法。

關鍵字

雲端；異質性；平行運算

並列摘要

In this thesis, we focus on the ad-hoc computing cloud, which consists of a client program running on a set of heterogeneous computers connected through heterogeneous networks. The main goal is to utilize resources from heterogeneous computers efficiently to facilitate cloud computing in the target scenario. We first set up a testbed and discover that the traditional Amdahl's law of speedup does not fit the scenario with heterogeneous computers and networks. Therefore, we introduce heterogeneity score for evaluating heterogeneous machines linked by heterogeneous networks. We then further propose a heterogeneity evaluation (HE) algorithm to distribute appropriate workload based on different abilities of individual machines. However, because the accuracy of measuring the heterogeneous score is limited by bandwidth contention, we further propose the second algorithm, multi-round transmission (MRT) algorithm, to avoid bandwidth contention by transmitting the data in multiple rounds. Unlike HE, MRT does not need to measure variables in advance and hence it can eliminate estimation error in various applications. To evaluate the performance of the proposed algorithms, we implement these two solutions in Message Passing Interface (MPI) framework. We find that both of these algorithms can save considerable completion time. In the target scenario, the traditional approach can achieve a speedup of only 2.78. The proposed HE algorithm, on the other hand, can lift the speedup to 4.72, whereas the MRT algorithm can lift the speedup to 5.35. However, the performance of the MRT algorithm drops 16.5\% due to the unnecessary communication overhead under high latency network, while the HE algorithm shows better resistance to high latency. The two algorithms thus can be appropriately used for different environments and applications under consideration.

並列關鍵字

Cloud Computing ； Heterogeneity ； Parallel Computing

參考文獻

by promoting collaboration in peer-to-peer grids. submitted for publication. hp

labs. Technical report, Journal of Parallel and Distributed Computing, 2005.

G. Girardi. Peer-to-peer desktop grids in the real world: The sharegrid project.

In Cluster Computing and the Grid, 2008. CCGRID ’08. 8th IEEE International

[5] G. Barlas. An analytical approach to optimizing parallel image registration/retrieval.

國際替代計量

異質網路及運算資源下之雲端運算問題初步研究

全文下載

主題瀏覽