SaberLDA: Sparsity-Aware Learning of Topic Models on GPUs

Kaiwei Li, Jianfei Chen, Wenguang Chen, Jun Zhu

Abstract

SaberLDA is a high-performance system that enables GPUs to train Latent Dirichlet Allocation (LDA) models with tens of thousands of topics—an order of magnitude more than previous GPU solutions. By implementing a sparsity-aware algorithm with novel data layouts and warp-based kernels, it can process billions of tokens in just two hours on a single 4-GPU machine, matching the performance of massive CPU clusters.

Introduction

Topic modeling, specifically Latent Dirichlet Allocation (LDA), is a cornerstone of text mining and recommendation systems. To capture the "rich semantic structure" of massive industry-scale datasets, models often need tens of thousands of topics ($K$).

However, training such models is computationally expensive. Standard LDA algorithms have a time complexity of $O(K)$ per token. While CPU-based systems have used "sparsity-aware" optimizations to reduce this to sublinear complexity, GPUs have historically struggled with these techniques. Sparsity introduces random memory access and branch divergence—two things GPUs are notoriously bad at handling. Consequently, previous GPU-based LDA systems were limited to only a few hundred or thousand topics before becoming too slow or running out of memory.

Methods

SaberLDA bridges the gap between sparsity-aware algorithms and GPU architecture through several key innovations designed to maximize hardware utilization and minimize memory bottlenecks.

PDOW Data Layout and Word-Major Ordering

The system introduces a hybrid "Partition-by-Document and Order-by-Word" (PDOW) layout. While CPU systems often prefer document-major ordering, SaberLDA utilizes word-major ordering to maximize cache locality on GPUs. This allows the system to calculate a word-topic factor once and reuse it for all occurrences of that word in a block, significantly reducing redundant global memory fetches.

Comparison of data layouts: (a) single token sampling, (b) doc-id major order, and (c) word-id major order which optimizes cache locality on GPUs.

Warp-Based Sampling and W-ary Tree

Instead of assigning one thread to one token (which causes massive branch divergence), SaberLDA uses an entire warp (32 threads) to collaboratively sample a single token. This "Warp as a Unit" philosophy transforms a divergent, random-access problem into a coordinated, vectorized one.

To sample from the dense portion of the topic distribution, the authors developed a 32-way (W-ary) search tree. This structure allows a warp to find the correct topic in just a few steps using specialized GPU instructions like __ballot and __ffs.

The W-ary sampling tree structure used for efficient topic sampling within a warp.

Load Balancing and Multi-GPU Support

To handle power-law distributions in real-world vocabularies, SaberLDA uses Split Index Load Balancing, splitting the workload of frequent words across multiple GPU blocks. For multi-GPU environments, the Shuffle and Segmented Count (SSC) algorithm efficiently updates sparse count matrices without the heavy overhead of global sorting.

Evaluation

The system was evaluated on three large-scale public datasets: NYTimes (100 million tokens), PubMed (738 million tokens), and ClueWeb12 (8.9 billion tokens).

Key Results

  • Massive Scale: SaberLDA successfully trained a model with 40,000 topics on the 8.9-billion-token ClueWeb12 dataset in just 2 hours using 4 GPUs. Previously, this required clusters of 32+ CPU nodes.
  • Speedup: On thousands of topics, SaberLDA is 6–10 times faster than BIDMach (the previous state-of-the-art GPU LDA system).
  • Efficiency: Using a single GPU, SaberLDA converges 5x faster than previous GPU systems and 4x faster than optimized CPU systems.
  • Scalability: The system achieves near-linear speedup when scaling from 1 to 4 GPUs, thanks to the Split Index load balancing.

Conclusion

By embracing sparsity as a feature rather than a limitation, SaberLDA achieves sublinear complexity, meaning the time to process a token does not scale linearly with the number of topics. While currently a single-server solution, its performance demonstrates that GPUs can effectively handle massive-scale topic modeling tasks previously reserved for large CPU clusters. Future work may involve scaling out to multi-server clusters and streaming data from NVMe SSDs to bypass RAM constraints.

Summary updated

BibTeX
@inproceedings{li2017saberlda,
  author = {Kaiwei Li and Jianfei Chen and Wenguang Chen and Jun Zhu},
  title = {{SaberLDA: Sparsity-Aware Learning of Topic Models on GPUs}},
  booktitle = {ASPLOS},
  year = {2017},
  doi = {10.1145/3037697.3037740},
}
Figure