Abstract
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。