本研究主要為探討平行化處理用於流場之數值模擬，為了克服日益複雜的流場問題甚至是紊流問題所帶來之計算上的耗時，而將平行化的工具建立並應用於初步的基本問題。本研究使用 Gentoo Linux 作業系統，採用 MPI (Messages Passing Interface) 函式庫，並使用至多九台電腦實作出可用於流場的平行化工具。在解 Ax = b 且 A 為 tridiagonal matrix 的演算法方面，本研究採用 Parallel Partition LU Algorithm 、Parallel Diagonal Dominant Algorithm 等演算法。另外本研究亦採用 Domain Decomposition method 直接先將計算區域分割之後，在各 CPU 獨立形成矩陣，並在各 CPU 之間交換邊界值。

　　本研究除了比較 PPT 、PDD 差異並討論其效率之外，並將二維穴流，用 Domain Decomposition Method 平行化搭配不同的矩陣解法來比較其加速性 (Speedup) ，並比較各種方法之精確度、平行效率。對於二維問題，並另外比較 1D Domain Decomposition 與 2D Domain Decomposition 的差異。對於網路頻寬的不同造成之加速效果的不同本研究亦有比較。綜合本研究各項測試的結果，建議未來解複雜流場的方式都採用 Domain Decomposition method ，而選擇 1D Topology 或是 2D Topology 則取決於流場區域的形狀，只要讓各主機之處理器使用率能夠達到高負載及主機間計算量之負載平衡，便能獲得最好的平行效率，另外至少要 gigabit 等級以上的網路環境才能得到比較理想的 Speedup 。

　The objective of this study aims at applying the parallelization technique to flow computation. In order to conquer the time consumption from the growing complexity of flow computation problems, especially the direct numerical simulation (DNS) of turbulence problems, the parallel tools are constructed and applied to some fundamental problems first. This study uses the Gentoo Linux operating system on which the MPI (Messages Passing Interface) libraries are installed. A nine-nodes pc cluster is established as the parallel tools for flow field simulation. To solve Ax = b while A is a tridiagonal matrix, two algorithms including Parallel Partition LU Algorithm and Parallel Diagonal Dominant Algorithm are used. Furthermore, the Domain Decomposition Method which separates the domain into several subdomains and assigns each CPU to solve a subdomain is used.

　The study compares the performance differences of PPT and PDD algorithms and discuss their efficiencies. A cavity flow which is 2D is parallelized by domain decomposition method. The results obtained with 1D Domain Decomposition and 2D Domain Decomposition are also investigated and compared with each other. The comparison of the speedup resulting from different network environments is included in the study.Based on the present study, the domain decomposition method is recommended to use for solving complicated flow fields. It is also found that the gigabit ethernet network environment can lead to better speedup than the usual fast ethernet network environment.

[1] Guerrero, M. S., Parallel multigrid algorithms for computational fluid dynamics and heat transfer , Departament de M`aquines i Motors T`ermics E.T.S.E.I.T Univerditat Polit`ecnica de Catalunya, Doctor Enginyer Industrial, 2000.
[2] Chen, H., Hunag, P. G., and LeBeau, R. P., Performance Tests of a New Parallel Unstructured CFD Code on Multiple Linux Cluster Architectures, Dept. of Mechanical Engineering, University of Kentucky，第十一屆全國計算流體力學學術研討會，2004 年八月。
[3] Farrell, P. A., Cluster computing, Dept of Computer Science, Kent State University, Spring, 2004.
[4] Sun, X. H., Efficient Tridiagonal Solvers on Multicomputers, IEEE Transactions on computers, Vol. 41, No. 3, March, 1992
[5] 周朝宜、張西亞、鄭守成、許武榮、王順泰，A Study on Portable Parallel Program using Two-Dimensional Topology ，國家高速網路與計算中心，第十一屆全國計算流體力學學術研討會，2004 年八月。
[6] Ivanova, I. G. and Walshaw, C, A parallel method for solving pentadiagonal systems of linear equations, University of Greenwich, London, England.
[7] Austin, T. M., Berndt, M., and Moulton, J, D, A Memory efficient parallel tridiagonal solver , Preprint LA-UR-03-4149, 2004.
[8] Wang, H. H., A Parallel Method for Tridiagonal Equations, IBM Scientific Center, 1980.
[9] Sun, X. H. and Moitra, S., A Fast Parallel Tridiagonal Algorithm for a Class of CFD Applications , NASA Technical Paper 3585, August 1996.
[10] Sherman, J. and Morrison, W. J., Adjustment of an Inverse Matrix Corresponding to a Change in One element of a Given Matrix, The Annals of Mathematical Statistics, Vol. 21, No. 1, 124-127.
[11] Chan, A., Ashton, D., Lusk, R., and Gropp, W., Jumpshot 4 Users Guide, Mathematics and Computer Science Division, Argonne National Laboratory, December, 2004.
[12] Piernas, J., Flores, A., and Garc`?a, J. M., Analyzing the Performance of MPI in a Cluster of Workstations based on Fast Ethernet, ACPC 1999: 570-571.
[13] Stone, H. S., An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations, ACM: Volume 20, Issue 1, Pages: 27-38, 1973.
[14] Sun, X. H., and Zhang, W, A Parallel Two–Level Hybrid Method for Diagonal Dominant Tridiagonal Systems, Department of Computer Science, Illinois Institute of Technology, Chicago, IEEE, 2002.
[15] Sun, X. H., Application and accuracy of the parallel diagonal dominant algorithm, Parallel Computing 21(1995) 1241-1267.
[16] Egecioglu, O., Koc, C. K., and Laub, A. J., A Recursive Doubling Algorithm for Solution of Tridiagonal Systems on Hypercube Multiprocessors, Department of Computer Science University of California, 1988.
[17] Nupairoj, N. and Ni, L. M., Performance Evaluation of Some MPI Implementations on Workstation Clusters, IEEE 1995.
[18] Ortega, J. M., and Voigt, R. G., Solution of Partial Differential Equations on Vector and Parallel Computers, SIAM Review, Vol. 27, No. 2, 1985.
[19] Zaki, O., Luck, E., Gropp, W., and D. Swider, Toward Scalable Performance Visualization with Jumpshot, High Performance Computing Applications, pp. 277-288, Fall 1999.
[20] 鄭守成，MPI 平行計算程式設計，國家高速電腦中心，1999 年。
[21] 沈澄宇，高效能計算簡介，國家高速網路與計算中心，2003 年九月。