Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/20030
DC FieldValueLanguage
dc.contributor林 偉zh_TW
dc.contributorWoei Linen_US
dc.contributor.author吳星佑zh_TW
dc.contributor.authorWu, Hsing-Youen_US
dc.contributor.other資訊科學與工程學系所zh_TW
dc.date2013en_US
dc.date.accessioned2014-06-06T07:08:16Z-
dc.date.available2014-06-06T07:08:16Z-
dc.identifierU0005-2406201318290600en_US
dc.identifier.citation[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,” http://www.cloudbus.org/cloudsim/ [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, 2004en_US
dc.identifier.urihttp://hdl.handle.net/11455/20030-
dc.description.abstract近年來雲端運算科技快速發展,藉由虛擬化技術,許多應用程式已經轉變成透過網路來提供服務,這些服務也包括了科學運算。企業越是提供更多的雲端服務,資料中心對於工作量的處理將會越來越龐大。如何在較短的時間內完成大量工作成了重要課題,因此我們將探討如何將工作分配給虛擬機器執行來達到最好的效能。 應用程式可以用工作流程(workflow)來表示,通常由多個工作所組成。這些工作間具有資料相依性,意指某些工作必須等待其他工作完成後接收他的資料才能執行。而我們可以透過有效的排程使得這些工作能夠平行處理,藉此縮短整體的執行時間。在序列排程中常見的權重計算方法是向上疊加(Upward Rank),權重會從工作流程的最下方向上疊加計算。雖然這種方式可以簡單的得到排程順序,可是這樣的方式容易導致某些工作不需要太好的資源卻優先被分配。透過疊加的方式也很容易產生分層(level)排程的問題,使得工作依照工作流程的分層去進行排程,降低資源利用度。其他方法像是在工作流程中找出絕對路徑,但是絕對路徑通常只能保證最晚何時可以完成工作。因為具相依性的工作被分配在同個虛擬機器時可以不需要傳輸時間,我們以此創造一個以傳輸時間為主要依據的局部化權重。並利用動態選擇排程工作的方式來打破分層排程情形。透過這樣的方式讓所有工作都能盡可能的分配在較合適的資源,增加資源的利用度並縮短完成時間。 我們創造了局部化權重排程法(Localized Weight Scheduling,LWS)。在模擬實驗結果的數據中和最快完成時間分配法(Heterogeneous Earliest Finish Time,HEFT)相較起來,在10000組工作的實驗當中我們縮短了約120秒左右的時間。也減少了整體虛擬機器的停滯時間,增加了雲端環境中的處理效能。zh_TW
dc.description.abstractIn 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.en_US
dc.description.tableofcontentsAbstract iv 第一章 緒論 1 1.1 簡介 1 1.2 研究動機與目的 1 1.3 論文架構 2 第二章 背景與文獻探討 3 2.1 雲端運算服務 3 2.2 CloudSim 11 2.2.1 Cloudsim簡介 11 2.2.2 CloudSim架構 11 2.3 相依性之工作 14 2.3.1 相依性之工作特性 14 2.3.2 最快完成時間分配法(Earliest Finish Time) 15 2.3.3 相關研究 15 第三章 研究方法與設計 18 3.1 相依性之工作排程 18 3.1.1 相異性之最快完成時間分配法( HEFT ) 19 3.1.2 局部化權重分配法 ( Localized Weight Scheduling ) 21 第四章 實驗結果分析 24 4.1 模擬環境及參數設定 24 4.1.1 模擬環境架構 24 4.1.2 輸入樣本 25 4.2 模擬結果 26 第五章 結論 30 參考文獻 31zh_TW
dc.language.isozh_TWen_US
dc.publisher資訊科學與工程學系所zh_TW
dc.relation.urihttp://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-2406201318290600en_US
dc.subject有相依性之工作zh_TW
dc.subjectdata dependencyen_US
dc.subject工作排程策略zh_TW
dc.subject局部化權重zh_TW
dc.subjecttask schedulingen_US
dc.subjectlocalized weighten_US
dc.title用於虛擬機器配置之局部化權重排程法zh_TW
dc.titleA Virtual-Machine Task Scheduling Method Based on Localized Weight Evaluationen_US
dc.typeThesis and Dissertationzh_TW
Appears in Collections:資訊科學與工程學系所
文件中的檔案:

取得全文請前往華藝線上圖書館



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