high performance computing on graphics processing units: hgpu.org

Hidden Semi-Markov Models (HSMMs) are powerful generalizations of Hidden Markov Models that have been effectively employed in tasks such as machine translation and optical character recognition. A principal computational bottleneck on these systems as applied to optical character recognition [5] is the need to compute emission probabilities for a large number of possible model states. Recognizing that such systems may be deployed on hardware with different specifications, we examine multiple ways of addressing this computational bottleneck. The structure of the emission computation is amenable to running on GPUs using CUDA [19]; this gives roughly a 30x speedup on this part of the algorithm over an optimized single-threaded CPU implementation. When a GPU is not available, an approximation scheme can be employed to achieve speedups of between 2x and 4x depending on how much accuracy loss can be tolerated.