Efficient Emission Computation in Hidden Semi-Markov Models on Diverse Hardware

Greg Durrett, Taylor Berg-Kirkpatrick
UC Berkeley
UC Berkeley, Project final report, 2013


   title={Efficient Emission Computation in Hidden Semi-Markov Models on Diverse Hardware},

   author={Durrett, Greg and Berg-Kirkpatrick, Taylor},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: