劉邦鋒臺灣大學:資訊工程學研究所陳惠麟Chen, Hui-LinHui-LinChen2010-06-022018-07-052010-06-022018-07-052008U0001-2208200812540900http://ntur.lib.ntu.edu.tw//handle/246246/184931這篇論文是研究有關獨立工作的配置策略。我們以chunk 的方式來分配大量不知執行時間的工作給多個處理器，而每個chunk 的配置都會有一個固定的通訊成本。配置目的是讓所有工作的總執行時間是最小。我們提出的演算法是結合靜態和動態的排程。以統計分析為基礎，提出了一個技巧來決定有多少比例的工作是作靜態排程。然後在動態的部份，我們使用Kruskal and Weiss所提出一個固定chunk大小來作排程。由大量的實驗得知，其結果是符合我們理論上的預測，同時我們的演算法是優於這篇論文所提出的其他策略。This paper studies the placement strategies of independent tasks. We assign a large number of tasks with unknown execution time to multiple processors in chunks, and each chunk assignment is associated with a fixed communication overhead. The goal is to minimize the total execution time of all tasks. We propose a heuristic algorithm Hybrid that combines static and dynamic scheduling. We present a technique that determines the percentage of tasks that should be scheduled statically, based on statistic analysis. Then we apply a fixed chunk size based on the work of Kruskal and Weiss for the dynamic scheduling part. We conduct extensive experiments and the results are consistent with our theoretical prediction, and our algorithm outperforms other strategies suggested in the literature.Abstract i Introduction 1 Related work 4 System Model 10 Heuristic Algorithm 15.1 Notations 15.2 Static-Workload Ratio 16.2.1 Other Distributions 20.3 Dynamic Chunk Size 20.3.1 Optimal Dynamic Chunk Size 21 Experiment Results 23.1 Experimental Setting 23.1.1 Task Execution Time Distributions 24.2.1 Effect of r for Normal Distribution 25.2.2 Effect of r for Exponential Distribution 27.3 Performance Comparison between Hybrid and PBS 28.3.1 Effect of p for Normal Distribution 28.3.2 Effect of p for Exponential Distribution 30.3.3 Effect of lamda for Normal Distribution 30.3.4 Effect of lamda for Exponential Distribution 34.3.5 Effect of h for Normal Distribution 34.3.6 Effect of h for Exponential Distribution 34 Conclusion 39ibliography 40application/pdf315379 bytesapplication/pdfen-US混合式獨立工作通訊成本靜態工作量比例動態批次工作量大小HybridIndependent TaskCommunication OverheadStatic-Workload RatioDynamic Chunk Sizethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184931/1/ntu-97-R95922002-1.pdf