雲端計算中工作序列的虛擬機器排程方法

Virtual Machine Scheduling for Job Sequences in Cloud Computing

許詠慶(Yung-Ching Hsu)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.00174

摘要

這篇論文指出資料中心在能源保存上的重要議題。我們探討如何將伺服器分配給工作序列並且減少總能源消耗，在此我們使用效能評比標準為“浪費能源” – 伺服器額外供應給工作的計算資源超出實際工作需求的部分。我們提出了三種工作序列資源佈署策略，分別為最大機器優先方法、最佳符合方法和混合方法。我們並證明出最大機器優先方法與混合方法擁有效能保證，最多只會造成 2/n 浪費能源比值。換句話說，額外浪費能源與實際供應能源比值不會超過 2(1 + δ)/n，n 為工作序列中工作數目，而 1 + δ 為工作序列中工作最大執行時間與最小執行時間的比值。當δ 任意大時，我們也對浪費能源推導出一個精確界限 1/2 。最後我們藉由實驗去比較這三種方法在實際應用上的效能，實驗結果顯示出這三種方法都浪費相當少能源。混合方法優於最佳符合方法，且最佳符合方法優於最大機器優先方法。

關鍵字

雲端計算 ； 能源保存 ； 工作序列排程

並列摘要

This paper describes the important issue of energy conservation for data centers. We consider the problem of provisioning physical servers to a sequence of jobs, and reducing the total energy consumption. The performance metric is the wasted energy – the over-provisioned computing power provided by the physical servers, but exceeding the requirement of the jobs. We propose three new strategies for allocating servers to a sequence of jobs – a largest machine first heuristic, a best fit method, and a mixed method. We prove that both the largest machine first heuristic and the
mixed method will only incur at most 2/n in over-provisioned energy. That is, the ratio between the over-provisioned energy and the total provisioned energy is bounded by 2(1 + δ)/n, where n is the number of jobs, and 1+δ is the ratio between the maximum and minimum execution time of jobs. We also derive a tight bound of 1/2 on the ratio of wasted energy if the ratio δ could be arbitrarily large. We also conduct experiments to compare the three algorithms in practice. The experiment results indicate that all three algorithms waste very little energy in over-provision. The mixed method outperforms the best fit method, which outperforms the largest machine first method.

並列關鍵字

Cloud computing ； Energy conservation ； Job sequence scheduling

參考文獻

[3] Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.

[5] Bo Li, Jianxin Li, Jinpeng Huai, Tianyu Wo, Qin Li, and Liang Zhong. Enacloud: An energy-saving application live placement approach for cloud computing environments. In

[10] Jiayin Li, Meikang Qiu, Jianwei Niu, Yu Chen, and Zhong Ming. Adaptive resource allocation for preemptable jobs in cloud systems. In ISDA, pages 31–36, 2010.

CLOUD ’10, pages 418–425, Washington, DC, USA, 2010. IEEE Computer Society.

[1] Amazon ec2. http://aws.amazon.com/ec2/.