臺灣博碩士論文加值系統

Fortran 語言在科學計算上廣為大家所採用，但是目前的 Fortran 77和 Fortran 90 語言已經數年前所定義的，對於支援目前日新月異的計算機架構的能力已經不再足夠。要在這些新環境上完全發揮計算能力,我們還需要更多目前 Fortran 77 或 Fortran 90 所無法提供的功能。 HPFF (High Performance Fortran Forum) 提供了一組 Fortran 的標準擴充功能，也就是 HPF-2 (High Performance Fortran 2)語言。 HPF-2最終的目的是希望能夠成為標準的高速平行計算程式語言。 我們實作 HPF-2的一個子集，特別是 Fortran 所沒有的優點 - 資料分散和平行計算的功能。 HPF-2 資料分散方式可分為 BLOCK、 CYCLIC 、 BLOCK-CYCLIC 、 GEN_BLOCK 及 INDIRECT，在這篇文章，我們提供一種有效率的排程演算法 DRC (degree-reduction and coloring)，來縮短GEN_BLOCK資料重新分散所需的時間，在最短的傳輸步驟內將需要重新分散的資料排程，來獲得較佳的傳輸時間。 以及針對GEN_BLOCK用來傳輸資料的MPI (Message Passing Interface) 做 本地端-本地端 與 本地端-遠端 在傳送時間上的探討，針對DRC做適度的修整。 最後的實驗部份與 Divide-and-Conquer (DC), Smallest Conflict Points Algorithm (SCPA) 和 List 演算法比較，這些演算法被提出來重新探討並與我們所提出的演算法做效能上的比較，來驗證我們所提出的演算法可以對以往的方法做進一步的改善。

High Performance Fortran Forum (HPFF) offered a set of standard extensions to Fortran, a given name High Performance Fortran 2 (HPF-2). The purpose of HPF-2 is to become the standard language of high speed and parallel calculation. We implement a subset of HPF-2 language. The data are redistribution with the function of parallel computing. The extended function of data distribution in HPF-2 can be divided into BLOCK, CYCLIC, BLOCK-CYCLIC, GEN_BLOCK and INDIRECT in this article, we provide an efficient scheduling algorithm degree-reduction and coloring (DRC) to shorten the necessary time of GEN_BLOCK data redistribution, and discuss with Message Passing Interface (MPI) which GEN_BLOCK used for data redistribution, comparing the different transfer time between data sending to local-host and sending to remote-host. After the analysis the discussion of MPI, we do appropriate recondition to DRC. The experiment part we compare with Divide-and-Conquer (DC), Smallest Conflict Points Algorithm (SCPA) and List algorithm to verify the algorithm of performing that we put forward. Related work on these problems is reviewed and experimental results to demonstrate the benefit of the proposed methods.

ACKNOWKEDGE I
ABSTRACT II
摘要 III
CHAPTER 1 INTRODUCTION 1
1.1. Data-Parallel Languages 2
1.2. DISTRIBUTE Directive 3
1.3. Organization Of The Dissertation 6
CHAPTER 2 RELATED WORK 7
2.1. GEN_BLOCK Redistribution 9
2.2. Divide-and-Conquer Scheduling Algorithm 11
2.3. Smallest Conflict Points Algorithm 14
2.4. List Algorithm 16
CHAPTER 3 PROPOSED ALGORITHM 21
3.1. Message-Coloring Step 21
3.2. Degree-Reduction Step 25
3.3. Correctness Proof 29
3.4. MPI Transport Measurement 30
CHAPTER 4 PERFORMANCE EVALUATION 33
4.1. Simulation Comparison 34
4.2. Performance On Linux Cluster 45
4.3. Scheduled After Normalized Performance On Linux Cluster 48
CHAPTER 5 CONCLUSION 50
REFERENCES 52

1.G. Bandera and E.L. Zapata, “Sparse Matrix Block-Cyclic Redistribution,” Proceeding of IEEE Int'l. Parallel Processing Symposium (IPPS'99), San Juan, Puerto Rico, 355 - 359 ,April 1999
2.J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
3.Frederic Desprez, Jack Dongarra and Antoine Petitet, “Scheduling Block-Cyclic Data redistribution,” IEEE Trans. on PDS, vol. 9, no. 2, pp. 192-205, Feb. 1998.
4.Minyi Guo, “Communication Generation for Irregular Codes,” The Journal of Supercomputing, vol. 25, no. 3, pp. 199-214, 2003.
5.Minyi Guo and I. Nakata, “A Framework for Efficient Array Redistribution on Distributed Memory Multicomputers,” The Journal of Supercomputing, vol. 20, no. 3, pp. 243-265, 2001.
6.Minyi Guo, I. Nakata and Y. Yamashita, “Contention-Free Communication Scheduling for Array Redistribution,” Parallel Computing, vol. 26, no.8, pp. 1325-1343, 2000.
7.Minyi Guo, I. Nakata and Y. Yamashita, “An Efficient Data Distribution Technique for Distributed Memory Parallel Computers,” Joint Symp. on Parallel Processing (JSPP'97), pp.189-196, 1997.
8.Minyi Guo, Yi Pan and Zhen Liu, “Symbolic Communication Set Generation for Irregular Parallel Applications,” The Journal of Supercomputing, vol. 25, pp. 199-214, 2003.
9.Edgar T. Kalns, and Lionel M. Ni, “Processor Mapping Technique Toward Efficient Data Redistribution,” IEEE Trans. on PDS, vol. 6, no. 12, pp. 1234-1247, December 1995.
10.S. D. Kaushik, C. H. Huang, J. Ramanujam and P. Sadayappan, “Multiphase data redistribution: Modeling and evaluation,” International Parallel Processing Symposium (IPPS’95), pp. 441-445, 1995.
11.Kun-Ming Yu, Chi-Hsiu Chen, Ching-Hsien Hsu, Chang Wu Yu and C.-K. Liang, “Contention-Free Communication Scheduling for Irregular Data Redistribution in Parallelizing Compilers,” Advanced Parallel Processing Technologies - Lecture Notes in Computer Science, Vol. 3756, pp. 101-110, Springer-Verlag, Oct. 2005. (APPT’05)
12.Peizong Lee, Academia Sinica, and Zvi Meir Kedem, “Automatic Data and Computation Decomposition on Distributed Memory Parallel Computers,” ACM Transactions on Programming Languages and systems, Vol 24, No. 1, pp. 1-50, January 2002.
13.S. Lee, H. Yook, M. Koo and M. Park, “Processor reordering algorithms toward efficient GEN_BLOCK redistribution,” Proceedings of the ACM symposium on Applied computing, pp . 539-543, 2001.
14.Y. W. Lim, Prashanth B. Bhat and Viktor and K. Prasanna, “Efficient Algorithms for Block-Cyclic Redistribution of Arrays,” Algorithmica, vol. 24, no. 3-4, pp. 298-330, 1999.
15.C.-H Hsu, S.-W Bai, Y.-C Chung and C.-S Yang, “A Generalized Basic-Cycle Calculation Method for Efficient Array Redistribution,” IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 12, pp. 1201-1216, Dec. 2000.
16.Ching-Hsien Hsu, Kun-Ming Yu, “An Optimal Processor Replacement Scheme for Efficient Communication of Runtime Data Realignment,” Parallel and Distributed and Processing and Applications, - Lecture Notes in Computer Science, Vol. 3358, pp. 268-273, 2004.
17.Chao-Yang Lan, Shih-Chang Chen and Ching-Hsien Hsu, "On Improving Scheduling Length for Irregular Data Redistribution Based on Local Message Reduction," Proceedings of the 12th Workshop on Compiler Techniques for High-Performance Computing, pp. 203-211, March 2006, Taiwan.
18.C.-H Hsu, Dong-Lin Yang, Yeh-Ching Chung and Chyi-Ren Dow, “A Generalized Processor Mapping Technique for Array Redistribution,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, vol. 7, pp. 743-757, July 2001.
19.Antoine P. Petitet and Jack J. Dongarra, “Algorithmic Redistribution Methods for Block-Cyclic Decompositions,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 12, pp. 1201-1216, Dec. 1999
20.Neungsoo Park, Viktor K. Prasanna and Cauligi S. Raghavendra, “Efficient Algorithms for Block-Cyclic Data redistribution Between Processor Sets,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, No. 12, pp.1217-1240, Dec. 1999.
21..L. Prylli and B. Touranchean, “Fast runtime block cyclic data redistribution on multiprocessors,” Journal of Parallel and Distributed Computing, vol. 45, pp. 63-72, Aug. 1997.
22.S. Ramaswamy, B. Simons, and P. Banerjee, “Optimization for Efficient Data redistribution on Distributed Memory Multicomputers,” Journal of Parallel and Distributed Computing, vol. 38, pp. 217-228, 1996.
23.Akiyoshi Wakatani and Michael Wolfe, “Optimization of Data redistribution for Distributed Memory Multicomputers,” short communication, Parallel Computing, vol. 21, no. 9, pp. 1485-1490, September 1995.
24.Hui Wang, Minyi Guo and Wenxi Chen, “An Efficient Algorithm for Irregular Redistribution in Parallelizing Compilers,” Proceedings of 2003 International Symposium on Parallel and Distributed Processing with Applications, LNCS 2745, pp 76-87, 2003.
25.Hui Wang, Minyi Guo and Daming Wei, "Divide-and-conquer Algorithm for Irregular Redistributions in Parallelizing Compilers”, The Journal of Supercomputing, vol. 29, no. 2, pp. 157-170, 2004.
26.Hui Wang, Minyi Guo and Daming Wei, “Message Scheduling for irregular Data Redistribution in Parallelizing Compilers,” IEICE TRANS. INF&SYST. Vol.E89-D.NO.2 February 2006.
27.H.-G. Yook and Myung-Soon Park, “Scheduling GEN_BLOCK Array Redistribution,” The Journal of Supercomputing, vol.22, no. 3, pp 251-267, 2002