A fully data parallel WFST-based large vocabulary continuous speech recognition on a graphics processing unit

Jike Chong, Ekaterina Gonina, Youngmin Yi, Kurt KeutzerInterspeech 2009 · DOI

Introduction

Large Vocabulary Continuous Speech Recognition (LVCSR) is a computationally intensive task traditionally divided into two distinct phases: acoustic modeling and graph traversal. While acoustic modeling—calculating phoneme probabilities—is highly compute-heavy and well-suited for parallel processing, graph traversal is notoriously difficult for GPUs. This second phase involves searching through a massive Weighted Finite State Transducer (WFST) "knowledge network," characterized by irregular memory access patterns and frequent branching.

Historically, performance gains were limited because developers would offload math to the GPU while keeping the logic-heavy graph search on the CPU. This split creates a significant communication bottleneck across the PCI-Express bus. Researchers at UC Berkeley have addressed this by re-architecting the entire inference engine to be fully data-parallel, allowing the entire pipeline to run on the GPU.

System Architecture

The proposed system implements the inference engine using NVIDIA’s CUDA platform. The core innovation lies in treating the entire recognition process as a series of data-parallel operations that keep state information local to the GPU memory, avoiding the overhead of CPU-GPU data transfers.

Overview of the speech recognition pipeline and the internal architecture of the data-parallel inference engine.

As illustrated in the architecture overview, the inference engine operates iteratively. Each time step involves a compute-intensive phase (Phase 1) followed by a communication-intensive phase (Phase 2). By mapping these phases to thousands of concurrent tasks, the system maximizes the utilization of the GPU's parallel processing units.

Optimization Strategies

The architecture focuses on three primary optimization strategies to overcome the limitations of traditional graph search:

  1. Arc-Based Traversal: Traditional methods often assign one GPU thread per state. However, because different states have varying numbers of outgoing connections, this leads to significant load imbalance. By assigning threads to individual arcs instead, the system ensures that SIMD (Single Instruction, Multiple Data) groups perform uniform work, maximizing hardware utilization.
  2. Network Augmentation: WFSTs frequently contain "epsilon arcs"—transitions that do not consume input signals. These require multiple passes and global synchronizations. The researchers "flattened" these networks by adding shortcut arcs, which reduces synchronization overhead at the cost of a manageable increase in memory footprint.
  3. Redundancy Elimination: During the Gaussian Mixture Model (GMM) computation in the acoustic phase, the system employs aggressive pruning. By identifying which triphone states are relevant to the current search path, they successfully eliminated approximately 70% of the required calculations.

Experimental Evaluation

The system was evaluated using the SRI CALO Real-Time Meeting Recognition dataset, which features challenging spontaneous speech from NIST conference meetings. The test set included 3.1 hours of audio from 35 different speakers. The acoustic model featured 52,000 triphone states clustered into approximately 2,600 mixtures.

Results and Performance

The fully data-parallel GPU implementation achieved a 11.7x speedup over a highly optimized sequential implementation on an Intel Core i7. In terms of real-world utility, the system reached a Real-Time Factor (RTF) of 0.14, meaning it can process an hour of speech in just 8.4 minutes.

Performance comparison between CPU and GPU, highlighting the 11x speedup and the breakdown of compute vs. communication intensive phases.

As shown in the performance breakdown, the GPU implementation significantly shifts the bottleneck. While the CPU version spends over 80% of its time on compute-intensive tasks, the GPU version is more balanced, with communication-intensive tasks (like graph traversal and synchronization) accounting for 47% of the execution time. This shift indicates that the compute phases have been optimized to the point where data movement and synchronization are now the primary concerns.

Conclusion

The Berkeley team demonstrated that even "irregular" algorithms like WFST graph traversal can be mapped efficiently to parallel hardware if the architecture is designed to minimize CPU-GPU communication. While "One-Level" network augmentation increases the number of arcs by roughly 32%, the resulting speed gains are substantial. As GPU memory capacity and synchronization primitives continue to improve, these data-parallel techniques provide a clear path toward high-performance, real-time speech recognition on consumer-grade hardware.

Summary updated

BibTeX
@inproceedings{chong2009fully,
  author = {Jike Chong and Ekaterina Gonina and Youngmin Yi and Kurt Keutzer},
  title = {{A fully data parallel WFST-based large vocabulary continuous speech recognition on a graphics processing unit}},
  booktitle = {Interspeech},
  year = {2009},
  doi = {10.21437/interspeech.2009-343},
}
Figure