Please use this identifier to cite or link to this item:
標題: 以基因演算法增進回填排程法的效能
Performance Enhancement of Backfilling Scheduling Methods Using Genetic Algorithm
作者: 江嘉峻
Chiang, Chia-Chun
關鍵字: 服務品質;quality of service (Qos);工作排程;回填排程;基因演算法;雲端運算;Task Scheduler;backfill scheduling;genetic algorithms;cloud computing
出版社: 資訊網路多媒體研究所
引用: [1] S. Sadhasivam, N. Nagaveni, R. Jeyarani and R. V. Ram, “Design and implementation of two level scheduler for cloud computing environment,” International Conference on Advances in Recent Technologies in Communication and Computing, pp. 884-886, 2009. [2] S.Selvarani and G. S. Sadhasivam , “Improved cost-based algorithm for task scheduling in cloud computing,” International Conference on Computational Intelligence and Computing Research (ICCIC), pp. 1-5, 2010. [3] S. Srinivasan, R. Kettimuthu, V. Subramani and P. Sadayappan , “Characterization of backfilling strategies for parallel job scheduling,” IEEE International Conference on Parallel Processing Workshops, pp. 514-519, 2002. [4] Z. Yanyong, H. Franke, J. Moreira and A. Sivasubramaniam, “An integrated approach to parallel scheduling using gang-scheduling, backfilling, and migration,” IEEE Transactions on Parallel and Distributed Systems, Vol. 14, no. 3, pp. 236-247, 2003. [5] M. Srinivas and L. M. Patnaik, “Genetic algorithms: a survey,” IEEE Computer, Vol.27, no. 6, pp.17-26, 1994. [6] T. Ibaraki and N. Katoh, Resource Allocation -Algorithmic Approaches. The MIT Press, 1988. [7] K. Li, G. Xu, G. Zhao, Y. Dong and D. Wang, “Cloud task scheduling based on load balancing ant colony optimization,” Chinagrid Conference, pp.3-9, 2011. [8] R. N. Calheiros, R. Ranjan, A. Beloglazov and C. A. F. De Rose, R. Buyya, “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” The Journal of Concurrency and Computation: Practice and Experience, Vol. 41, no. 1, pp. 23-50, 2011. [9] “CloudSim Simulator,” [10] R. Buyya and M. Murshed, “Gridsim: A toolkit for the modeling and simulation of distributed management and scheduling for grid computing,” The Journal of Concurrency and Computation: Practice and Experience, Vol. 14, pp. 13-15, 2002. [11] D. Kliazovich, P. Bouvry, Y. Audzevich and S. U. Khan, “GreenCloud: a packet-level simulator of energy-aware cloud computing data centers,” Global Telecommunications Conference (GLOBECOM 2010), pp.1-5, 2010. [12] “Greencloud - The green cloud simulator,” [13] A. Suresh and P. Vijayakarthick , “Improving scheduling of backfill algorithms using balanced spiral method for cloud metascheduler,” International Conference on Recent Trends in Information Technology (ICRTIT), pp. 624-627, 2011. [14] N. Ye, X. Li, T. Fraely and X. Xu, “Job scheduling methods for reducing waiting time variance,” The Journal of Computer & Operation Research, Vol. 34, pp. 3069-3083, 2007. [15] N. G. Hall and W. Kubiak, “Proof of a conjecture of Schrage about the completion time variance problem,” Operations Research Letter, Vol. 10, Issue 8, pp. 467-472, 1991. [16] D. Tsafrir, Y. Etsion and D. G. Feitelson , “Backfilling using system-generated predictions rather than user runtime estimates,” IEEE Transactions on Parallel and Distributed Systems, Vol.18, no.6, June 2007. [17] L. He, S. A. Jarvis, D. P. Spooner, X. Chen and G. R. Nudd,“Dynamic scheduling of parallel jobs with QoS demand in multi-clusters and grids,” Proceedings of the fifth IEEE/ACM international workshop on Grid Computing, 2004. [18] G. R. Nudd, D. J. Kerbyson, E. Papaefstathiou, J. S. Harper, S. C. Perry and D. V. Wilcox, “PACE: A Toolset for the Performance Prediction of Parallel and Distributed Systems,” International Journal of High Performance Computing Applications, Vol. 14, Issue 3, pp. 228-251, 2000. [19] S. K. Garg and R. Buyya, “NetworkCloudSim: Modelling parallel applications in cloud simulations,” IEEE International Conference on Utility and Cloud Computing (UCC), pp. 105-113, 2011.
近年來由於基礎網設備發展地更加完備與成熟,再加上綠色IT、節能省碳的觀念興起,「雲端運算」成為未來的發展主流已不再受質疑了。各種改善雲端網路效能的研究開始快速發展,包含雲端環境下的工作排程、虛擬機器的管理、能源消耗等等議題開始被大量地討論。而本論文的主旨為研究並改進該種網路環境下,工作排程這部分可以如何加強,以達到效率更加優良,服務品質更加完善的目的。我們主要評估效能的參數為總花費時間(Completion time)、平均等待時間(Average waiting time)。

透過模擬結果顯示,我們所提出的方法確實能有效地解決回填法在過程中容易產生因執行順序而導致使用率低落的缺點,因而降低大量的執行時間。本篇論文中,我們將以CloudSim這套雲端網路模擬器作為實驗平台,用基因演算法(GA, Genetic Algorithm)與BS(Balanced Spiral)這兩種方法來重新排列送到meta-scheduler上的工作序列,以改善回填法(Backfilling Scheduling)的效能,提升整體的使用率。然而,我們由實驗過程中觀察出:當工作長度彼此間有一定程度上的差異時,作回填排程時才會容易產生空缺(gap)的情形,而我們所作的調整序列的方法才能有效地發揮其功效。舉例來說,在動態產生5000個不同長度工作的實驗中,相較於只使用BS的回填法,我們的方法將可以再減少約8%的執行時間。

As the underlying network equipments become complete and mature, cloud computing has become the future mainstream of development toward the goal of green IT, energy saving and carbon reduction. A variety of research efforts have been devoted to the performance improvement of the cloud networks. Major issues under study in the cloud environment include task scheduling, virtual machine management, and energy consumption. In this thesis, we focus on scheduling tasks in the cloud network environment. We propose a backfilling-based scheduling method for achieving efficient and quality task scheduling. Our method features the use of the genetic algorithm with balanced spiral for scheduling the tasks. The main idea behind our research effort is to rearrange a sequence of tasks with the aid of the genetic algorithm with balanced spiral. We aim at improving the performance of the backfilling scheduler so that the completion time and the average waiting time of a given task sequence are minimized.
We choose the cloud network simulator – CloudSim - as an experimental platform for verification. The simulation results show that our proposed method considerably improves utilization, when compared with the basic backfill algorithm. This leads to a significant reduction in the completion time and the average waiting time for a given task sequence, especially when these tasks have drastically different lengths. For example, in a case of 5000 tasks with various lengths, the proposed method achieves an 8% reduction in completion time. Through the simulation, we also find two major factors that can influence the task completion time: fixed or variable task length, and ascending or descending task sequence.
其他識別: U0005-1207201208403700
Appears in Collections:資訊網路與多媒體研究所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.