Technical Papers Archive

W-Cycle SVD: A Multilevel Algorithm for Batched SVD on GPUs

Authors: Junmin Xiao, Yunfei Pang, Qing Xue, and Chaoyang Shui (Institute of Computing Technology, Chinese Academy of Sciences); Ke Meng (Alibaba Group); and Hui Ma, Mingyi Li, Xiaoyang Zhang, and Guangming Tan (Institute of Computing Technology, Chinese Academy of Sciences)

Abstract: As a basic matrix factorization operation, Singular Value Decomposition (SVD) is widely used in diverse domains. In real-world applications, the computational bottleneck of matrix factorization is on small matrices, and many GPU-accelerated batched SVD algorithms have been developed recently for higher performance. However, these algorithms failed to achieve both high data locality and convergence speed, because they are size-sensitive. In this work, we propose a novel W-cycle SVD to accelerate the batched one-sided Jacobi SVD on GPUs. The W-cycle SVD, which is size-oblivious, successfully exploits the data reuse and ensures the optimal convergence speed for batched SVD. Further, we present the efficient batched kernel design, and propose a tailoring strategy based on auto-tuning to improve the batched matrix multiplication in SVDs. The evaluation demonstrates that the proposed algorithm achieves 2.6–10.2× speedup over the state-of-the-art cuSOLVER. In a real-world data assimilation application, our algorithm achieves 2.73–3.09× speedup compared with MAGMA.


Presentation: file


Back to Technical Papers Archive Listing