SaberLDA: Sparsity-Aware Learning of Topic Models on GPUs

Kaiwei Li, Jianfei Chen, Wenguang Chen, Jun Zhu

TL;DR

SaberLDA is a high-performance GPU system that enables training Latent Dirichlet Allocation (LDA) models with up to 10,000 topics on billions of tokens using a single GPU. By leveraging sparsity-aware algorithms and novel GPU-optimized data structures, it achieves performance and scale that previously required clusters of dozens of CPU-based machines.

What Problem Does This Paper Address?

Latent Dirichlet Allocation (LDA) is a cornerstone of text analysis, used to discover hidden "topics" in massive collections of documents. As datasets grow to billions of tokens, researchers need thousands of topics to capture fine-grained semantic structures.

While GPUs offer massive computational power, existing GPU-based LDA systems hit a wall at a few hundred topics. This is because they use "dense" algorithms where the time and memory required grow linearly with the number of topics ($O(K)$). To scale further, we need "sparsity-aware" algorithms that recognize a single document or word only relates to a tiny fraction of all possible topics. However, implementing these algorithms on GPUs is notoriously difficult due to the GPU's sensitivity to random memory access and branch divergence (where different threads in a group try to do different things).

Methods

The authors introduce SaberLDA, which implements the sparsity-aware ESCA algorithm on GPUs. Their approach relies on three key technical innovations:

  1. PDOW Data Layout (Partition-by-Document and Order-by-Word): To handle datasets larger than GPU memory, SaberLDA partitions data by documents into chunks for streaming. Within each chunk, tokens are sorted by word-id. This hybrid layout maximizes cache locality by allowing the system to load a word's topic distribution once and reuse it for all occurrences of that word in the chunk.
  2. Warp-based Sampling Kernel: Standard GPU programming often assigns one thread to one task. In SaberLDA, an entire warp (a group of 32 threads) collaborates to sample a single token. This eliminates branch divergence and allows for efficient vectorization. To support this, they developed a $W$-ary sampling tree (where $W=32$), which perfectly matches the warp size for $O(\log_{32} K)$ sampling complexity.
  3. SSC (Shuffle and Segmented Count): Updating sparse matrices on a GPU is slow. Instead of updating the document-topic matrix element-by-element, SaberLDA uses a novel "shuffle and segmented count" algorithm to rebuild the sparse matrix from scratch each iteration, which is significantly faster and more hardware-friendly.
Figure 1. An example token list and related count matrices.

To manage memory, SaberLDA uses a streaming workflow that overlaps computation on the GPU with data transfers from the CPU, as shown below:

Figure 3. Streaming workflow of SaberLDA. L: Token List, A: document-topic count matrix, B: word-topic count ma- trix, ˆB: word-topic probability matrix.

Datasets

The system was evaluated on three major datasets:

  • NYTimes: 300,000 documents, 100 million tokens.
  • PubMed: 8.2 million documents, 738 million tokens.
  • ClueWeb12 subset: A massive web crawl containing 19.4 million documents and 7.1 billion tokens.

Key Insights and Ideas

  • The Locality Trade-off: On CPUs, document-major ordering is often preferred because the word-topic matrix can fit in the large L3 cache. On GPUs, the cache is much smaller, making word-major ordering superior because it allows for sequential access to the document-topic matrix rows.
  • Warp-Level Collaboration: By treating the warp as the basic unit of work rather than the thread, the authors bypass the "long-tail" problem where one thread with many non-zero entries stalls the entire group.
  • Tree Branching Factor: While binary trees (branching factor of 2) are standard, a 32-way tree is the "sweet spot" for GPUs. It reduces the tree height significantly (e.g., a 4-level tree can handle over 32,000 topics) while allowing a single warp to process a node in one go.

Key Results

  • Massive Scaling: SaberLDA successfully trained models with 10,000 topics, nearly two orders of magnitude more than previous GPU systems like BIDMach.
  • Superior Speed: On a single NVIDIA GTX 1080, SaberLDA converged 5.6x faster than BIDMach and 4x to 5.4x faster than highly optimized CPU-based systems (like ESCA-CPU and DMLC).
  • Efficiency: When increasing the number of topics from 1,000 to 10,000, SaberLDA's throughput only dropped by 17%, demonstrating excellent sublinear complexity.
  • Single-Card Power: It processed the 7.1-billion-token ClueWeb dataset with 10,000 topics in just a few hours on one GPU—a feat previously requiring a 32-machine CPU cluster.

Limitations and Future Work

The current implementation of SaberLDA is designed for a single GPU. While it is incredibly powerful, the authors note that extending the system to multi-GPU setups and distributed clusters is a natural next step for even larger datasets. Additionally, they suggest that exploring different underlying inference algorithms that might converge in fewer iterations while maintaining GPU-friendly locality is a promising research direction.

Summary updated

Abstract

Latent Dirichlet Allocation (LDA) is a popular tool for analyzing discrete count data such as text and images. Applications require LDA to handle both large datasets and a large number of topics. Though distributed CPU systems have been used, GPU-based systems have emerged as a promising alternative because of the high computational power and memory bandwidth of GPUs. However, existing GPU-based LDA systems cannot support a large number of topics because they use algorithms on dense data structures whose time and space complexity is linear to the number of topics. In this paper, we propose SaberLDA, a GPU-based LDA system that implements a sparsity-aware algorithm to achieve sublinear time complexity and scales well to learn a large number of topics. To address the challenges introduced by sparsity, we propose a novel data layout, a new warp-based sampling kernel, and an efficient sparse count matrix updating algorithm that improves locality, makes efficient utilization of GPU warps, and reduces memory consumption. Experiments show that SaberLDA can learn from billions-token-scale data with up to 10,000 topics, which is almost two orders of magnitude larger than that of the previous GPU-based systems. With a single GPU card, SaberLDA is able to learn 10,000 topics from a dataset of billions of tokens in a few hours, which is only achievable with clusters with tens of machines before.
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