Parallel Composition of Weighted Finite-State Transducers

Shubho Sengupta, Vineel Pratap, Awni Y. HannunICASSP 2022 · DOI

TL;DR

This paper introduces a novel parallel algorithm for composing weighted finite-state transducers (FSTs) specifically designed for GPUs. This GPU-accelerated approach significantly speeds up FST composition, a critical operation in speech recognition and other sequence processing tasks, by up to 30 times compared to highly optimized sequential CPU implementations.

What Problem Does This Paper Address?

Finite-state transducers (FSTs) are fundamental tools in areas like speech recognition, natural language processing, and optical character recognition. A key operation with FSTs is composition, which allows combining information from different sources at various granularities. For instance, in speech recognition, FSTs are composed to integrate language models, lexicons, and acoustic models. However, FST composition is computationally expensive, with its complexity scaling poorly with the size of the input FSTs (O(V₁V₂D₁D₂)). Existing parallel approaches often struggle with efficiency or generality due to the heterogeneous nature of FSTs. While "lazy" or "on-the-fly" composition methods exist for inference, constructing the full composed graph is crucial for tasks like model training with automatic differentiation. This creates a need for an efficient, "eager" parallel composition method, especially for modern hardware like GPUs.

Methods

The authors propose a SIMD-style parallel algorithm for FST composition optimized for GPUs. The core idea is to leverage the parallel processing capabilities of GPUs to explore multiple composition possibilities concurrently.

Key aspects of their method include:

  • Structure of Arrays (SoA) Layout: They adopt a SoA data structure for FSTs, which is more efficient for SIMD operations on GPUs compared to the traditional Array of Structures (AoS) used in sequential implementations. This involves storing node and edge data in separate arrays.
  • Parallel Exploration: The algorithm parallelizes the core loops of the sequential composition process. Instead of processing one state pair at a time, multiple threads are assigned to explore arc pairs for all currently active state pairs in the queue.
  • Handling Epsilon Transitions: The proposed algorithm supports epsilon (ε) transitions, which are common in FSTs and add complexity to composition.
  • Race Condition Mitigation: To handle concurrent modifications to the composed graph data structures, the parallel implementation employs a two-pass approach. The first pass atomically counts new nodes and arcs, and the second pass atomically assigns indices and fills in the arc data. This ensures thread safety without requiring extensive synchronization primitives.
  • Co-accessible State Computation: The initial step of computing co-accessible states is also parallelized using a similar approach.

Datasets

The paper does not introduce new datasets. Instead, it uses two types of benchmarks for evaluation:

  1. Random Graphs: These are generated by specifying the number of nodes, a single start and accept state, and a fixed outgoing arc degree. The destination nodes and arc labels are chosen randomly.
  2. Lexicon and Emissions Graph: This benchmark emulates a realistic speech recognition scenario. It involves composing the closure of a lexicon (derived from the Librispeech corpus, containing 200,000 word-to-phoneme mappings) with a linear emissions graph representing acoustic model scores. This benchmark specifically requires support for epsilon transitions.

Key Insights and Ideas

  • GPU Parallelism for FST Composition is Viable and Highly Effective: The research demonstrates that the inherent parallelism in FST composition can be effectively exploited on GPUs, leading to substantial speedups.
  • SoA Data Structure is Crucial for GPU Performance: The choice of data structure significantly impacts performance on parallel architectures. The SoA layout is shown to be a key enabler for their GPU algorithm.
  • Epsilon Transitions Don't Hinder GPU Performance: Unlike some prior GPU FST work, their algorithm handles epsilon transitions efficiently, making it applicable to more practical scenarios.
  • Scalability is Achieved for Large Graphs: The performance gains are most pronounced for larger graphs, where the overhead of parallelization is amortized over a greater number of operations.

Key Results

The paper reports significant speedups for their GPU-based parallel composition algorithm:

  • Random Graphs: For large graphs (8,192 nodes), the GPU implementation was up to 30 times faster than a highly optimized sequential CPU implementation. This speedup was observed when varying the number of nodes and the outgoing arc degree.
  • Lexicon and Emissions Graph: When composing a lexicon with an emissions graph, the GPU implementation was more than 10 times faster than the CPU implementation for a lexicon size of 32,000 words.

Limitations and Future Work

  • N-way Composition: The current algorithm focuses on composing two FSTs at a time. The authors suggest that developing parallel algorithms for N-way composition could yield further improvements.
  • Other FST Operations: The paper highlights that a fully featured GPU framework for FSTs would require parallel implementations of other critical operations, such as determinization, minimization, epsilon removal, and shortest path algorithms.
  • Further Optimization: The authors intend to continue refining and optimizing their parallel composition algorithm.

Summary updated

BibTeX
@inproceedings{sengupta2022parallel,
  author = {Shubho Sengupta and Vineel Pratap and Awni Y. Hannun},
  title = {{Parallel Composition of Weighted Finite-State Transducers}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  doi = {10.1109/icassp43922.2022.9747713},
}
Figure