利用高度平行之演算法整合多重隨機奇異值分解並應用於巨量資料分析

Highly Scalable Parallelism of Integrated Randomized Singular Value Decomposition with Big Data Applications

楊慕(Mu Yang)

指導教授 ： 王偉仲

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

https://doi.org/10.6342/NTU201702960

摘要

低秩近似在大數據分析中佔了重要的地位，整合奇異值分解（Integrated Singular Value Decomposition，iSVD）是一種用於計算大矩陣的低秩近似奇異值分解的演算法。iSVD集成了從多個隨機子空間抽樣而獲得的不同的低秩奇異值分解，並達到更高的精準度和更好的穩定性。雖然多個隨機抽樣與合併的過程需要更高的計算成本，但由於這些操作可以平行化，iSVD 仍然可以節省計算時間。我們在多核心計算集群上平行此演算法，並對計算方法及資料結構進行了修改，以增加可擴展性並減少資料傳輸。透過平行化，iSVD 可以找到巨大矩陣的近似奇異值分解，達到相對於矩陣尺寸和機器數量接近線性的可擴展性，並透過使用 GPU 在抽樣的步驟達到四倍的加速。我們用 C++ 實作此演算法，並應用了幾種提高可維護性、可擴展性和可用性的技術。我們在使用混合 CPU-GPU 的超級電腦系統上使用 iSVD 求解一些大規模的應用問題。

關鍵字

奇異值分解 ； 平行演算法 ； 分散式演算法 ； 隨機演算法 ； 圖形處理器 ； 大數據分析

並列摘要

Low-rank approximation plays an important role in big data analysis. Integrated Singular Value Decomposition (iSVD) is an algorithm for computing low-rank approximate singular value decomposition of large size matrices. The iSVD integrates different low-rank SVDs obtained by multiple random subspace sketches and achieve higher accuracy and better stability. While iSVD takes higher computational costs due to multiple random sketches and the integration process, these operations can be parallelized to save computational time. We parallelize iSVD for multicore clusters, and modify the algorithms and data structures to increase the scalability and reduce communication. With parallelization, iSVD can find the approximate SVD of matrices with huge size, and achieve near-linear scalability with respect to the matrix size and the number of machines, and gained further 4X faster timing performance on sketching by using GPU. We implement the algorithms in C++, with several techniques for high maintainability, extensibility, and usability. The iSVD is applied on some huge size application using hybrid CPU-GPU supercomputer systems.

並列關鍵字

Singular value decomposition ； Parallel algorithms ； Distributed algorithms ； Randomized algorithms ； Graphics processing units ； Big data analysis

參考文獻

[3] T.-L. Chen, D. D. Chang, S.-Y. Huang, H. Chen, C. Lin, and W. Wang, “Integrating multiple random sketches for singular value decomposition,” arXiv preprint arXiv:1608.08285, 2016.

[19] E. Anderson, J. Dongarra, and S. Ostrouchov, LAPACK Working Note 41: Installation Guide for LAPACK. University of Tennessee, Computer Science Department, 1992.

[1] N. Halko, P.-G. Martinsson, and J. A. Tropp, “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,” SIAM review, vol. 53, no. 2, pp. 217–288, 2011.

[2] V. Rokhlin, A. Szlam, and M. Tygert, “A randomized algorithm for principal component analysis,” SIAM Journal on Matrix Analysis and Applications, vol. 31, no. 3, pp. 1100–1124, 2009.

[4] S. Fiori, T. Kaneko, and T. Tanaka, “Mixed maps for learning a Kolmogoroff-Nagumo-type average element on the compact Stiefel manifold,” in 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2014, pp. 4518–4522.