以分級平行多層舒爾法於CUDA叢集解線性系統

Scalable Hierarchical Schur Linear System Solver with Multilevel Parallelism on CUDA Enabled Clusters

王柏川(Po-Chuan Wang)

指導教授 ： 王偉仲

國立臺灣大學/理學院/應用數學科學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201610362

摘要

解稀疏線性系統是科學計算領域中最核心的問題之一，隨著問題的規模增加，有效率的解稀疏線性系統是必要的。在現今的計算機架構中，計算核心的時脈由於物理限制而難以大幅提升，計算單元的設計傾向以多核心平行達到提升效能的目的。為了最大化計算資源的使用以達到更高的效率，演算法必須針對平行的架構設計演算法。多層舒爾法藉由分析以多重巢狀分割法重排後稀疏矩陣的分塊結構，將矩陣直接解法的分解過程拆解為可平行的子問題，各個子問題中再適當地以不同的方法平行加速。在此之上，經由分析各個子問題的所需計算量，再以優化過的機制將子問題均衡的分配到不同的處理器上，進而達到更高的可擴展性。

關鍵字

線性系統 ； 圖形處理器 ； 舒爾法 ； 巢狀分割法 ； 直接法

並列摘要

Sparse linear system solver is one of the core of scientific computing. As the scale of problem increases, to solve sparse linear systems efficiently is necessary.
In recent computer architecture, the frequency of computation core is bounded
by physical limitations, thus current design of computatation unit as CPU and
GPU use multiple cores to improve the performance.
Hierarchical Schur method expolits the block structure of multilevel nested
dissection reordered sparse linear system and decompose the direct matrix
factorization scheme into concurrent subproblems. In each subproblems we
properly applied different techniques for lower level parallelism. Moreover
by analyzing the computation cost of each subproblems, it is able to
distribute the computation load to different resources to improve overall
scalability.

並列關鍵字

Linear system ； GPU ； Nested dissection method ； Direct method

參考文獻

[3] C.Che-Ming.Hybridhierarchicalschursolversforlargesparselinearsystemsoncpu- cpu cluster. Master’s thesis, Department of Mathematics, National Taiwan University, 2014.

[4] Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam. Algorithm 887: Cholmod, supernodal sparse cholesky factorization and update/downdate. ACM Trans. Math. Softw., 35(3):22:1–22:14, Oct. 2008.

[5] D. Y. Chenhan, W. Wang, and D. Pierce. A cpu–gpu hybrid approach for the unsym- metric multifrontal method. Parallel Computing, 37(12):759–770, 2011.

[7] O. Schenk, K. Gartner, W. Fichtner, and A. Stricker. Pardiso: a high-performance serial and parallel sparse linear solver in semiconductor device simulation. Future Generation Computer Systems, 18(1):69–78, 2001.

[8] I. Yamazaki and X. S. Li. On techniques to improve robustness and scalability of the schur complement method.