多GPU架構之Strassen矩陣乘法

Strassen’s Matrix Multiplication on Multi-GPU

10.6843/NTHU.2012.00500

高魁良

矩陣乘法 ； 快速矩陣乘法 ； 通用圖形處理器 ； matrix multiplication ； Strassen ； multi-GPU ； GPGPU ； GPU

清華大學資訊工程學系所學位論文

2012年

碩士

李哲榮

繁體中文

裝配有大量平行處理單元的通用圖形處理器已經成為高效能計算領域中不可或缺的設備。為了能更有效率地處理更大尺度的問題，多GPU架構也開始被使用在高效能的機器上。因此，設計良好的演算法以符合多GPU平台在現今已是重要研究課題。 在本論文中，我們在多GPU架構實作了高效能的Strassen乘法演算法。Strassen矩陣乘法演算法具有遞迴性質，在每個步驟中，輸入矩陣將被分解為2*2的子矩陣，遞迴進行7次的子矩陣乘法以及18個子矩陣加法，再組合出最後的結果。比起傳統的O(n^3)矩陣乘法，Strassen演算法能夠達到低於立方次的時間複雜度。 我們提出3種多GPU平台上的快速矩陣乘法實作： 傳統方法：使用傳統的block形式矩陣乘法將工作分配給多個GPU，然後再於GPU上運行cublas4.2的O(n^3)矩陣乘法sgemm。 Hybrid方法：使用傳統的block形式矩陣乘法將工作分配給多個GPU，然後再於GPU上運行快速矩陣乘法。 Strassen方法：使用Strassen的子矩陣分割方式遞迴展開2次，然後再於GPU上運行快速矩陣乘法。 我們在裝配有四張Tesla C2070運算卡的平台上測試，相較於O(n^3)的平行sgemm，我們的Strassenz方法獲得了28.5%的效能進展；以單一GPU的sgemm作為比較對象，則可以達到4.37的speedup。

General Purpose Graphics Processing Unit (GPGPU) that equips massively parallel processing units has become an indispensible building block in High Performance Computing (HPC). To achieve better scalability, the multi-GPU architecture is used in modern HPC machines. Therefore, designing efficient algorithms for multi-GPU platforms has been an important research topic already. In this thesis, we presented the high performance implementations of Stassen’s matrix multiplication algorithm on multi-GPU. Strassen’s algorithm is recursive defined. In each level, the matrices are evenly partitioned into 2x2 submatrices, and Strassen’s algorithm uses 7 matrix multiplications and 18 matrix additions on those submatrices to assemble the final result. Comparing to the general O(n^3) matrix multiplication algorithms, Strassen’s algorithm can achieve subcubic time complexity. Three implementations of matrix multiplication for multi-GPU are presented. Traditional method: which uses the block matrix multiplication algorithm to partition the multiplications of submatrices to multiple GPUs, and uses sgemm on each single GPU. Hybrid method: which uses the block matrix multiplication algorithm to partition the multiplications of submatrices to multiple GPUs, and uses fast matrix multiplication on each single GPU. Strassen method: which applies 2 times Strassen’s partition(which gives 49 sub-multiplications and 126 sub-additions) to distribute the workload for multiple GPU, and uses fast matrix multiplication on each single GPU. Those implementations were experimented on the platform equipped with four Tesla C2070 GPUs, and compared with the sgemm kernel for single GPU in cublas 4.2. About 4.37 times speedup can be obtained by using the Strassen implementation。

1. 黃啟青(2017)。商業環境改變下，台灣針織染整業新舊商業模式比較研究。臺中科技大學企業管理系碩士班學位論文。2017。1-98。