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

本篇論文研究在頻寬受限之主從式系統中，如何利用有效的排程方法，使工作的完成時間能最小化。我們假設系統中的工作是互相獨立的。每個工作在開始執行前必須累積足夠的頻寬使用權以下載所需的輸入資料。此外我們假設系統中的主結點可同時送資料給複數個從結點，只要所有結點在任何時間使用的頻寬都沒有超過其頻寬限制。對上述排程問題，我們提出了兩個不同的模型。如果資料的傳輸不能被中斷，我們證明了在這個模型下的排程是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.e 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.Certification icknowledgement iihinese Abstract iiibstract iv Introduction 1 RelatedWorks 3 System Model 5.1 Jobs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Scheduling with Uninterruptible Communication 9.1 NP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Unlimited Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3 Heuristic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Scheduling with Interruptible Communication 16.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.1.1 Completion Time Guessing . . . . . . . . . . . . . . . . . . . . 16.1.2 Feasibility Verification . . . . . . . . . . . . . . . . . . . . . . . 17 Conclusions 23ibliography 2