本研究旨在利用近期發展之圖形處理單元(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.