格網和叢集環境下考慮資料傳輸頻寬的工作排程

Data-bandwidth-aware Job Scheduling in Grid and Cluster Environments

陳德禹(De-Yu Chen)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.03321

摘要

本篇論文研究在頻寬受限之主從式系統中，如何利用有效的排程方法，使工作的完成時間能最小化。我們假設系統中的工作是互相獨立的。每個工作在開始執行前必須累積足夠的頻寬使用權以下載所需的輸入資料。此外我們假設系統中的主結點可同時送資料給複數個從結點，只要所有結點在任何時間使用的頻寬都沒有超過其頻寬限制。

針對上述排程問題，我們提出了兩個不同的模型。如果資料的傳輸不能被中斷，我們證明了在這個模型下的排程是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.

並列關鍵字

grid computing ； cluster systems ； master/worker systems ； job scheduling ； data transfer ； bandwidth allocation

參考文獻

[2] BIRN: The Biomedical Informatics Research Network. http://www.nbirn.net/.

[3] B. Hong and V. Prasanna. Distributed adaptive task allocation in heterogeneous

[4] J. D. Ullman. Np-complete scheduling problems. Journal of Computer and System

[5] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of

[6] H. Casanova, G. Obertelli, F. Berman, and R. Wolski. The apples parameter sweep