圖形處理器上的內迭代不精確和混合精度特徵值解法

Abstract

特徵值問題是現今工程及科學計算領域中最重要的議題之一,在實際 應用中,解決特徵值問題所需的計算量相當龐大, 因此高效能計算(High Performance Computing, HPC)在此扮演著重要的角色, 其中一有效之方法 是運用混合精度以達到更高的效能,也就是在適當的時機使用較低的精度計 算,並且不影響最後計算的精度。 單精度所需的記憶體容量較小,因此有較 大的可能性可造成高速緩存命中(cache hit),其往往影響最終效能顯著。 除 此之外,許多運算以單精度皆可獲得較高的效能。因此如果原本的演算法就 有較高的精度容忍程度,若重新設該演算法 將有機會運用混合精度的方法達 到更高的效能。而我們專注的演算法既屬於此種類型。 Shift-Invert Residual Arnoldi (SIRA)演算法為計算特徵值的重要方法, 該演算法由內外迭代迴圈 所組成,其中內迴圈為求解線性系統的過程,其目的在於計算修正方向, 以 幫助外迴圈計算出所要之特徵值與特徵向量。SIAR 的效率決定於內迴圈迭 代中線性系統的解。 然而,此線性系統可以在不影響最終精度的狀況下,以 較低的精度求解。 本研究主要利用此特性及混和精度和圖形處理器針對對稱 正定(Symmetric Positive Definite, SPD)的大型稀疏矩陣, 設計一有效率的 特徵值解法。我們提出一名為混合精度口袋演算法,該方法可以自動選擇何 時使用單精度或雙精度計算內圈迭代, 並且在每一回的內圈計算中可以自適 性地調整內圈的容忍度和離開回圈之時機。 此方法在我們絕大多數的測試中 都有最好的表現。

Eigenvalue problem is one of the most crucial topics in engineering and science fields nowaday. In practice applications, the target matrix is usually large and sparse, hence solving the eigenvalue problems need huge computa- tion amount. The high efficiency is a strong demand in practice, therefore High Performance Computing, HPC, plays an important role in this topic. One important approach for getting higher performance is mixed precision design, which means it will change the operation precision during the com- putation without dropping the finial accuracy. Since single precision requires less memory storage and it may cause higher cache hit ratio, which may affect performance a lot. In addition, in some numerical operation, single precision is faster than double precision. Hence, if the original algorithm is accuracy insensitive, which means that it could lost some accuracy during the compu- tation and keep the same final accuracy, then it is suitable to be redesigned as a mixed precision type algorithm to enhance the performance. The eigen- solver we focus on exactly belongs to this type. Shift-Invert Residual Arnoldi, SIRA, algorithm is an well-known eigenvalue solver, which consists of an in- ner loop and an outer loop. The inner loop is solving a linear system, which is for searching the correction direction to help outer loop find the desired eigen-pair. The efficiency of SIRA relies on the solutions of the inner-loop linear systems. These systems can be solved in lower accuracy without down- grading the final accuracy of the target eigenvalues. By taking advantage of this algorithmic feature and the computational power of GPU, we develop a mixed precision eigensolver in this research. We develop a method called pocket method, it adaptively choosing the double or single precision to solve the linear system. Moreover, in solving the linear system, it automatically adjust the inner tolerance and timing of exiting inner loop. Pocket method has the best performance in most of our experiments.