Replica Aware Job Scheduling in Grid Environments

我們提出了一個在格網系統中可以善用獨立工作間的檔案分享及資料複本以提昇效能的排程演算法。這個演算法不只會考量系統運算時間的負載平衡，還會考量檔案及資料複本的存放位置。實驗模擬的結果顯示我們的演算法在各種不同大小規模的系統中皆比隨機選擇演算法的效能表現穩定，並且多數的情況下與理論值的相對效能差異在 50% 之內。模擬的結果也顯示我們的演算法在自行生成的系統參數或是實際量測取得的系統參數下都有良好的效能表現。We proposes a heuristic algorithm that explores the advantage of file sharing and replication while executing independent jobs in a grid environment. The proposed scheduling algorithm not only consider execution time load balancing, but also consider the location of data and replica these jobs require. The simulation results indicate that the proposed algorithm is more scalable than a random heuristic algorithm. In addition, in most cases the relative performance of our heuristic algorithm is within 50% of a conservative theoretical lower bound. The simulation results also indicate that the heuristic performs well in our synthesis environment, as well as in real grid system like Taiwan Unigrid.1 Introduction 1 Related Works 4 System Model 7 3.1 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . .7 3.2 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 A Scheduling problem . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Heuristic Algorithm 13 4.1 Evaluation of Completion Time of Jobs . . . . . . . . . . . . . 14 4.1.1 Estimated Finish Time . . . . . . . . . . . . . . . . . . 15 4.2 Job Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Experimental Results 21 5.1 Environment Settings . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Reference Metrics for Comparison . . . . . . . . . . . . . . . . 22 5.2.1 Theoretical Lower Bounds . . . . . . . . . . . . . . . . 22 5.2.2 Random Job Selection . . . . . . . . . . . . . . . . . . 24 5.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 24 5.3.1 Synthetic Simulation Parameters . . . . . . . . . . . . 25 5.3.2 Real Grid Parameters . . . . . . . . . . . . . . . . . . 30 Conclusions and Future Work 33ibliography 3