透過有效率之叢集Sufferage排程演算法來提升異質雲端環境之系統執行效能

An Efficient Cluster Scheduling Algorithm based on Sufferage Heuristic to Improve the Performance of System in the Heterogeneous Cloud Computing Environment

林仕軒(SHIH-HSUAN LIN)

指導教授 ： 江茂綸

朝陽科技大學/資訊學院/資訊與通訊系/碩士(2016年)

摘要

隨著科技的蓬勃發展，現今的網路應用服務迅速增加。近年來十分熱門的雲端運算將是提供快速服務的一大趨勢，它是一個包含龐大的異質處理單元、記憶體和高速網路的分散式運算環境，並透過網路來為人們提供服務。因此，在各種異質性節點和應用服務下，如何提供最合適及快速的服務，將是排程演算法的一大考驗。
然而，先前學者所提出許多演算法，如Min-Min、Max-Min和Sufferage等，都不適應於異質性雲端運算環境。主要是因為Min-Min及Max-Min只考慮了單一節點能力，而未考慮節點間的負載平衡，進而無法降低任務完成時間，而Sufferage雖然改善了工作負載不均的問題，但仍於任務預估完成時間差距大的情況下，將無法降低任務完成時間。
所以，本研究將針對異質性雲端運算環境，以所提出的ClusterMaxSufferage(CMS)演算法來改善傳統演算法的缺點，進而降低任務完成時間及實現系統之負載平衡，以提昇整體系統之效能及可用性。但因為CMS演算法會優先分配較大的任務，而未考慮其他節點能力，造成任務分配到較差的節點，使任務的完成時間增加。因此我們再提出ClusterMaxSufferage+ (CMS+)來改善先前的演算法之缺點，進而降低任務完成時間及達到系統之負載平衡。

關鍵字

雲端運算 ； Sufferage ； 負載平衡 ； 排程演算法

並列摘要

With the exploded development of technology, the applications of network services increase more and more. Cloud providers need a system to provide quick network service, thus the cloud computing is proposed in recent years. The cloud computing system is consists of a huge number of heterogeneous nodes, memories, high-speed networks, and various application services to provide a lot of service over the Internet for users. However, how to provide the suitable and fast service among a huge heterogeneous service node is an important issue.
Therefore, the previous studies proposes many algorithms, such as Min-min, Max-min, and Sufferage algorithms cannot adapt to existing heterogeneous cloud computing environment. It is because that the Min-min and Max-Min algorithms have high makespan and workload in a high heterogeneous environment. In Sufferage algorithm, the workload of each service node can be improved to achieve load balance of system. But, it cost high makespan in a heterogeneous task environment.
As a result, we proposes a ClusterMaxSufferage (CMS) algorithm base on Sufferage heuristic to improve the performance of system and achieve load balance in a heterogeneous cloud computing environments. However, the a larger tasks will be assigned in CMS algorithm first without estimate the ability of other nodes. Therefore, the task is easy to assign to a poor node to increase the task of completion time. As a result, we proposes ClusterMaxSufferage+ (CMS+) algorithm again to improve the CMS to reduce the task of completion time and the achieve load balance.

並列關鍵字

Cloud Computing ； Sufferage ； Load Balance ； Scheduling Algorithms

參考文獻

[1]T. Amudha and T. T. Dhivyaprabha, “QoS Priority based Scheduling Algorithm and Proposed Framework for Task Scheduling in a Grid Environment,” Proceedings of the 2011 International Conference on Recent Trends in Information Technology (ICRTIT), 2011, pp. 650-655.

[6]H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman, “Heuristics for Scheduling Parameter Sweep Applications in Grid Environment,” Proceedings of the 9th Heterogeneous Computing Workshop (HCW), 2000, pp. 349-363.

[7]S.S. Chauhan and R.C. Joshi, “A Weighted Mean Time Min-Min Max-Min Selective Scheduling Strategy for Independent Tasks on Grid,” 2010 IEEE 2nd International Advance Computing Conference (IACC), 2010, pp. 4-9.

[12]R.L. Grossman, “The Case for Cloud Computing,” IT Professional, Mar. 2009, Vol. 11, No. 2, pp. 23-27.

[13]L. M. Khanli and M. Analoui, “Grid_JQA: A QoS Guided Scheduling Algorithm for Grid Computing,” Proceedings of the Sixth International Symposium on Parallel and Distributed Computing (ISPDC ’07), 2007, pp. 34.