Distributed Out-of-Memory SVD on CPU/GPU Architectures

Abstract

We propose an efficient, distributed, out-of-memory implementation of the truncated singular value decomposition (t-SVD) for heterogeneous (CPU+GPU) high performance computing (HPC) systems. Various implementations of SVD have been proposed, but most only estimate the singular values as an estimation of the singular vectors which can significantly increase the time and memory complexity of the algorithm. In this work, we propose an implementation of SVD based on the power method, which is a truncated singular values and singular vectors estimation method. Memory utilization bottlenecks seen in the power method are typically associated with the computation of the Gram matrix ${A}^T{A}$, which can be significant when ${A}$ is large and dense, or when ${A}$ is super-large and sparse. The proposed implementation is optimized for out-of-memory problems where the memory required to factorize a given matrix is greater than the available GPU memory. We reduce the memory complexity of ${A}^T{A}$ by using a batching strategy where the intermediate factors are computed block by block. We also suppress I/O latency associated with both host-to-device (H2D) and device-to-host (D2H) batch copies by overlapping each batch copy with compute using CUDA streams. Furthermore, we use optimized $\textit{NCCL}$ based communicators to reduce the latency associated with collective communications (both intra-node and inter-node). In addition, sparse and dense matrix multiplications are significantly accelerated with GPU cores (or tensors cores when available), resulting in an implementation with good scaling. We demonstrate the scalability of our distributed out of core SVD algorithm to successfully decompose dense matrix of size 1TB and sparse matrix of size 128PB with 1e-6 sparsity.

Publication
arXiv preprint. Accepted at IEEE HPEC Conference 2022 with Outstanding Paper Award

Keywords:

SVD, out-of-memory, latent features, data com- pression, distributed processing, parallel programming, big data, heterogeneous computing, GPU, CUDA, NCCL, cupy

Citation:

Boureima, I., Bhattarai, M., Eren, M. E., Solovyev, N., Djidjev, H., & Alexandrov, B. S. (2022). Distributed Out-of-Memory SVD on CPU/GPU Architectures. arXiv preprint arXiv:2208.08410.

BibTeX:

@article{boureima2022distributed,
  title={Distributed Out-of-Memory SVD on CPU/GPU Architectures},
  author={Boureima, Ismael and Bhattarai, Manish and Eren, Maksim E and Solovyev, Nick and Djidjev, Hristo and Alexandrov, Boian S},
  journal={arXiv preprint arXiv:2208.08410},
  year={2022},
  note={Accepted at IEEE HPEC Conference 2022 with Outstanding Paper Award}
}
Maksim E. Eren
Maksim E. Eren
Graduate Research Assistant

My research interests lie at the intersection of the machine learning and cybersecurity disciplines, with a concentration in tensor decomposition.