cuFasterTucker: A Stochastic Optimization Strategy for Parallel Sparse FastTucker Decomposition on GPU Platform

Zixuan Li, Yunchuan Qin, Qi Xiao, Wangdong Yang, Kenli LiACM Trans. Parallel Comput 2024 · DOI

TL;DR

This paper introduces cuFasterTucker, a novel GPU-accelerated algorithm for sparse FastTucker decomposition. It significantly speeds up the decomposition process by optimizing intermediate variable computations and leveraging a balanced sparse fiber (B-CSF) tensor storage format, achieving up to 15x speedup over existing methods.

What Problem Does This Paper Address?

The ever-increasing size and complexity of scientific data, often characterized by high-order, high-dimensionality, and sparsity, pose significant challenges for traditional tensor decomposition methods. Tucker decomposition, a powerful tool for analyzing such data, becomes computationally prohibitive due to its high memory and computational demands, especially for sparse tensors. Existing parallel sparse Tucker decomposition algorithms, while making progress, still suffer from high intermediate variable storage and computational complexity, limiting their scalability. This paper aims to address these limitations by proposing an efficient and scalable parallel sparse FastTucker decomposition algorithm optimized for GPUs.

Methods

The core of this work is the cuFasterTucker algorithm, built upon the FastTucker decomposition framework. FastTucker itself reduces the computational complexity of Tucker decomposition from exponential to polynomial by replacing the n-order core tensor with n low-rank core matrices. cuFasterTucker further enhances this by:

  • Stochastic Optimization: It employs a stochastic optimization strategy, updating one factor or core matrix at a time while keeping others fixed, ensuring a convex optimization problem at each step.
  • Balanced Compressed Sparse Fiber (B-CSF) Tensor Storage Format: This format is crucial for efficiently handling sparse tensors on GPUs. It balances the load across threads by dividing large data structures into smaller, more manageable sub-structures, reducing memory access overhead and improving computational efficiency.
  • Reusable and Shared Intermediate Variables: The algorithm meticulously identifies and reuses intermediate variables that are computed multiple times, significantly reducing redundant calculations. This includes pre-calculating and storing products of factor matrices and core matrices.
  • Fine-grained Parallelization: cuFasterTucker leverages GPU's parallel processing capabilities through both worker parallelization (dividing tasks among thread blocks) and thread parallelization (optimizing thread execution within blocks).
  • Memory Optimization Techniques: Techniques like memory coalescing (optimizing memory access patterns) and warp shuffle instructions (efficient inter-thread communication within a warp) are employed to maximize GPU memory bandwidth and reduce latency.

Datasets

The paper evaluates cuFasterTucker using both real-world and synthetic datasets:

  • Real-world Datasets:
    • Netflix: Movie rating data (user, movie, time, rating).
  • Yahoo! Music: Music rating data (user, music, time, rating).
  • Synthetic Datasets:
    • Synthetic(Order): Tensors with orders ranging from 3 to 10 to test adaptability to high-order tensors.
  • Synthetic(Sparsity): Tensors with varying sparsity levels (2% to 10%) to assess performance on sparse data.

Key Insights and Ideas

  • The Power of B-CSF for Sparse Tensors: The B-CSF format is a key enabler for efficient sparse tensor processing on GPUs, providing a balanced distribution of work and reducing load imbalances that plague other methods.
  • Intermediate Variable Optimization is Crucial: Identifying and reusing intermediate variables, as done in cuFasterTucker, offers substantial computational savings, especially in the context of sparse tensor decomposition.
  • GPU Architecture Exploitation: The algorithm effectively utilizes GPU features like dynamic random access memory (DRAM), on-chip caches (L1), shared memory, and warp shuffle instructions to maximize performance.
  • Scalability with Sparsity: cuFasterTucker shows a significant efficiency increase with increasing tensor sparsity, making it particularly well-suited for many real-world high-dimensional sparse datasets.

Key Results

  • Significant Speedup: cuFasterTucker achieves substantial speedups compared to its predecessor, cuFastTucker, with up to 15.0X speedup in updating factor matrices and 7.0X speedup in updating core matrices.
  • Improved Performance on High-Order Tensors: cuFasterTucker demonstrates better scalability and significantly smaller single iteration times for high-order tensors compared to other algorithms.
  • Competitive Accuracy: The algorithm achieves comparable accuracy to existing methods on real-world datasets, as measured by RMSE and MAE.
  • Efficiency Gains from B-CSF: cuFasterTucker_B-CSF (using the B-CSF format) shows a 2.0X to 5.0X speedup over cuFastTucker, highlighting the format's effectiveness.
  • Adaptability to Sparsity: The efficiency of cuFasterTucker increases significantly with tensor sparsity, outperforming other methods in this regard.

Limitations and Future Work

  • Limitations: The paper acknowledges that while B-CSF provides load balancing, it slightly increases the amount of computation due to the division of sub-slices. The performance on very low sparsity tensors is comparable to other algorithms but doesn't show the same dramatic efficiency gains as with high sparsity.
  • Future Work: The authors plan to explore the FastTucker algorithm with even faster convergence speeds and extend it to new parallel hardware platforms and distributed systems.

Summary updated

BibTeX
@article{li2024cufastertucker,
  author = {Zixuan Li and Yunchuan Qin and Qi Xiao and Wangdong Yang and Kenli Li},
  title = {{cuFasterTucker: A Stochastic Optimization Strategy for Parallel Sparse FastTucker Decomposition on GPU Platform}},
  journal = {ACM Trans. Parallel Comput.},
  year = {2024},
  doi = {10.1145/3648094},
}
Figure