線性相關工作與非相關工作的探索式排程策略; Heuristic Scheduling Strategies for Linear-Dependent and Independent Tasks

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/48448

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/48448

题名:	線性相關工作與非相關工作的探索式排程策略;Heuristic Scheduling Strategies for Linear-Dependent and Independent Tasks
作者:	張彥然;Yen-jan Chang
贡献者:	資訊工程研究所
关键词:	工作排程;網格計算;探索式方法;工作相依性;Job scheduling;Grid computing;Heuristics;Job dependency.
日期:	2011-07-26
上传时间:	2012-01-05 14:55:04 (UTC+8)
摘要:	由於網際網路的發展和計算機的取得越來越容易，分散式計算已經變成新一代計算機科學上主要的研究領域。分散式計算其中一個主要的動機是期望它能夠整合分散在各地的計算資源並且提供強大的計算服務給使用者。為了達到這樣的目的，在分散式計算系統中一種有效率的排程演算法是不可或缺的一部分。因為最佳化排程已經被證明是屬於NP-Hard，所以這篇論文主要的研究目標是探索式的排程演算法。探索式演算法能避免為了追求最佳解所需的大量運算的時間，而以近似的解來取代最佳解並且省去了大量的計算時間。在這篇論文中我們會先介紹一些常用於排程的探索式的方法，包括優點、缺點以及它們的虛擬碼。然後利用網格模擬器GridSim[1]去模擬在工作間具有線性相依性和不具有相依性的情況下各個探索式的方法的效能表現，並討論其模擬的結果。最後在根據各個探索式方法模擬出來的結果整合出一個混合式的方法。這個混合式的方法可以避免單一探索式的方法在特定情況下所遇到的問題。我們也會去檢驗混合式的方法在job間具有相依性、job間不具有相依性和job間具有隨機的相依性的情況下表現出來的效能。 Thanks to advances in wide-area network technologies and the low cost of computing resources, grid computing came into being an active research area. One motivation of grid computing is to aggregate the power of widely distributed resources, and to provide non-trivial services to the users. To minimize the total completion time (makespan), an efficient grid scheduling mechanism must be used in a grid system to dispatch computing tasks to computing resources effectively. However, it has been proved that the optimal scheduling algorithm is NP-hard. Therefore, many people turn to use heuristic approaches for grid scheduling. In this thesis, we introduce eleven common scheduling heuristics to schedule a combination of linear dependent jobs and independent jobs. Then, we use a grid simulator, namely GridSim[1], to evaluate the performance of these heuristic approaches. According to the simulation results, we propose a novel hybrid heuristic approach that can avoid the drawbacks of the eleven heuristic approaches under different situations. Further simulation results confirm that the proposed hybrid approach is among the best heuristic approaches under most circumstances.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	670	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....