進階搜尋


 
系統識別號 U0026-0508201611153700
論文名稱(中文) 在GPU架構下GMRes演算法的數值實現
論文名稱(英文) Numerical Implementation of GMRes Algorithm on the GPU Architecture
校院名稱 成功大學
系所名稱(中) 數學系應用數學碩博士班
系所名稱(英) Department of Mathematics
學年度 104
學期 2
出版年 105
研究生(中文) 許雁棋
研究生(英文) Yen-Chi Hsu
學號 L16024054
學位類別 碩士
語文別 英文
論文頁數 22頁
口試委員 指導教授-王辰樹
共同指導教授-陳旻宏
口試委員-黃聰明
口試委員-黃印良
中文關鍵字 廣義最小殘量方法  平行計算  預處理 
英文關鍵字 GMRes  parallel computing  precondition 
學科別分類
中文摘要 在本文中,我們提出了一個快速的線性系統解,用以解偏微分方程。此偏微分方程主要由Poisson方程的變形以及Dirichlet邊界條件所組成的。我們使用preconditioned generalized minimal residual iterative method(通常簡稱GMRes)作為線性系統的主要算法以及使用fast Poisson solver作預處理。
為了加速運算的性能,我們利用GPU來進行GMRes的平行計算。此計算平台,CPU為I7-4770,記憶體為8G,而GPU則是Nvidia GTX Titian Black。數值實現結果顯示,相較於單核心CPU計算,利用GPU做平行計算可以取得14倍左右的加速效能,而測試矩陣的大小為2的13次方乘以2的13次方。計算結果得出的結論為,GPU的計算具有有效性以及可擴展性。
英文摘要 In this paper, we propose a fast linear system solver for the numerical solutions to partial differential equations mainly consisting of Poisson’s equation with Dirichlet boundary conditions. We pick up the preconditioned generalized minimal residual iterative method (usually abbreviated GMRes) to be linear system solver and the fast
Poisson solver to be the preconditioner.
In order to speed up the computation performance, we implement parallel computing of the GMRes algorithm on the GPU architecture. Our computing platform, CPU is I7 - 4770, RAM is 8G, and GPU is Nvidia GTX TITAN Black. The numerical implementation of the linear system solver for solving the partial differential equation shows that the performance on GPU architecture is about 14 times faster than that on non-parallel architecture for the case of test matrices of sizes 2^13-by-2^13. The numerical results conclude that the GPU computing is efficient and scalable.
論文目次 1. Introduction ...1
2. Poisson Solver ...3
2.1 Poisson's equation ...3
2.2 Statment of the equation ...3
2.3 Finite Difference Discretization ...4
2.4 Fast Solver ...5
2.5 Algorithm ...6
3. GMRes ...7
3.1 Generalized Minimal Residual Method ...7
3.2 The method ...7
3.3 Solving the least squares problem ...9
3.4 Algorithm ...11
4. Numerical Experiments and Conclusion Remarks ...12
4.1 Basic Linear Algebra Subprograms (BLAS) ...12
4.2 Fast Poisson Solver ...17
4.3 GMRes ...18
References ...21
參考文獻 [1] A.S.L.Shieh. Numer.Math.. Springer-Verlag 1979, 1978.
[2] A. Hyvarinen. Fast and robust fixed-point algorithms for independent component
analysis. IEEE Computational Intelligence Society, pp. 626-634, 2002.
[3] D. Calvetti, J. Petersen, L. Reichel. A parallel implementation of the GMRes
method in Numerical Linear Algebra. L. Reichel, A. Ruttan and R. S. Varga, de
Gruyter, Berlin, pp. 31-45, 1993.
[4] F. Bodin, J. Erhel, T. Priol. Parallel sparse matrix vector multiplication using a
shared virtual memory environment. Sixth SIAM Conference on Parallel Processing
for Scientific Computing. R. F. Sincovec, D. E. Keyes, M. R. Leuze, L. R. Petzold,
D. A. Reed, SIAM, Philadelphia, pp. 421-428, 1993.
[5] H. F. Walker. Implementation of the GMRes method using Householder transformations.
SIAM J. Sci. Stat. Comput., pp. 152-163, 1988.
[6] James Demmel. Applied Numerical Linear Algebra. 1996.
[7] Jocelyne Erhel. A parallel GMRes version for general sparse matrices. Electronic
Transactions on Numerical Analysis, 1998.
[8] Kendall E.Atkinson, Weimin Han. Elementary Numerical Analysis Third Edition.
John Wiley and Sons, Inc., pp. 451-490, 2004.
[9] Lloyd N. Trefethen, David Bau. Numerical Linear Algebra. Society for Industrial
and Apllied Mathematics, pp. 266-275, 313-320, 1997.
[10] William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery.
Numerical Recipes. Cambridge University Press, 1988
[11] Rudnei Dias da Cunha. A parallel implementation of the restarted GMRes iterative
algorithm for non-symmetric systems of linear equations. Advances in Computational
Mathematics, 1994, pp. 261-277.
[12] Roberto Toscano Couto. Green’s functions for the wave, Helmholtz and Poisson
equations in a two-dimensional boundless domain. 2013.
[13] CUDA Toolkit Documentation,
http://docs.nvidia.com/cuda/
[14] FFTW,
http://www.fftw.org/
[15] Geforce GTX Titan Black,
http://www.geforce.com.tw/hardware/desktop-gpus/geforce-gtx-titanblack
[16] LAPACK-Linear Algebra PACKage,
http://www.netlib.org/lapack/
[17] Laplace operator,
https://en.wikipedia.org/wiki/Laplace-operator
[18] PGI Compilers and Tools,
http://www.pgroup.com/index.htm
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2016-08-08起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2016-08-08起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw