臺灣博碩士論文加值系統

本研究利用鏈狀分割法（chain partitioner）將直接模擬蒙地卡羅法（Direct Simulation Monte Carlo method, DSMC）予以平行化，然後在一個有九顆處理器的電腦叢集系統（PC cluster）上執行並與之前蕭啟宏[5]論文中使用單一處理器的例子作比較，以凸顯平行化的優點。在平行化的過程中，在做區域切割時必須考慮到以每顆處理器負責相同的粒子數為分割標準，而非相同的區域大小。此外，在分散式記憶體的系統上作平行計算時，計算速度(speedup)並不能與所使用的處理器數目成線性正比，因此當參與計算的處理器數目增加時，儘管速度變快也不能持續地保持好的運算效率（Efficiency）。最後，模擬粒子數及計算腔體的尺寸和計算時步（time step）分別被提出討論是否對平行程式執行時的性能表現有所影響，結果發現在越多的模擬粒子數及越大的計算腔體的案例中，平行程式能得到較好的性能，而由於本研究中粒子數並不會隨時間劇烈改變，所以計算時步並不影響性能。

In this thesis, the parallelization is applied to DSMC method by utilizing chain partitioner. The computation is carried out on a PC cluster system consisting of nine processors. The preliminary results are compared with the Hsiao’s single-processor results [5], to demonstrate the advantage of parallelization. The computational domain is decomposed according to the same number of simulated particles in each processor. When a parallel program is executed on a distributed memory system, the speedup may not be proportional linearly to the number of processor. The computing load in each processor becomes lighter by increasing the processor number, whereas the communication load becomes heavier at the same time. Therefore the efficiency becomes worse with an increment of processor number. The parametric studies are based on the variations of particle number, computing domain size and time step, respectively. The better speedup and efficiency can be achieved when the particle number and computational domain increase. The performance does not depend on time step in present case because the variation of particle number is not severe.

Contents
ABSTRACT(CHINESE) I
ABSTRACT(ENGLISH) II
ACKNOWLEDGMENT III
CONTENTS V
LIST OF TABLES VI
LIST OF FIGURES VII
CHAPTER 1 INTRODUCTION 1
1.1 MOTIVIATION 1
1.2 LITERATURE REVIEW 2
1.3 PROBLEM DESCRIPTION 5
CHAPTER 2 SIMULATION METHOD AND COMPUTING SYSTEM 7
2.1 INTRODUCE TO DSMC METHOD 7
2.2 HARDWARE FOR HIGH PERFORMANCE COMPUTATIONS 8
2.2.1 The shared memory model 9
2.2.2 The distributed memory model 10
2.3 PARALLEL PROGRAM LANGUAGES 11
2.4 DOMAIN PARTITION METHODS 12
2.5 LOAD BALANCE PROCESS 14
2.5.1 Static load balance 14
2.5.2 Dynamic load balance 15
2.6 PARALLEL DSMC METHOD 15
2.7 SUMMARY OF PARALLEL DSMC PROCEDURE FOR PRESENT WORK 16
2.8 PERFORMANCE EVALUATION OF PARALLEL IMPLEMENT 19
CHAPTER 3 PRESENT RESULTS AND DISCUSSION 21
3.1 COMPARISON WITH HSIAO'S THESIS[5] 22
3.1.1 The comparison with Hsiao’s results 22
3.1.2 The efficiency comparison with Hsiao's parallel code 22
3.2 PARTITION METHOD 23
3.3 THE EFFECTS OF PROCESSOR NUMBER 26
3.4 EFFECTS OF DIFFERENT PARTICLE NUMBERS 27
3.5 INFLUENCES OF DIFFERENT COMPUTING DOMAIN SIZE 28
3.6 EFFECTS OF DIFFERENT PARTICLE NUMBERS 29
CHAPTER 4 CONCLUSIONS AND SUGGESTED FUTURE WORK 31
4.1 CONCLUSIONS 31
4.2 SUGGESTED FUTURE WORKS 32
REFERENCE 33
FIGURES…… 36

Reference
1. C. H. Dei and C. H. Chen, “The study of Thermal Flow Field in Vertical Rotating Disk Chemical Vapor Deposition Reactor Using the DSMC,”Institute of Mechanical Engineering College of Engineering, National Chiao Tung University, 1998.
2. Y. C. Sun and C. H. Chen, “Analysis of Thermal Flow Field in Vertical Rotating Injector Low Pressure Chemical Vapor Deposition Reactor Using the DSMC,” Institute of Mechanical Engineering College of Engineering, National Chiao Tung University, 1998.
3. P. M. Yang and C. H. Chen, “Analysis of Thermal Flow Field and Film Deposition in Vertical Rotating Substrate for LPCVD Using the DSMC Method,” Institute of Mechanical Engineering College of Engineering, National Chiao Tung University, 1999.
4. H. P. Chen and C. H. Chen, “The Simulation of Compression Characteristics for a Simple Molecular Drag Pump Using DSMC Method,” Institute of Mechanical Engineering College of Engineering, National Chiao Tung University, 2000.
5. C. H. Hsiao and C. H. Chen, “The Simulation of Thermal Flow Field and Film Deposition in Vertical Rotating Substrate for LPCVD Using DSMC Method,” Institute of Mechanical Engineering College of Engineering, National Chiao Tung University, 2001.
6. G. A. Bird, Molecular gas dynamics and the direct simulation of gas flows, Oxford University Press, London, 1994.
7. T. I. Gombosi, Gaskinetic Theory, Cambridge University Press, 1994.
8. R. G. Wilmoth, “Direct simulation Monte Carlo analysis of rarefied flows on parallel processors,” Journal of Thermophysics, pp. 292-300, July/Sept 1991.
9. P. Cremonesi, M. Ferrari, A. Frezzotti and R. Pavani, “Paraller Algorithms Applied to Direct Simulation Methods,” Paraller and Distributed Processing, pp. 239-246, Euromicro Workshop on 1993
10. R. P. Nance, R. G. Wilmoth, B. Moon, H. A. Hassan and J. Saltz, “Parallel Monte Carlo Simulation of Three-Dimensional Flow over a Flat Plate,” Journal of Thermophysics and Heat Transfer, Vol.9.No.3, 471-477,July-September 1995.
11. J. D. McDonald and L. Dagum, “A Comparison of Particle Simulation Implementations on Two Different Parallel Architectures,” Proceedings of Distributed Memory Computing Conference, 1991, The Sixth, pp. 413-418
12. S. Dietrich and I. D. Boyd, “Scalar and Parallel Optimized Implementation of the Direct Simulation Monte Carlo Method,” Journal of Computational Physics, Vol.126, pp. 328-342,1996.
13. B. Moon and J. Saltz, “Adaptive Runtime Support for Direct Simulation Monte Carlo Methods on Distributed Memory Architectures,” Proceedings of the Scalable High-Performance Computing Conference May 23-25 1994 Knoxville, TN, USA
14. Y. Matsumoto and T. Tokumasu, “ Parallel Computing of Diatomic Molecular Rarefied Gas Flows,” Parallel Computing, Vol.23, pp. 1249-1260,1997.
15. F. Coron and P. Homsi, “Rarefied Gas Flow Computational with a 3D Unstructured Mesh On a Connection Machine (CM2),”Future Generation Computer System, Vol.11, pp. 1-6, 1995.
16. G. J. LeBeau, “A Parallel Implementation of the Direct Simulation Monte Carlo Method,” Comput. Methods Appl. Mech. Engrg. 174, pp. 319-337, 1999.
17. T. J. Yang and J. S. Wu, “The parallel Implementation of the Direct Simulation Monte Carlo Method Using Unstructured Mesh and Its Applications,” Institute of Mechanical Engineering College of Engineering, National Chiao Tung University, 2000.
18. A. Singh and Z. Yong, “Parallel unstructured dynamic grid direct simulation Monte Carlo of molecular gas dynamics and the associated thin-film deposition,” First MIT Conference on Computational Fluid and Solid Mechanics.
19. D. W. Heermann and A. N. Burkitt, “Parallel Algorithms in Computational Science,” Springer-Verlag, Berlin Heidelberg, 1991.
20. J. Jaja, “An introduction to Parallel Algorithms,” Addison-Wesley Publishing Comp, Reading, 1992.
21. 張德富, “平行處理技術,” 儒林圖書公司,1993.
22. C. Xu and C. M. Lau, “Load Balancing in Parallel Computers,” Kluwer Academic Publishers, Boston, 1997.
23. S. Tatsuta, Y. Sato, N. Tamaoki, Y. Egashira, H. Komiyama, “Acceleration of CVD Step Coverage Simulation Applied to DSMC Method,” Transactions of Japan Society of Mechanical Engineers, Part B v 62 n 601 p 3323-3329 0387-5016, Sep. 1996.
24. M. Ota, H. Taniguchi and M. Aritomi, “Parallel Processings for Direct Simulation Monte Carlo Method,” Transactions of Japan Society of Mechanical Engineers, Part B v 61 n 582 p 496-502, Feb. 1995.
25. 曾耀寰, “企鵝雄兵-以LINUX進行電腦叢集計算,” 和碩科技文化有限公司,Nov. 2001.