Please use this identifier to cite or link to this item:
標題: 用於虛擬機器配置之局部化權重排程法
A Virtual-Machine Task Scheduling Method Based on Localized Weight Evaluation
作者: 吳星佑
Wu, Hsing-You
關鍵字: 有相依性之工作;data dependency;工作排程策略;局部化權重;task scheduling;localized weight
出版社: 資訊科學與工程學系所
引用: [1] H. Topcuoglu, S. Hariri and M. Y. Wu,” Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, no. 3,March 2002 [2] E. Deelman, G. Singh, M. Livny, B. Berriman and J. Good,” The Cost of Doing Science on the Cloud: The Montage Example,” SC ’08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing Article, No. 50, 2008 [3] S. Pandey, L. Wu, S. M. Guru and R. Buyya,” A Particle Swarm  Optimization-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments,” IEEE International Conference on Advanced Information Networking and Applications, 2010 [4] Y. Kwok and I. Ahmad, ”Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Transactions on Parallel and Distributed Systems, Vol. 7, no. 5, pp. 506-521, May 1996 [5] J. Hu, J. Gu, G. Sun and T. Zhao,” A Scheduling Strategy on Load Balancing of Virtual Machine Resources in Cloud Computing Environment,” 3rd International Symposium on Parallel Architectures, Algorithms and Programming, 2010 [6] S. Pandey and R. Buyya,” Cloudbus Workflow Management System as a Platform-as-a-Service for Cloud Computing,” Cloud Slam, 2010 [7]  R. N. Calheiros1, R. Ranjan, A. Beloglazov and C. A. F. De Rose and 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 [8] H. M. Fard and H. Deldari,” An Economic Approach for Scheduling Dependent Tasks in Grid Computing,” The 11th IEEE International Conference on Computational, 2008 [9]  “CloudSim Simulator,” [10] D.I. G. Amalarethinam and F. K. M. Selvi,” A Minimum Makespan Grid Workflow Scheduling Algorithm,” 2012 International Conference on Computer Communication and Informatics, Jan 2012 [11] K. Li, G. Xu, G. Zhao, Y. Dong and D. Wang,” Cloud Task Scheduling Based on Load Balancing Ant Colony Optimization,” Paper presented at the Chinagrid Conference (ChinaGrid), Sixth Annual, 2011 [12] B. Kruatrachue and T.G. Lewis,” Grain Size Determination for Parallel Processing,” IEEE Software, pp. 23-32, Jan 1988 [13] S. Jha, D. S. Katz, A. Luckow, A. Merzky, and K. Stamou,” Understanding Scientific Applications for Cloud Environments,” in Cloud Computing:Principles and Paradigms, R. Buyya, J. Broberg and A. M. Goscinski, 2011, pp. 350-359 [14] C. Vecchiola, X. Chu, and R. Buyya,” Aneka:A Software Platform for .NET-based Cloud Computing,” Proceedings of High Performance Computing Workshop, pp. 267-295, 2008 [15] Z. Li, L. Wang, S. Ren, and G. Quan,” Temperature, Power, and Makespan Aware Dependent Task Scheduling for DataCenters,” 2011 IEEE/ACM International Conference on Green Computing and Communications, 2011 [16] E. Barrett, E. Howley, and J. Duggan,” A Learning Architecture for Scheduling Workflow Applications in the Cloud,” 2011 Ninth IEEE European Conference on Web Services, 2011 [17] M. Wang, K. Ramamohanarao, and J. Chen,” Dependency-based Risk Evaluation for RobustWorkflow Scheduling,” 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, 2012 [18] C. Lin, and S. Lu,” Scheduling ScientificWorkflows Elastically for Cloud Computing,” 2011 IEEE 4th International Conference on Cloud Computing, 2011 [19] F. Pop, and V. Cristea,” Intelligent Strategies for DAG Scheduling Optimization in Grid Environments,” Proceedings of the 16th International Conference on Control Systems and Computer Science, pp. 98-103, May 22-25, Bucharest, Romania, 2007 [20] X. Tang, K. Li, G. Liao, and R. Li,” List Scheduling with Duplication for Heterogeneous Computing Systems,” Journal of Parallel and Distributed Computing, Vol 70, pp. 323-329, April 2010 [21] T. Hagras, and J. Janecek,”A High Performance, Low Complexity Algorithm for Compile-time Task Scheduling in Heterogeneous Systems,” Parallel Computing, pp. 653–670, 2005 [22] G.Q. Liu, K.L. Poh, and M. Xie,” Iterative List Scheduling for Heterogeneous Computing,” Journal of Parallel and Distributed Computing, pp. 654-665, 2005 [23] O. Sinnen, and L. Sousa,” List Scheduling: Extension for Contention Awareness and Evaluation of Node Priorities for Heterogeneous Cluster Architectures,” Parallel Computing, pp. 81–101, 2004 [24] Z. Shia, and J. J. Dongarraa,” Scheduling Workflow Applications on Processors with Different Capabilities,” Future Generation Computer Systems 22, pp. 665–675, 2006 [25] L. F. Bittencourt, R. Sakellariou, and E. R. M. Madeira,” DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm,” 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, 2010 [26] E. Ilavarasan, P. Thambidurai, and R. Mahilmannan,” Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System,” Proceedings of the 4th International Symposium on Parallel and Distributed Computing, 2005 [27] J. Decker, and J. Schneider,” Heuristic Scheduling of Grid Workflows Supporting Co-Allocation and Advance Reservation,” 7th IEEE International Symposium on Cluster Computing and the Grid, 2007 [28] H. Zhao and R. Sakellariou,” An Experimental Investigation into The Rank Function of The Heterogeneous Earliest Finish Time Scheduling Algorithm,” Euro-Par, 2003 [29] J. Barbosa, C. Morais, R. Nobrega, and A.P. Monteiro,” Static Scheduling of Dependent Parallel Tasks on Heterogeneous Clusters,” Cluster Computing, 2005 [30] D. S. Yang, Y. L. Lu, Z. Liu, and W. M. Zhang,” Research on Algorithms of Task Scheduling,” Proceedings of the Third Intemational Conference on Machine Learning and Cybemetics, 2004

應用程式可以用工作流程(workflow)來表示,通常由多個工作所組成。這些工作間具有資料相依性,意指某些工作必須等待其他工作完成後接收他的資料才能執行。而我們可以透過有效的排程使得這些工作能夠平行處理,藉此縮短整體的執行時間。在序列排程中常見的權重計算方法是向上疊加(Upward Rank),權重會從工作流程的最下方向上疊加計算。雖然這種方式可以簡單的得到排程順序,可是這樣的方式容易導致某些工作不需要太好的資源卻優先被分配。透過疊加的方式也很容易產生分層(level)排程的問題,使得工作依照工作流程的分層去進行排程,降低資源利用度。其他方法像是在工作流程中找出絕對路徑,但是絕對路徑通常只能保證最晚何時可以完成工作。因為具相依性的工作被分配在同個虛擬機器時可以不需要傳輸時間,我們以此創造一個以傳輸時間為主要依據的局部化權重。並利用動態選擇排程工作的方式來打破分層排程情形。透過這樣的方式讓所有工作都能盡可能的分配在較合適的資源,增加資源的利用度並縮短完成時間。

我們創造了局部化權重排程法(Localized Weight Scheduling,LWS)。在模擬實驗結果的數據中和最快完成時間分配法(Heterogeneous Earliest Finish Time,HEFT)相較起來,在10000組工作的實驗當中我們縮短了約120秒左右的時間。也減少了整體虛擬機器的停滯時間,增加了雲端環境中的處理效能。

In recent years, cloud computing technology develops rapidly. Through virtualization, many applications have been provided via internet, including scientific computing. As cloud services provided by enterprise increases, workload that datacenters have to process increases dramatically. So task scheduling becomes an important research issue on processing large workload in a short time period. We focus on how to allocate tasks on virtual machines for performance improvement.
An application can be typically represented by a workflow graph. A workflow graph consists of many tasks. These tasks may have data dependency between each other. This means that some tasks need to wait for data which are produced by other tasks. We intend to design an efficient scheduling method to reduce the completion time of workflow. In level scheduling, priorities of tasks are calculated by accumulating weights level-by-level in a bottom-up fashion, so called upward ranking. Upward ranking allows us to figure out a scheduling order rapidly. However, it leads to indiscriminate allocation, and tasks are assigned on the basis of priority to resource whichever becomes available first. This may result in poor resource utilization. Other methods find critical paths in workflow graphs, and use critical paths for scheduling tasks with the guaranteed finish time. But these methods tend to ignore the communication effect on task finish time.
Here we propose a scheduling method for allocating the resources of virtual machines, called localized weight scheduling and LWS for short. The proposed LWS method features communication minimization and utilization improvement. Our method is based upon an important observation that assigning dependent tasks to the same virtual machine helps reduce the communication cost. The LWS method evaluates weights of tasks with localizing communication in mind. It crosses the boundary of level to choose tasks for dynamical scheduling. In this manner, the proposed method can achieve higher resource utilization with minimized completion time. We evaluate the performance of the LWS method through simulation using CloudSim. Compared with HEFT, the proposed method reduces about 120 seconds in 10000 works. Virtual Machine’s idle time also reduced. We conclude that our LWS method significantly minimizes execution time and improves resource utilization of cloud computing.
其他識別: U0005-2406201318290600
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


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