  Weighted finite-state transducers (FSTs) are frequently used in language
processing to handle tasks such as part-of-speech tagging and speech
recognition. There has been previous work using multiple CPU cores to
accelerate finite state algorithms, but limited attention has been given to
parallel graphics processing unit (GPU) implementations. In this paper, we
introduce the first (to our knowledge) GPU implementation of the FST
composition operation, and we also discuss the optimizations used to achieve
the best performance on this architecture. We show that our approach obtains
speedups of up to 6x over our serial implementation and 4.5x over OpenFST.
