臺灣博碩士論文加值系統

近年來，因科技之發達，有許多需要大量運算之應用已逐步被實現，例如氣象預報、流體力學、影像處理、甚至於在統計分析上的應用，皆需利用電腦運算獲得結果。而這些運算中，有些運算模式如LU、GJE、FFT是比較常見的運算模式，這些運算模式可透過平行處理來增進運算速度。
而在平行處理的研究中，分散式異質性系統技術日新月異地進步，但如要使其能滿足各種平行應用的計算需求，則最需要的就是設計一個有效率的工作排程策略。過去的研究指出排程問題是一個NP-complete的問題；為了考慮排程時間，許多學者致力於直覺式演算法(Heuristic)的設計。在此論文中則是提出了一個以複製為基礎的演算法(D3T演算法)來解決排程問題，其主要精神為考慮每個子工作排程之後，排程時間最長的路徑會動態的改變。為了使每個階段上會影響總排程時間的主要子工作(dominate task)所處的排程路徑的排程時間縮短，我們優先對此主要子工作做排程，以期縮短最後排程時間。透過實驗的證明，D3T演算法效能明顯優於其他最近比較有名的演算法(CNPT, TANH, HCPFD)，證明了D3T演算法在分散式異質性環境中有不錯的表現，並可達到有效縮短平行程式執行時間的目標。

Recently, due to the advance of the information technology, many computing sensitive applications have been proposed; for example, weather modeling, statistics analysis, fluid flow, image processing, and so on. Some mathematical expressions are often used in the above applications e.g., the Gauss-Jordan Elimination (GJE), the Fast Fourier Transformation (FFT), LU factoring, and so on. Parallel computing could solve these applications more quickly by creating and coordinating multiple execution processes.
The capability of the distributed heterogeneous computing system grows up in recent years. In order to satisfy the computational requirement of many parallel applications, the most important issue is how to design an efficiently scheduling strategy. However, the scheduling problem is an NP-complete problem; many researchers tend to propose the heuristic to satisfy a reasonable time complexity. This thesis proposes a duplication-based task scheduling algorithm, called D3T, to solve the scheduling problem. The main idea of the D3T algorithm is that the critical path (CP) might dynamically change after each scheduling step. To schedule the dominate task first is a good idea to reduce the schedule length of the critical path.
The experimental results show that the performance of the D3T is better than those of the other three algorithms (CNPT, TANH, HCPFD). The experimental results also demonstrate that the D3T algorithm could reduce the schedule length in the DHC system.

List of Figures iii
List of Tables v
摘要 vi
Abstract vii
Chapter1. Introduction 1
1.1 Motivations 1
1.2 Problems 2
1.3 Purposes 4
1.4 Restrictions 7
1.5 Notations 8
Chapter 2. Related Works 10
2.1 The Levelized Duilication-Based Scheduling (LDBS) Algorithm 10
2.2 The Task Duplication Scheduling (TDS) Algorithm and the Scalable Task Duplication Scheduling (STDS) Algorithm 11
2.3 The Task Duplication-based Scheduling Algorithm for Network of Heterogeneous Systems (TANH). 14
2.4 The Heterogeneous Critical Parents with Fast Duplicator (HCPFD) Algorithm 15
Chapter 3 Proposed Algorithm 17
3.1 Problem Definition 17
3.2 The Dynamic Duplication of Dominate Tasks Scheduling Algorithm 20
Chapter 4. Simulation Environment 32
Chapter 5. Experimental Results 36
5.1 Comparison Metrics 36
5.2 Influence Factors 37
5.3 Comparison Results 38
Chapter 6. Conclusions and Future Works 59
References 60

Ahmad, I., and Ghafoor, A. (1991, Oct). Semi-distributed load balancing for massively parallel multicomputer systems. IEEE Trans. Softw. Eng., 17(10), 987–1004.
Ahmad, I., and Kwok, Y.-K. (1998, Sept). On Exploiting Task Duplication in Parallel Program Scheduling. IEEE Transactions on Parallel and Distributed Systems, 9(8), 872-892.
Bajaj, Rashmi., and Agrawal, Dharma P. (2004, Feb). Improving Scheduling of Tasks in a Heterogeneous Environment. IEEE Transactions on Parallel and Distributed Systems, 15(2), 107-118.
Braun, T. D. et. al. (1999, Apr). A comparison study of static mapping heuristic for a class of meta-tasks on heterogeneous computing system. IPPS/SPDP Workshop on Heterogeneous Computing, San Juan, Puerto Rico.
Braun, T., Siegel, H.J., Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B., Hengsen, D., and Freund, R.F. (1999). A Comparison Study of Static Mapping Heuristics for a Class of Meta-Tasks on Heterogeneous Computing Systems. Proc. Heterogeneous Computing Workshop, 15-29.
Chu, W. W., Lan, M.-T., and Hellerstein, J. (1984, Aug). Estimation of intermodule communication (IMC) and its applications in distributed processing systems. IEEE Trans. Comput., 33(8), 691–699.
Chung, Y. C., and Ranka, S. (1992, Nov). Application and Performance Analysis of a Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed-Memory Multiprocessors. Proc. Supercomputing, 512-521.
Chung, Y.C., Liu, C.C., & Liu, J.S. (1995, June). Applications and Performance Analysis of A Compile-Time Optimization Approach for List Scheduling Algorithms on Distributed Memory Multiprocessors. Journal of Information Science and Engineering, 11(2), 155-181
Correa, R.C., Ferreria, A., and Rebreyend, P. (1996, Oct). Integrating List Heuristics into Genetic Algorithms for Multiprocessor Scheduling. Proc. Eighth IEEE symp. Parallel and Distributed Processing (SPDP ’96).
Dogan, A. and Ozguner, R. (2002) LDBS: a duplication based scheduling algorithm for heterogeneous computing systems. Proceedings of International Conference on Parallel Processing 2002 (ICPP'02), 352- 359.
Gajski, D. D., and Pier, J. (1985, Jun). Essential issues in multiprocessors. IEEE Computer, 18(6).
Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, NY.
Gerasoulis, A. and Yang, T. (1992, Dec). A Comparison of Clustering Heuristics for Scheduling Directed Acyclic Graphs onto Multiprocessors. Journal of Parallel and Distributed Computing, 16(4), 276-291.
Gerasoulis, A., and Yang, T. (1993, June). On the Granularity and Clustering of Directed Acyclic Task Graphs. IEEE Transactions on Parallel and Distributed Systems, 4(6), 686-701.
Hagras, Tarek. and Janecek, Jan. (2003). A High Performance, Low Complexity Algorithm for Compile-Time Job Scheduling in Homogeneous Computing Environment. 2003 IEEE Int. Conf. on Parallel Processing Workshops.
Hagras, Tarek., and Janecek, Jan.(2004a). A High Performance, Low Complexity Algorithm for Compile-Time Task Scheduling in Heterogeneous Systems. 2004 IEEE Int. Parallel and Distributed Processing Symposium.
Hagras, Tarek., and Janecek, Jan.(2004b). A Near Lower-Bound Complexity Algorithm for Compile-Time Task-Scheduling in Heterogeneous Computing Systems. 2004 IEEE Proceedings of the ISPDC/HeteroPar’04.
Hou, E.S.H., Ansari, N., and Ren, H. (1994 Feb). A Genetic Algorithm for Mutiprocessor Scheduling. “ IEEE Trans. Parallel and Distributed Systems, 5(2), 113-120.
Kwok, Y., Ahmad, I., and Gu, J. (1996). Fast: A Low-Complexity Algorithm for Efficient Scheduling of DAGs on Parallel Processors. Proc. Int’l Conf. Parallel Processing, 2, 150-157.
Kwok, Y.-K., and Ahmad, I. (2000). Link Contention-Constrained Scheduling and Mapping of Tasks and Messages to a Network of Heterogeneous Processors. Cluster Computing: Journal of Networks, Software Tools, and Applications, 3(2), 113-124.
Kwok, Y-K., and Ahmad, I. (1996, May). Dynamic critical-path scheduling: an effective technique forallocating task graphs to multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 7(5), 506-521.
Kwok, Y-K., and Ahmad, I. (1999, Dec). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4), 406 – 471.
Lai, G.J., Fang, J.F., Sung, P.S., and Pean, D.L. (2003, July). Scheduling Parallel Tasks onto NUMA Multiprocessors with Inter-processor Communication Overhead. 2003 International Symposium on Parallel and Distributed Processing and Applications( ISPA-03), Japan.
Liu, C.H., Li, C.F., Lai, K.C., and Wu, C.C. (2006, July). A Dynamic Critical Path Duplication Task Scheduling Algorithm for Distributed Heterogeneous Computing Systems. The 2006 International Conference on Parallel and Distributed Systems (ICPADS 2006), Minneapolis, U.S.A.
Liu, C.H. (2006, July). A Study of Exploiting Efficiency of the Duplication-based Algorithm in Distributed Heterogeneous Computing Systems. Unpublished dissertation, National Tai-chung University, Taiwan.
Lord, R.E., Kowalik, J.S., & Kumar, S.P. (1983, Jan). Solving Linear Algebraic Equations on an MIMD Computer. Journal of the ACM, 30(1), 103-117.
Olivier, B., Vincent B. and Yves, R. (2002). The Iso-Level Scheduling Heuristic for Heterogeneous Processors. Proc. Of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing.
Palis, M. A., Liou, J.-C., Rajasekaran, S., Shende, S., and Wei, D. S. L. (1995, Dec). Online scheduling of dynamic trees. Para. Proc. Lett., 5(4), 635–646.
Palis, M.A.., Liou, J.-C., and Wei, D.S.L. (1996, Jan). Task Clustering and Scheduling for Distributed Memory Parallel Architectures. IEEE Transactions on Parallel and Distributed Systems, 7(1), 46-55.
Pande, S. S., Agrawal, D. P., and Mauney, J. (1994a, May). A New Threshold Scheduling Strategy for Sisal Programs on Distributed Memory Systems. Journal of Parallel and Distributed Computing, 21(2), 223-236.
Pande, S. S., Agrawal, D. P., and Mauney, J. (1995, Apr). A Scalable Scheduling Method for Functional Parallelism on Distributed Memory Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 6(4), 388-399.
Ranaweera, A. and Agrawal, D.P. (2000b, May). A task duplication based algorithmfor heterogeneous systems. Proceedings of the Int. Paralleland Distributed Processing Symposium, 445–450.
Ranaweera,A. and Agrawal,D.P. (2000a). A scalable task duplication based algorithm for heterogeneous systems. Proceedings of the ICPP, 383–390.
Sarkar, V. (1989). Partitionning Scheduling Parallel Programs for Execution onMultiprocessors. MIT Press.
Selvakumar, S., and Murthy, C. Siva Ram. (1994). Scheduling Precedence Constrained Task Graphs with Non-Negligible Intertask Communication onto Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 5(3), 328-336.
Shroff, Ps., Watson, D.W., Flann, N.S., and Freund, R. (1996) Genetic Simulated Annealing for Scheduling Data-Dependent Tasks in Heterogeneous Environments. Proc Heterogeneous Computing Workshop, 98-104.
Sih, G.C., and Lee, E. A. (1993). A Compiler-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures. IEEE Transactions on Parallel and Distributed Systems, 4(2), 175-186.
Singh, H., and Youssef, A. (1994). Mapping and Shcheduling Heterogeneous Task Graphs Using Genetic Algorithms. Proc. Heterogeneous Computing Workshop, 47-51.
Tao, L., Narahari, B., and Zhao, Y.C. (1993). Heuristics for Mapping Parallel Computations to Heterogeneous Parallel Architectures. Proc. Heterogeneous Computing Workshop.
Topcuoglu, H., Hariri, S., and Wu, M.Y. (2002, Mar). Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Transactions on Parallel and Distributed Systems, 13(3), 260-274.
Ullman, J. D. (1975). NP-Complete Scheduling Problems. J. Computing System Science, 10, 384-393.
Wang, L., Siegel, H.J., and Roychowdhury, V.P. (1996). A Genetic-Algorithm-Based Approach for Task Matching and Scheduling in Heterogeneous Computing Environments. Proc. Heterogeneous Computing Workshop.
Wu, M., Shu, W., and Gu, J. (1997). Loacl Search for DAG Scheduling and Task Assignment. Proc. 1997 Int’l Conf. Parallel Processing, 174-180.
Wu, M.Y., & Gajski, D. (1990). Hypertool: A Programming Aid for Message-Passing Systems. IEEE Transactions on Parallel and Distributed Systems, 1(3), 330-343.
Wu, M-Y., and Shu, W. (2001, Apr). A high-performance mapping algorithm for heterogeneous computing systems. Int' l Parallel and Distributed Processing Symposium, San Francisco, CA.
Wu, M-Y., Shu, W., and Zhang, H. (2000, May). Segmented min-min: Astatic mapping algorithm for meta-tasks on heterogeneous computing systems. IPDPS Workshop on Heterogeneous Computing, 375–385, Canc´un, Mexico.
Yang, Tao., and Gerasoulis, A., (1994, Sep). DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Transactions on Parallel and Distributed Systems, 5(9), 951-967.
宋佩珊 (民92)。透過網路連結異質性電腦環境中增進計算效能之研究。未出版之碩士論文，國立台中師範學院教育測驗統計所，台中市。