請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44506
標題: | 格網和叢集環境下考慮資料傳輸頻寬的工作排程 Data-bandwidth-aware Job Scheduling in Grid and Cluster Environments |
作者: | De-Yu Chen 陳德禹 |
指導教授: | 劉邦鋒(Pangfeng Liu) |
關鍵字: | 格網計算,叢集系統,主從式系統,工作排程,資料傳輸,頻寬分配, grid computing,cluster systems,master/worker systems,job scheduling,data transfer,bandwidth allocation, |
出版年 : | 2009 |
學位: | 碩士 |
摘要: | 本篇論文研究在頻寬受限之主從式系統中,如何利用有效的排程方法,使工作的完成時間能最小化。我們假設系統中的工作是互相獨立的。每個工作在開始執行前必須累積足夠的頻寬使用權以下載所需的輸入資料。此外我們假設系統中的主結點可同時送資料給複數個從結點,只要所有結點在任何時間使用的頻寬都沒有超過其頻寬限制。
針對上述排程問題,我們提出了兩個不同的模型。如果資料的傳輸不能被中斷,我們證明了在這個模型下的排程是NP-complete的問題。針對這個問題我們 提出了幾個啟發式演算法並透過實驗來比較其表現。如果資料的傳輸可以被中斷,我們則是提出了一個能有效率找到最佳解的演算法。 This paper introduces techniques in scheduling jobs on a master/workers platform where the bandwidth is shared by all workers. The goal is to minimize the total makespan. The jobs are independent and each job requires a fixed amount of bandwidth to download input data before execution. The master can communicate with multiple workers simultaneously, provided that the bandwidth used by the master and the workers do not exceed their bandwidth limits. We proposed two models for this limited-bandwidth problem. If the data transfer cannot be interrupted, then we prove that the scheduling problem is NP-complete. Nevertheless we propose heuristic algorithms and experimentally test their performance. If the data transfer can be interrupted, we propose an algorithm that produces optimal makespan. The algorithm is based on a binary search on the completion time, and an efficient feasibility verification process for a given completion time. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44506 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 410.97 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。