Please use this identifier to cite or link to this item:
A Virtual-Machine Task Scheduling Method Based on Localized Weight Evaluation
|關鍵字:||有相依性之工作;data dependency;工作排程策略;局部化權重;task scheduling;localized weight||出版社:||資訊科學與工程學系所||引用:|| 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  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  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  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  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  S. Pandey and R. Buyya,” Cloudbus Workflow Management System as a Platform-as-a-Service for Cloud Computing,” Cloud Slam, 2010  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  H. M. Fard and H. Deldari,” An Economic Approach for Scheduling Dependent Tasks in Grid Computing,” The 11th IEEE International Conference on Computational, 2008  “CloudSim Simulator,” http://www.cloudbus.org/cloudsim/  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  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  B. Kruatrachue and T.G. Lewis,” Grain Size Determination for Parallel Processing,” IEEE Software, pp. 23-32, Jan 1988  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  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  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  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  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  C. Lin, and S. Lu,” Scheduling ScientificWorkflows Elastically for Cloud Computing,” 2011 IEEE 4th International Conference on Cloud Computing, 2011  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  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  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  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  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  Z. Shia, and J. J. Dongarraa,” Scheduling Workflow Applications on Processors with Different Capabilities,” Future Generation Computer Systems 22, pp. 665–675, 2006  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  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  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  H. Zhao and R. Sakellariou,” An Experimental Investigation into The Rank Function of The Heterogeneous Earliest Finish Time Scheduling Algorithm,” Euro-Par, 2003  J. Barbosa, C. Morais, R. Nobrega, and A.P. Monteiro,” Static Scheduling of Dependent Parallel Tasks on Heterogeneous Clusters,” Cluster Computing, 2005  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||摘要:||
我們創造了局部化權重排程法(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.
|Appears in Collections:||資訊科學與工程學系所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.