王勝德臺灣大學：電機工程學研究所許以達Hsu, I-TarI-TarHsu2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/53224網格(Grid)計算的環境中，有動態的工作，以及異質性高的計算節點。這篇論文中，我們提出了一個適應網格計算環境的動態排程方法 most fit task first。在過去，有釵h靜態的排程方法，在已知所有工作資訊的條件下，有著很好的效能。但是在工作動態加入時，我們無法預先知道尚未加入的工作之資訊，雖然這些排程方法可以處理動態加入的工作，但卻無法發揮這些方法的效能，而造成工作執行時間(task execution time)的增長且不穩定。然而，我們的排程方法，在工作動態加入時，仍能保有穩定且不至於過大的工作執行時間。In this thesis, we propose an adaptive and dynamic scheduling method, called most fit task first (MFTF), for a class of computational grids, which are characterized by heterogeneous computing nodes and dynamic task arrivals. Some existing static scheduling methods resume that tasks arrive statically and may not perform well in the case of dynamic task arrivals. Our method can get stable task execution times whether tasks arrive statically or dynamically. We compare the task execution time with other methods to show the performance of our scheduling method.致謝 i 中文摘要 ii 英文摘要 iii 1. INTRODUCTION 1 2. TASK SCHEDULING SYSTEM 3 3. SCHEDULING METHODS OF BOT APPLICATIONS 5 3.1. WORKQUEUE 5 3.2. WORKQUEUE WITH REPLICATION 6 3.3. FASTEST PROCESSOR TO LARGEST TASK FIRST 7 3.4. MOST FIT TASK FIRST 8 3.4.1. MFTF with Fixed Expected Task Execution Time 11 3.4.2. MFTF with Estimated Expected Task Execution Time 12 4. PERFORMANCE EVALUATION 15 4.1. DYNAMICS 15 4.1.1. Difference between static-arrival and dynamic-arrival tasks 16 4.1.2. Different density of dynamic-arrival tasks 21 4.1.3. Different range of arrival time of dynamic-arrival tasks 23 4.2. HETEROGENEITY 24 4.3. Adaptability 31 5. CONCLUSIONS 37 6. FUTURE WORK 39 REFERENCE 41372605 bytesapplication/pdfen-US網格計算Gridthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53224/1/ntu-93-R91921087-1.pdf