一种利用GPU优化大规模小方阵奇异值分解的新方法

李晓敏，鄢社锋，侯朝焕

(中国科学院 声学研究所，北京 100190)

传统意义的 GPU主要针对游戏加速和图形图像处理。NVIDIA公司于2007年发布了基于CUDA的GPU，这种意义上的GPU具有很强的并行计算能力和数据吞吐能力，在诸多领域里能使程序性能提高好几个数量级，对未来信息社会处理海量数据的需求具有很强的适应性。

基于CUDA的GPU自问世4年以来，由于其在性能、成本和开发周期上的显著优势，一经推出即在学术界和产业界引起了热烈反响，已经广泛应用于金融、石油、天文学、流体力学、信号处理、电磁仿真、模式识别、图像处理、视频压缩等众多领域[1]。

求解一般矩阵的 SVD最常用算法可以分为两大类：基于QR分解的算法和基于Jacobi旋转的分解[2]。前者首先通过一系列Householder变换实现双对角，然后通过QR变换实现对角。其中，QR分解是一种严格串行的过程，只能获得有限的并行度，因此不适合应用于GPU。后者使用平面旋转进行正交化。双边Jacobi每次正交化矩阵的两行和两列，调度时同时涉及到行和列，不适合 GPU的并行架构。而单边Jacobi每次旋转只需要正交化矩阵的两列，很容易实现并行访问。

目前关于在GPU上进行SVD的研究并不多。最初，文献[3]采用在GPU上实现双对角变换和在CPU上实现对角变换的混合编程法完成了SVD。2009年，文献[5]首次使用 GPU实现了双对角-对角算法。同年，文献[6]在 3D重建过程中将VL数据库里的SVD程序转换成CUDA语言，从而实现实时重建。2010年，文献[7]采用 Webb算法在GPU上实现了SVD。然而，这些方法相对于MATLAB和IntelMKL的优势仅仅体现在针对单个大矩阵SVD，并且当矩阵维数增大到成千上万时这种优势更加明显。……