基於單側雅可比演算法於CUDA計算機實現平行矩陣特徵值分解

One-Sided Jacobi Algorithm based on CUDA Computer for Parallel Eigenvalue Decomposition

宋啟嘉(Chi-Chia Sun) ； 胡逸秀(Yi-Siou Hu)

《中正嶺學報》 45卷2期 (2016/11) Pp. 113-120

摘要

本文提出基於單側雅可比演算法實現於支援平行編譯與計算平台（CUDA）達到硬體加速優化。在現今的計算系統中，由於單一個CPU的核心效能已經漸漸達到硬體上的限制，而GPU計算加速架構的優勢在於它本身固有的平行特徵，故在多核心平行計算的環境之下更能突顯其優勢。另一方面，特徵值分解（EVD）在通訊系統中長期扮演著一個非常重要的角色，因為在通訊系統中常以矩陣特徵值作為訊號通道判斷的依據，故實現平行特徵值分解計算有其重要性。經由實現平行單側雅可比演算法於CUDA計算機後，由於單側雅可比演算法本身簡單、快速收斂以及固有的平行特徵，使輸入之對稱矩陣能夠經過連續疊代計算分解為特徵值與特徵向量，最後實驗結果顯示本文所提出的單側雅可比演算法於CUDA計算機上之效能與傳統循環雅可比演算法比較，其計算速度快近102～103倍之多。

關鍵字

平行矩陣特徵值分解 ； GPU計算 ； 單側雅可比演算法 ； CUDA

並列摘要

In this paper, One-Sided Jacobi algorithm is optimized on the Graphics Processing Unit (GPU) for hardware acceleration using Compute Unified Device Architecture (CUDA) computer. In modern computation systems, due to the fact that the performance of a single CPU core has already reached its limitation, the architecture of GPU with many cores is advantageous in its inherent parallel features and extremely fast computation time. In order to realize high performance parallel Eigenvalue Decomposition (EVD) on the CUDA computer, One-Sided Jacobi parallel algorithm is selected, due to its simple, strong convergence and inherent parallel features. It can factorize the input symmetric matrix into eigenvalues and eigenvectors iteratively. Finally, the experimental results show that the performance of the proposed One-Sided Jacobi Method using CUDA hardware accelerator is improved to 102~103 times faster than the conventional Cycle-by-Row Jacobi algorithm.

並列關鍵字

Parallel EVD ； GPU Computing ； One-side Jacobi algorithm ； CUDA