簡易檢索 / 詳目顯示

回結果列表
研究生： 潘茂森
Mao-Sen Pan
論文名稱： 無元素分析法之高效能軟體架構
High-Performance Software Framework for Element-free Methods
指導教授： 謝佑明
Yo-Ming Hsieh
口試委員: 謝尚賢
Shang-Hsien Hsieh
王仲宇
Chung-Yue Wang
楊元森
Yuan-Sen Yang
陳鴻銘
Hung-Ming Chen
張大鵬
Ta-Peng Chang
潘誠平
Chan-Ping Pan
學位類別： 博士
Doctor
系所名稱： 工程學院 - 營建工程系
Department of Civil and Construction Engineering
論文出版年： 2015
畢業學年度： 103
語文別： 中文
論文頁數： 151
中文關鍵詞： 無元素法 、軟體架構 、耦合分析 、物件導向設計 、高效能運算 、混合式運算 、GPU 、CUDA
外文關鍵詞： meshfree methods, software framework, object-oriented design, design pattern, high performance computing, CUDA
相關次數： 點閱：430  下載：7 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本研究目的在於發展高效能、易維護、易擴充的無元素力學分析程式之架構，根據過去20年的無元素法研究之相關文獻，整合、分析無元素法通用流程及基本要素，經過不斷的需求分析與調整，及效能剖析，發展出一套可實現多種無元素分析法、有限元素法及耦合分析的軟體架構 – ESFM (Essential Software Framework for Meshfree methods)。
    此架構包含了23類的群組演算法，涵蓋1) 無元素法基本要素，如近似函數 (approximation function)、基底函數 (basis function)、權重函數 (weight function)、支撐領域 (support domain)、邊界條件 (essential boundary condition) 等；2) 可擴充的力學分析Formulation，藉此實現其它力學分析法，如有限元素法等；3) 耦合分析架構，可藉由多種演算法耦合不同的力學分析系統；4) 效能相關數值方法，如鄰近點位搜尋演算法、稀疏矩陣儲存格式、稀疏矩陣求解等；5) 導入CUDA架構，透過 GPU運算提升整體分析效能；6) 提供多種前後處理的方式，讓分析模型建立更為方便及分析結果輸出的呈現；且藉由物件導向設計模式的架構設計優勢，讓上述所函蓋的演算法可容易的擴充與實現相關類別。
    本研究中剖析了ESFM分析效能，對整體分析效能提出改善及提升運算效率的建議，並對二維及三維模型分析進行多種組合的驗證及多種模型的測試，已確保ESFM軟體架構的品質及高效能分析能力。

    This research describes an Essential Software Framework for Meshfree Methods (ESFM). Through integrated many existing meshfree methods and identified their common elements and procedures, ESFM can flexible implement existing meshfree methods or new algorithms, and accelerate new developments in meshfree methods. ESFM also modulates performance-critical components such as neighbor-point searching, sparse-matrix storage, sparse-matrix solver, etc., enabling developed meshfree analysis programs to achieve high-performance. By using object-oriented design, ESFM can be flexibly implemented using meshfree methods, finite element methods, or hybrid of these two methods. Finally, ESFM provides a common ground to compare various meshfree methods, enabling detailed analyses of performance characteristics.

    論文摘要 I ABSTRACT III 誌 謝 V 目 錄 VII 圖 目 錄 XI 表 目 錄 XV 第一章 緒論 1 1.1研究背景與目的 1 1.2論文架構 2 第二章 文獻回顧 3 2.1 無元素分析法 3 2.2混合式運算之研究 9 2.3 耦合分析 12 2.4 物件導向設計模式及軟體架構 14 2.5 小結 15 第三章 研究方法 19 3.1 研究架構 19 3.1.1 軟體架構 20 3.1.2 數值分析方法 22 3.1.3 加速運算 23 3.1.4 案例分析 27 3.1.5 格式處理 30 3.2 Weak-form無元素分析法通用分析流程 30 3.2.1 線彈性問題分析流程 30 3.2.2 非線性問題分析流程 33 3.3 Weak-form無元素法基礎要素 35 3.3.1 近似函數 (approximation function) 37 3.3.2 支撐領域 (support domain) 40 3.3.3 本質邊界條件 (essential boundary condition) 40 3.3.4 領域積分方法 (domain integration method) 40 3.4 無元素法效能相關數值方法 41 3.4.1 搜尋演算法 (search algorithm) 41 3.4.2 稀疏矩陣存取 (sparse matrix storage) 42 3.4.3 稀疏矩陣資料排序 (ordering) 42 3.4.4 系統方程式求解器 (solver) 43 3.5 小結 43 第四章 ESFM軟體架構 45 4.1 ESFM架構設計 45 4.1.1 Model classes群組 49 4.1.2 Domain classes群組 51 4.1.3 Formulation class群組 53 4.1.4 系統介面類別 57 4.2耦合系統 58 4.2 ESFM主要操作程序 62 4.2.1 主要分析程序 62 4.2.2 初始化程序 63 4.2.3 Formulation程序 66 4.2.4 耦合程序 67 4.3 小結 69 第五章 系統驗證 71 5.1 RPIM無元素法 71 5.2 線彈性分析驗證 72 5.2.1 二維懸臂梁模型驗證 72 5.2.2 二維線荷重模型驗證 75 5.2.3 三維點荷重模型驗證 77 5.3 非線性分析驗證 80 5.3.1 二維線荷重模型驗證 81 5.3.2 三維點荷重模型驗證 82 5.4 線彈性耦合分析驗證 85 5.4.1 二維懸臂梁模型驗證 85 5.4.2 二維線荷重模型驗證 89 5.4.3 三維點荷重模型驗證 93 第六章 ESFM效能評估 97 6.1 整體效能評估 97 6.1.1 二維度案例說明 98 6.1.2 二維度效能評估 100 6.1.3 三維度案例說明 101 6.1.4 三維度效能評估 102 6.2稀疏矩陣效能探討 104 6.2.1 二維度效能評估 105 6.2.2 三維度效能評估 107 6.3 小結 108 第七章 GPU加速運算演算法 109 7.1 ESFM混合式運算之架構 109 7.2 CUDA加速組合整體勁度矩陣效能探討 111 7.2.1 CRABS稀疏矩陣格式 112 7.2.2 CUDA加速CRABS策略 113 7.2.3 CUDA加速CRABS效能評估 116 7.3 使用CUDA加速PCG SSOR疊代求解演算法 120 7.3.1 CUDA加速PCG疊代求解演算法 120 7.3.2 SSOR preconditioner 123 7.3.3 CUDA加速SSOR preconditioner演算法 124 7.3.4 CUDA加速密三角矩陣系統方程式求解 126 7.4 使用混合式運算加速ESFM分析之效能評估 129 7.4.1二維懸臂梁模型混合式運算效能評估 130 7.4.2 二維線荷重模型混合式運算效能評估 133 7.4.3 三維點荷重模型混合式運算效能評估 136 7.5 小結 140 第八章 結論與建議 141 參考文獻 143

    1. Gu, Y.T., Meshfree methods and their comparisons. International Journal of Computational Methods, 2005. 2(4): p. 477-515.
    2. Li, S. and W.K. Liu, Meshfree and particle methods and their applications. Applied Mechanics Reviews, 2002. 55(1): p. 1-34.
    3. Belytschko, T., et al., Meshless methods: An overview and recent developments. Computer Methods in Applied Mechanics and Engineering, 1996. 139(1-4): p. 3-47.
    4. Lucy, L.B., A numerical approach to the testing of the fission hypothesis. Astrophysical Journal, 1997. 82: p. 1013-1024.
    5. Fernandez-Mendez, S. and A. Huerta, Imposing essential boundary conditions in mesh-free methods. Computer Methods in Applied Mechanics and Engineering, 2004. 193(12-14): p. 1257-1275.
    6. Swegle, J.W., D.L. Hicks, and S.W. Attaway, Smoothed Particle Hydrodynamics Stability Analysis. Journal of Computational Physics, 1995. 116(1): p. 123-134.
    7. Liu, W.K., S. Jun, and Y.F. Zhang, Reproducing Kernel Particle Methods. International Journal for Numerical Methods in Fluids, 1995. 20(8-9): p. 1081-1106.
    8. Belytschko, T., L. Gu, and Y.Y. Lu, Fracture and crack growth by element free Galerkin methods. Modelling and Simulation in Materials Science and Engineering, 1994. 2(3 A): p. 519-534.
    9. B, N., T. G, and V. P, Generalizing the finite element method: diffuse approximation and diffuse elements. Computational Mechanics, 1992. 10: p. 307-318.
    10. Babuška, I. and J.M. Melenk, The partition of unity method. International Journal for Numerical Methods in Engineering, 1997. 40(4): p. 727-758.
    11. Duarte, C.A. and J.T. Oden, Hp clouds-a meshless method to solve boundary-value problems, in Technical Report 95-05. 1995: Texas Institute for Computational and Applied Mathematics, University of Texas at Austin.
    12. Liu, W.K., S.F. Li, and T. Belytschko, Moving least-square reproducing kernel methods .1. Methodology and convergence. Computer Methods in Applied Mechanics and Engineering, 1997. 143(1-2): p. 113-154.
    13. Attaway, S.W., M.W. Heinstein, and J.W. Swegle, Coupling of Smooth Particle Hydrodynamics with the Finite-Element Method. Nuclear Engineering and Design, 1994. 150(2-3): p. 199-205.
    14. Belytschko, T., D. Organ, and Y. Krongauz, A coupled finite element - Element-free Galerkin method. Computational Mechanics, 1995. 17(3): p. 186-195.
    15. Johnson, G.R., Linking Lagrangian particle model for nucleation of solid-solid phase transformations. Modeling Simulations in Materials Science and Engineering, 1995. 3: p. 455-471.
    16. Liu, W.K., R.A. Uras, and Y. Chen, Enrichment of the finite element method with the reproducing kernel particle method. Journal of Applied Mechanics-Transactions of the Asme, 1997. 64(4): p. 861-870.
    17. Karutz, H., R. Chudoba, and W.B. Kratzig, Automatic adaptive generation of a coupled finite element/element-free Galerkin discretization. Finite Elements in Analysis and Design, 2002. 38(11): p. 1075-1091.
    18. Li, G., G.H. Paulino, and N.R. Aluru, Coupling of the mesh-free finite cloud method with the boundary element method: a collocation approach. Computer Methods in Applied Mechanics and Engineering, 2003. 192(20-21): p. 2355-2375.
    19. Wu, C.T., et al., Lagrangian meshfree formulation for analysis of geotechnical materials. Journal of Engineering Mechanics-Asce, 2001. 127(5): p. 440-449.
    20. Zhang, J.F., W.P. Zhang, and Y. Zheng, A Meshfree Method and Its Applications to Elasto-Plastic Problems. Journal of Zhejiang University (Science), 2005. 6A(2): p. 148-154.
    21. Liu, W.K., et al., Reproducing Kernel Particle Methods for Structural Dynamics. International Journal for Numerical Methods in Engineering, 1995. 38(10): p. 1655-1679.
    22. Plotzitza, A., T. Rabczuk, and J. Eibl, Techniques for numerical simulations of concrete slabs for demolishing by blasting. Journal of Engineering Mechanics-Asce, 2007. 133(5): p. 523-533.
    23. Dilts, G.A., Moving-Least-Squares-particle hydrodynamics - I. Consistency and stability. International Journal for Numerical Methods in Engineering, 1999. 44(8): p. 1115-1155.
    24. Rabczuk, T. and T. Belytschko, A three-dimensional large deformation meshfree method for arbitrary evolving cracks. Computer Methods in Applied Mechanics and Engineering, 2007. 196(29-30): p. 2777-2799.
    25. Sheu, G.Y., Direct back analysis by the meshless local Petrov-Galerkin method and Bayesian statistics. International Journal for Numerical and Analytical Methods in Geomechanics, 2006. 30(8): p. 823-842.
    26. Atluri, S.N. and T. Zhu, A new Meshless Local Petrov-Galerkin (MLPG) approach in computational mechanics. Computational Mechanics, 1998. 22(2): p. 117-127.
    27. Lim, Y.J. and S. De, Real time simulation of nonlinear tissue response in virtual surgery using the point collocation-based method of finite spheres. Computer Methods in Applied Mechanics and Engineering, 2007. 196(31-32): p. 3011-3024.
    28. Ionescu, I., et al., Simulation of soft tissue failure using the material point method. Journal of Biomechanical Engineering-Transactions of the Asme, 2006. 128(6): p. 917-924.
    29. Doblare, M., et al., On the employ of meshless methods in biomechanics. Computer Methods in Applied Mechanics and Engineering, 2005. 194(6-8): p. 801-821.
    30. Liew, K.M., J. Ren, and J.N. Reddy, Numerical simulation of thermomechanical behaviours of shape memory alloys via a non-linear mesh-free Galerkin formulation. International Journal for Numerical Methods in Engineering, 2005. 63(7): p. 1014-1040.
    31. Ishii, T., K. Terada, and T. Kyoya, Failure analysis of quasi-brittle materials involving multiple mechanisms on fractured surfaces. International Journal for Numerical Methods in Engineering, 2006. 67(7): p. 960-988.
    32. Song, J.H., P.M.A. Areias, and T. Belytschko, A method for dynamic crack and shear band propagation with phantom nodes. International Journal for Numerical Methods in Engineering, 2006. 67(6): p. 868-893.
    33. Rabczuk, T., P.M.A. Areias, and T. Belytschko, A simplified mesh-free method for shear bands with cohesive surfaces. International Journal for Numerical Methods in Engineering, 2007. 69(5): p. 993-1021.
    34. Kim, N.H., K.K. Choi, and J.S. Chen, Die shape design optimization of sheet metal stamping process using meshfree method. International Journal for Numerical Methods in Engineering, 2001. 51(12): p. 1385-1405.
    35. Yoon, S. and J.S. Chen, Accelerated meshfree method for metal forming simulation. Finite Elements in Analysis and Design, 2002. 38(10): p. 937-948.
    36. Kwon, K.C., S.H. Park, and S.K. Youn, The least-squares meshfree method for elasto-plasticity and its application to metal forming analysis. International Journal for Numerical Methods in Engineering, 2005. 64(6): p. 751-788.
    37. Alfaro, I., et al., Meshless methods with application to metal forming. Computer Methods in Applied Mechanics and Engineering, 2006. 195(48-49): p. 6661-6675.
    38. Lacroix, D. and P. Bouillard, Improved sensitivity analysis by a coupled FE-EFG method. Computers & Structures, 2003. 81(26-27): p. 2431-2439.
    39. Zou, W., et al., A truly meshless method based on partition of unity quadrature for shape optimization of continua. Computational Mechanics, 2007. 39(4): p. 357-365.
    40. Divo, E. and A.J. Kassab, An efficient localized radial basis function meshless method for fluid flow and conjugate heat transfer. Journal of Heat Transfer-Transactions of the Asme, 2007. 129(2): p. 124-136.
    41. Hu, N., et al., The partition of unity finite element method for elastic wave propagation in Reissner-Mindlin plates. International Journal for Numerical Methods in Engineering, 2007. 70(12): p. 1451-1479.
    42. Liu, G.R., Mesh free methods: Moving beyond the finite element method. 2003, Boca Raton: CRC Press. 693.
    43. IBM Roadrunner, http://en.wikipedia.org/wiki/IBM_Roadrunner, Wikipedia
    44. Top 500 Lists November 2013, http://www.top500.org/lists/2013/11/#.U4sfbfmSx8E. [cited 2013; Available from: http://www.top500.org/lists/2013/11/#.U4sfbfmSx8E.
    45. Cederman, D. and P. Tsigas, A Practical Quicksort Algorithm for Graphics Processors. Algorithms - Esa 2008, 2008. 5193: p. 246-258.
    46. Garcia, V., E. Debreuve, and M. Barlaud, Fast k Nearest Neighbor Search using GPU. 2008 Ieee Computer Society Conference on Computer Vision and Pattern Recognition Workshops, Vols 1-3, 2008: p. 1107-1112.
    47. Catanzaro, B., N. Sundaram, and K. Keutzer, Fast Support Vector Machine Training and Classification, in Proceedings of the 25th international conference on Machine learning. 2008. p. 104-111.
    48. Rueda, A.J. and L. Ortega, Geometric algorithms on CUDA. Grapp 2008: Proceedings of the Third International Conference on Computer Graphics Theory and Applications, 2008: p. 107-112.
    49. Cecka, C., A.J. Lew, and E. Darve, Assembly of finite element methods on graphics processors. International Journal for Numerical Methods in Engineering, 2011. 85(5): p. 640-669.
    50. Kakay, A., E. Westphal, and R. Hertel, Multiple-GPU accelerated FEM micromagnetic simulations. IEEE Transactions on Magnetics, 2010. 46: p. 2303.
    51. Nakata, S., et al., Parallel Algorithm for Meshfree Radial Point Interpolation Method on Graphics Hardware. Ieee Transactions on Magnetics, 2011. 47(5): p. 1206-1209.
    52. Gui, Y. and G. Zhang, An Improved Implementation of Preconditioned Conjugate Gradient Method on GPU. Journal of Software, 2012. 7(12): p. 2695-2702.
    53. Hogg, J.D., A Fast Dense Triangular Solve in Cuda. Siam Journal on Scientific Computing, 2013. 35(3): p. C303-C322.
    54. NVIDIA, CUSPARSE LIBRARY v6.5 2014.
    55. PARALUTION, http://www.paralution.com/documentation/, 2014.
    56. Tian, R. and G. Yagawa, Non-matching mesh gluing by meshless interpolation - An alternative to Lagrange multipliers. International Journal for Numerical Methods in Engineering, 2007. 71(4): p. 473-503.
    57. Tsai, H.C. and C.P. Pan, Element free formulation used for connecting domain boundaries. Journal of the Chinese Institute of Engineers, 2004. 27(4): p. 585-596.
    58. 林建勳, 元素釋放法與有限元素法之聯合應用, 博士論文, 國立臺灣科技大學營建工程系, in 國立臺灣科技大學營建工程. 2006.
    59. Baugh, J.W., Jr. and D.R. Rehak, Object-oriented design of finite element programs. Computers & Structures, 1989: p. 91-100.
    60. Kong, X.A. and D.P. Chen, An object-oriented design of FEM programs. Computers and Structures, 1995. 57(1): p. 157-166.
    61. Archer, G.C., G. Fenves, and C. Thewalt, A new object-oriented finite element analysis program architecture. Computers and Structures, 1999. 70(1): p. 63-75.
    62. Patzak, B. and Z. Bittnar, Design of object oriented finite element code. Advances in Engineering Software, 2001. 32(10-11): p. 759-767.
    63. Heng, B.C.P. and R.I. Mackie, Using design patterns in object-oriented finite element programming. Computers & Structures, 2009. 87(15-16): p. 952-961.
    64. Foote, B., A fractal model of the lifecycles of reusable objects, in OOPSLA ’92 Workshop on Reuse. 1992: Vancouver, British, Columbia, Canada.
    65. Gamma, E., et al., Design patterns: Elements of reusable object-oriented software. 34 ed. 2007, Massachusetts, MA, USA: Addison-Wesley.
    66. Freeman, E.T., et al., Head first design patterns. 2004, Sebastopol, CA, USA: O'Reilly Media.
    67. Yang, C.T. and S.H. Hsieh, An object-oriented framework for versatile discrete objects simulation using design patterns. Computational Mechanics, 2005. 36(2): p. 85-99.
    68. Liu, G.R. and Y.T. Gu, An introduction to meshfree methods and their programming. 2005, Dordrecht, The Netherlands: Springer. 479.
    69. Galoppo, N., et al., LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware, in Proceedings of the ACM/IEEE SC|05 Conference. 2005.
    70. NVIDIA, CUDA Programming Guide v6.5 2014.
    71. Belytschko, T., Y.Y. Lu, and L. Gu, Element-free Galerkin methods. International Journal for Numerical Methods in Engineering, 1994. 37(2): p. 229-256.
    72. Lu, Y.Y., T. Belytschko, and L. Gu, A new implementation of the element free Galerkin method. Computer Methods in Applied Mechanics and Engineering, 1994. 113(3-4): p. 397-414.
    73. Liu, G.R. and Y.T. Gu, A point interpolation method for two-dimensional solids. International Journal for Numerical Methods in Engineering, 2001. 50(4): p. 937-951.
    74. Wang, J.G. and G.R. Liu, A point interpolation meshless method based on radial basis functions. International Journal for Numerical Methods in Engineering, 2002. 54(11): p. 1623-1648.
    75. Berg, M.d., et al., Computational geometry: Algorithms and applications. 2008, New York: Springer. 386.
    76. ABAQUS, Abaqus Analysis User's Guide 6.13, http://50.16.176.52/v6.13/books/usb/default.php.
    77. Nguyen, V.P., et al., Meshless methods: A review and computer implementation aspects. Mathematics and Computers in Simulation, 2008. 79(3): p. 763-813.
    78. Fries, T.P. and H.G. Matthies, Classification and overview of meshfree methods. 2004: Brunswick, Germany.
    79. Puso, M.A., et al., Meshfree and finite element nodal integration methods. International Journal for Numerical Methods in Engineering, 2008. 74(3): p. 416-446.
    80. Liu, G.R., et al., A nodal integration technique for meshfree radial point interpolation method (NI-RPIM). International Journal of Solids and Structures, 2007. 44(11-12): p. 3840-3860.
    81. Puso, M.A. and J. Solberg, A stabilized nodally integrated tetrahedral. International Journal for Numerical Methods in Engineering, 2006. 67(6): p. 841-867.
    82. Zhou, J.X., et al., A nodal integration and post-processing technique based on Voronoi diagram for Galerkin meshless methods. Computer Methods in Applied Mechanics and Engineering, 2003. 192(35-36): p. 3831-3843.
    83. Chen, J.S., et al., A stabilized conforming nodal integration for Galerkin mesh-free methods. International Journal for Numerical Methods in Engineering, 2001. 50(2): p. 435-466.
    84. Perkins, E. and J.R. Williams, A fast contact detection algorithm insensitive to object sizes. Engineering Computations (Swansea, Wales), 2001. 18(1-2): p. 48-61.
    85. Bentley, J.L., Multidimensional binary search trees used for associative searching. Communications of the ACM, 1975. 18(9): p. 509-517.
    86. Sherman, A.H., On the efficient solution of sparse systems of linear and nonlinear equations. 1975, Yale University: New Haven, CT, USA. p. 207.
    87. George, A. and J.W.H. Liu, Computer solutions of large sparse positive definite systems. 1981, Englewood Cliffs, NJ: Prentice Hall. 208.
    88. Jennings, A., A compact storage scheme for the solution of symmetric linear simultaneous equations. 1966. 9: p. 281-285.
    89. Liu, W.-H. and A.H. Sherman, Comparative analysis of the Cuthill-McKEE and the reverse Cuthill-McKEE ordering algorithms for sparse matrices. Siam Journal on Numerical Analysis, 1976. 13(2): p. 198-213.
    90. Sloan, S.W., Algorithm for profile and wavefront reduction of sparse matrices. International Journal for Numerical Methods in Engineering, 1986. 23(2): p. 239-251.
    91. Saad, Y., Iterative methods for sparse linear systems. 2 ed. 2003, Philadelphia, USA: Society for Industrial and Applied Mathematics. 528.
    92. Miles, R. and K. Hamilton, Learning UML 2.0. 2006: O'Reilly.
    93. Booch, G., J. Rumbaugh, and I. Jacobson, Unified modeling language user guide, the (2nd Edition). 2005: Addison-Wesley. 496.
    94. Schenk, O., et al., PARDISO: A high-performance serial and parallel sparse linear solver in semiconductor device simulation. Future Generation Computer Systems, 2001. 18(1): p. 69-78.
    95. Demmel, J.W., et al., A supernodal approach to sparse partial pivoting. SIAM Journal on Matrix Analysis and Applications, 1999. 20(3): p. 720-755.
    96. Davis, T.A., Algorithm 832: UMFPACK V4.3 - An unsymmetric-pattern multifrontal method. Acm Transactions on Mathematical Software, 2004. 30(2): p. 196-199.
    97. CULA Tools, http://www.culatools.com/, 2015.
    98. CUSP, https://developer.nvidia.com/cusp, NVIDIA 2015.
    99. Hsieh, Y.M. and M.S. Pan, Efficient assembly of global stiffness matrix in meshfree methods through a new data structure - compressed row adaptive block storage scheme. 2011.

    QR CODE