淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2308201215403700
中文論文名稱 對稱正定矩陣Cholesky分解之GPU加速研究
英文論文名稱 GPU-based Cholesky decomposition for symmetric positive definite matrices
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 100
學期 2
出版年 101
研究生中文姓名 吳博雋
研究生英文姓名 Bo-Jun Wu
學號 698631479
學位類別 碩士
語文別 中文
口試日期 2012-05-26
論文頁數 38頁
口試委員 指導教授-魏世杰
委員-廖賀田
委員-陳永昇
中文關鍵字 Cholesky分解  圖形處理單元(GPU)  Intel數學核心函式庫(MKL) 
英文關鍵字 Cholesky Decomposition  Graphics Processing Units  Intel Math Kernel Library 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 本研究旨在利用近期發展之圖形處理單元(GPU)硬體,提昇特定矩陣運算之效能。在求解線性最小平方差問題中,常需要計算共變異矩陣之反矩陣。這時利用共變異矩陣滿足對稱正定矩陣之特性,求解過程可使用Cholesky分解,其相較於適用一般矩陣之LU分解,速度還快上一倍。近年來隨著技術進步,一片圖形卡中常可置入數百核作運算,相較於CPU之少數8核或16核,若能將圖形卡視為一般用途圖形處理單元(GPGPU),將可加速執行一般可平行化運算。目前文獻中已有許多矩陣運算平行化之研究,本文將針對求對稱正定矩陣逆運算常用之Cholesky分解,找尋現有網路上公開之GPU實作原始碼,分析其結構,評比其表現,並提出改良方法。經過測試,相較於純CPU執行之Intel數學核心函式庫(Math Kernel Library,MKL)版本,本文改良法可透過GPU提昇維度10000方陣之Cholesky分解速度達3.5倍快程度。
英文摘要 This work aims to apply the recently developed Graphics Processing Unit (GPU) to performance enhancement of a specific matrix operation. When solving the linear least squares problem, it is often necessary to compute the inverse of a covariance matrix. As the covariance matrix satisfies the condition of a symmetric positive definite matrix, the Cholesky decomposition can be used which is twice as fast as the LU decomposition on general matrices. In recent years, with the advances in technology, a graphics card can accommodate hundreds of cores compared to the small number of 8 or 16 cores on CPU. Therefore a trend is seen to use the graphics card as a general purpose graphics processing unit (GPGPU) for parallel computation. There are already many works on parallel matrix operations in the literature. This work will focus on the Cholesky decomposition commonly used in computing the inverse of a symmetric positive definite matrix. First, several open source GPU-based Cholesky decomposition programs on the Internet were located, analyzed, and evaluated. Then several strategies for performance improvement were proposed and tested. After experiments, compared to the CPU version using the Intel Math Kernel Library (MKL), our proposed GPU improvement strategy can achieve a speedup of 3.5x on the Cholesky decomposition of a square matrix of dimension 10,000.
論文目次 目錄
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目標 3
1.3 研究架構 3
第二章 文獻探討 4
2.1 反矩陣 4
2.1.1 LU分解 4
2.1.2 QR分解 5
2.1.3 奇異值分解(SVD) 5
2.1.4 Cholesky分解 5
2.2 BLAS函式庫 6
2.2.1 GEMM(GEneral Matrix Multiplication) 6
2.2.2 SYRK(SYmmetrix Rank K update) 6
2.2.3 TRSM(TRiangular Solve Multiple) 7
2.3 LAPACK函式庫 7
2.4 矩陣乘法之時間複雜度 7
2.5 圖形處理器 8
2.5.1 OpenCL 8
2.5.2 CUDA 9
2.6 運用GPU之數值函式庫 9
第三章 研究方法與目前作法分析 10
3.1研究方法 10
3.2目前作法分析 10
3.2.1 Bouckaert版本 11
3.2.2 Volkov版本 14
3.2.3 Henry版本 14
3.2.4 MAGMA版本 15
3.2.5 各版本差異分析 18
第四章 改進與測試 19
4.1 測試平台 19
4.2 改進方案 21
4.2.1 改進方案1:MKL函式庫之使用 21
4.2.2 改進方案2:區塊大小 23
4.2.3 最佳區塊大小 25
4.3 相關考量 28
4.3.1 誤差值 28
4.3.2 MAGMA版本特定矩陣維度較佳原因 30
4.3.3 CPU緒數影響 32
4.3.4 不同平台改進方案有效性 33
第五章 結論與未來發展 35

圖目錄
圖1 Bouckaert版本區塊Cholesky分解之演算法圖解 13
圖2 Henry版本區塊Cholesky分解之演算法圖解 15
圖3 MAGMA 版本區塊 Cholesky 分解之演算法圖解 17
圖4 整合各版本程式後之Cholesky分解原始加速比 21
圖5 Bouckaert 版本使用MKL函式庫後之Cholesky分解加速比 22
圖6 Bouckaert_MKL版本之區塊大小修改為64後之加速比 24
圖7 區塊大小統一為MAGMA版本給法後之加速比 25
圖8 各眾數值下之時間差總和與區塊差總和 27
圖9以周圍360×2個樣本之眾數作平滑化下之矩陣維度1000至3000之建議區塊大小 28
圖10 於另一GPU平台實驗最後結果之加速比 35

表目錄
表1:各版本四種函式所使用之核心(+:CPU使用 MKL 函式庫,*:GPU使用 CUBLAS 函式庫) 18
表2:整合各版本程式後之原始時間比較表 20
表3:Bouckaert版本使用MKL函式庫後之Cholesky分解時間比較表 22
表4:Bouckaert_MKL版本之區塊大小修改為64後之Cholesky分解時間比較表 23
表5:區塊大小統一為MAGMA版本給法後之Cholesky分解時間比較表 24
表6:Volkov版本矩陣維度1000至10000時不同區塊之運算時間表 26
表7:單精度與雙精度之誤差比較表 29
表8:MAGMA版本各步驟所花費之時間表(*為原本使用之區塊) 31
表9:MAGMA版本矩陣維度7000至9000,間距100各步驟所花費之時間表 32
表10:各版本於維度10000時不同CPU緒數之Cholesky分解時間表 33
表11:於另一GPU平台實驗最後改進結果之時間比較表 34
參考文獻 [1] 維基百科, <維基百科,自由的百科全書>,網址:http://zh.wikipedia.org/wiki/Wikipedia:%E9%A6%96%E9%A1%B5,上網日期:2012年2月15日。
[2] David B. Kirk, and Wen-mei W. Hwu, Programming Massively Parallel Processors, United States of America, ISBN: 978-0-12-381472-2, 2010.
[3] Gene H. Golub, and Charles F. Van Loan, Matrix Computations, Third Edition, The Johns Hopkins University Press, 1996.
[4] Hatem Ltaief, Stanimire Tomov, Rajib Nath, and Jack Dongarra, "Hybrid Multicore Cholesky Factorization with Multiple GPU Accelerators."
http://icl.cs.utk.edu/news_pub/submissions/tile_magma_journal.pdf, accessed 2011/10/22.
[5] IntelR, IntelR Math Kernel Library Documentation.
http://software.intel.com/en-us/articles/intel-math-kernel-library-documentation/, accessed 2012/2/11.
[6] Jason Sanders, and Edward Kandrot, Cuda by Example- an Introduction to General-Purpose GPU Programming, Addiaon-Wesley, July 2010.
[7] MAGMA, Matrix Algebra on GPU and Multicore Architectures.
http://icl.cs.utk.edu/magma/software/index.html, accessed 2011/11/18.
[8] Remco R. Bouckaert, Matrix inverse with CUDA and Cublas.
http://www.cs.waikato.ac.nz/~remco/gpuinvert.tgz, accessed 2011/10/22.
[9] Sylvain Henry, “Parallelizing Cholesky’s decomposition algorithm”, December 2009.
http://runtime.bordeaux.inria.fr/shenry/papers/HS_Cholesky.pdf, accessed 2011/11/14.
[10] V. Volkov, and J. W. Demmel, LU, QR and Cholesky Factorizations code using GPU - NVIDIA Forums.
http://forums.nvidia.com/index.php?s=2ddda4cd645b67253d127c878d2e45a2&app=core&module=attach§ion=attach&attach_id=11052, accessed 2011/10/22.
[11] William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery, Numerical Recipes in C - The Art of Scientific Computing, 2nd Edition, Cambridge University Press, 1992.
[12] NVIDIA Corporation, CUDA Toolkit 4.0 CUBLAS Library, February 2011.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-08-30公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-08-30起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信