臺灣博碩士論文加值系統

透過與網際網路相互連接的資源提供了一個新的計算平台，稱之為網格系統，可用來執行大型的分散式平行運算的應用程式。在網格系統中，其特性大多與一般的異質運算環境相同，但是其傳送率則通常是浮動的。由於這個主要的差異，使得以前已提出的一些演算法必須做一些修改，以期得到較好的效能。在本論文中，我們提出一個動態排程演算法，該演算法先將排程的結果存放在多重的佇列中，於執行期時，再逐一將佇列中的工作分配給對應的處理器，並做各處理器間傳輸率的預測，當傳輸率的變動超過門檻值時，則重新排程，以期得到較好的效能。實驗結果顯示，在變動傳輸率且各處理器間的頻寛差異較大的環境中，我們所提出的動態排程演算法有相當好的效能表現。

Diverse sets of resources interconnected with Internet provide a new computing platform, called the grid computing system, which can support execution of computationally intensive parallel and distributed applications. The main characteristics of grid computing system are similar to the heterogeneous computing system except the fluctuant transfer rate. For this major difference, the existing algorithms for supporting heterogeneous processors have to make some modifications in order to achieve a better performance of entire system. A dynamic scheduling algorithm, called Dynamic HEFT (DH) algorithm is proposed in this thesis to enhance the functions of the original static HEFT (SH) algorithm. Instead of dispatching tasks to physical processors directly, the DH algorithm dispatches tasks to multiple queues. During runtime, the DH algorithm continues to dispatch the scheduled tasks to corresponding physical processor and predicts the transfer rate. Once the difference between two consecutive transfer rates is greater than the threshold value, rescheduling will be performed. The experimental results show that the proposed DH algorithm performs better than the SH algorithm in the system, especially under the grid computing environment, with fluctuant transfer rate and high bandwidth differences.

ACKNOWLEDGEMENT III
ABSTRACT IV
中文摘要 V
TABLE OF CONTENTS VI
LIST OF FIGURES VII
LIST OF TABLES VIII
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 RELATED WORKS 3
2.1 SCHEDULING SYSTEM MODEL 3
2.2 CLASSIFICATION OF STATIC TASK-SCHEDULING ALGORITHMS 7
2.3 THE HETEROGENEOUS-EARLIEST-FINISH-TIME (HEFT) ALGORITHM 9
CHAPTER 3 THE PROPOSED ALGORITHM 14
3.1 NOTATION OF ATTRIBUTES 15
3.2 THE DYNAMIC HEFT (DH) ALGORITHM 18
CHAPTER 4 EXPERIMENTAL RESULTS 23
4.1 COMPARISON METRICS 23
4.2 SIMULATION MODEL 24
4.3 COMPARISON OF RESULTS 26
CHAPTER 5 CONCLUSIONS AND FUTURE WORKS 31
REFERENCES 32

[1]B. Kruatrachue and T. G. Lewis, “Grain Size Determination for Parallel Processing,” IEEE software, Jan. 1988, Pages 23-32.
[2]D. Minoli, “A Networking Approach to Grid Computing,” A John Wiley & Sons, 2005.
[3]E. S. H. Hou, N. Ansari, and H. Ren, “A Genetic Algorithm for Multiprocessor Scheduling,” IEEE Trans. Parallel and Distributed Systems, Feb. 1994, Pages 113-120.
[4]G. Park, B. Shirzai, and J. Marquis, “DFRN: A New Approach for Duplication Based Scheduling for Distributed Memory Multiprocessor Systems,” Proc. Int’l Conf. Parallel Processing, 1997, Pages 157-166.
[5] G. C. Sih and E. A. Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures,” IEEE Trans. Parallel and Distributed Systems, Feb. 1993, Page 175-186.
[6] G. Lai, “A Novel Task Scheduling Algorithm for Distributed Heterogeneous Computing Systems,” PARA '04 State-of-the-Art in Scientific Computing, Feb. 2004.
[7]H. Singh and A. Youssef, “Mapping and Scheduling Heterogeneous Task Graphs Using Genetic Algorithm,” Proc. Heterogeneous Computing Workshop, 1996, Pages 86-97.
[8] H. Topcuolgu, S. Hariri, and M. Y. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. Parallel and Distributed Systems, Mar. 2002, Pages 260-274.
[9]H. EI-Rewini and T. G. Lewis, “Scheduling Parallel Program tasks onto Arbitrary Target Machines,” J. Parallel and Distributed Computing, Sept. 1990, Pages 138-153.
[10]I. Ahmad and Y. Kwok, “A New Approach to Scheduling Parallel Programs Using Task Duplication,” Proc. Int’l Conf. Parallel Processing, 1994, Pages 47-51.
[11]L. Tao, B. Narahari, and Y.C. Zhao, “Heuristics for Mapping Parallel Computations to Heterogeneous Parallel Architectures,” Proc. Heterogeneous Computing Workshop, 1993.
[12]L. Wang, H.J. Siegel, and V.P. Roychowdhury, “A Genetic-Algorithm-Based Approach for Task Matching and Scheduling in Heterogeneous Computing Environments,” Proc. Heterogeneous Computing Workshop, 1996.
[13]M. Wu and D. Gajski, “Hypertool: A Programming Aid for Message-Passing Systems,” IEEE Trans. Parallel and Distributed Systems, July. 1990, Pages 330-343.
[14]M. Wu, W. Shu, and J. Gu, “Local Search for DAG Scheduling and Task Assignment,” Proc. Int’l Conf. Parallel Processing, 1997, Pages 174-180.
[15]P. Shroff, D.W. Watson, N.S. Flann, and R. Freund, “Genetic Simulated Annealing for Scheduling Data-Dependent Tasks in Heterogeneous Environments,” Proc. Heterogeneous Computing Workshop, 1996, Pages 98-104.
[16]S. J. Kim and J. C. Browne, “A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures,” Proc. Int’l Conf. Parallel Processing, 1988, Pages 1-8.
[17]T. Yang and A. Gerasoulis, “DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors,” IEEE Trans. Parallel and Distributed Systems, Sept. 1994, Pages 951-967.
[18]T. Hagras and J. Janecek, “A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems,” Parallel Computing, July 2005, Pages 653-670.
[19]Y. Chung and S. Ranka, “Applications and performance Analysis of a Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed Memory Multiprocessor,” Proc. Supercomputing, Nov. 1992, Pages 512-521.
[20]Y. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graph to Multiprocessors,” IEEE Trans. Parallel and Distributed Systems, May 1996, Pages 506-521.
[21]Y. Kwok, I. Ahmad, and J. Gu, “FAST: A Low-Complexity Algorithm for efficient Scheduling of DAGs on Parallel Processors,” Proc. Int’l Conf. Parallel Processing, 1996, Pages 150-157.