
Hidden Markov Models ATI Stream
frankas Jan 6, 2010 7:26 PM (in response to remco)Originally posted by: remco
Is it easy to implement a hidden markov model in ati stream?
What kind of speed ups can one expect?
Thanks in advance!
In general, using Brook+ or OpenCL is no harder that writing C code, once you have your developer enviornment up and running.
I haven't done double calculations, but a general observation is that you can often get more than 50% of theoretical speeds, without using exotic optimizations, if your task is highly paralellizable and with uniform code paths.
if you posted a link to C / C++ code similar to what you want to achieve, we may be able to tell you which performance issues you need to take into concideration.

Hidden Markov Models ATI Stream
remco Jan 7, 2010 11:10 AM (in response to frankas)Dear frankas,
Thank you for your reply. Wow 50% of theoretical speed without using exotic optimizations is really good. Hidden markov models are paralellizable over the states and over the number of independent observations. (At least for the forward, backward and viterbi algorithms which are dynamic programming examples) The computation of the emission probabilities is completely paralel. And the reestimation of the matrices are examples of matrix reduction. Sum over one of the dimensions of a given matrix but not always the ideal direction.
I already found two articles of people who implemented hidden markov models on the GPU. Both report dramatic speed ups over CPU implementations. (One of them unrealistic there must have been something wrong with the CPU implementation)
http://www.graphics.stanford.edu/papers/clawhmmer/hmmer.pdf
http://www.liuchuan.org/pub/cuHMM.pdf
Oke the code that I would like to speed up is divided into 5 functions namely:
hmmemissionprobabilitiesgmm //Computation of emission probabilities using gaussian mixture models
hmmstatetransitionprobabilities //Computation of state transition probabilities gamma and epsilon
hmmstatepriormatrix //Computation of state prior matrix
hmmstatetransitionmatrix //computation of state transition matrix
hmmstateemissionmatrixgmm //computation of new gaussian mixture model
The code:
http://blackboard.tudelft.nl/webapps/cmsmain/webui/_xy2061251_1tid_Ir5s4JuD //hmmemissionprobabilitiesgmm
http://blackboard.tudelft.nl/webapps/cmsmain/webui/_xy2061252_1tid_4jW7cjat //hmmstateemissionmatrixgmm
http://blackboard.tudelft.nl/webapps/cmsmain/webui/_xy2061256_1tid_JwuoXS1P //hmmstatepriormatrix
http://blackboard.tudelft.nl/webapps/cmsmain/webui/_xy2061253_1tid_W1kscrDw //hmmstatetransitionmatrix
http://blackboard.tudelft.nl/webapps/cmsmain/webui/_xy2061254_1tid_QwyALa8M //hmmstatetransitionprobabilities

Hidden Markov Models ATI Stream
frankas Jan 9, 2010 9:36 PM (in response to remco)Hi, sorry for the delay, I didn't have time to read all the code you posted, but I noticed at some points there were inversion of matrices, but the size was not specified. Inversion of large matrices may be a challenge to do efficiently.
You may do well to google for GPU + matrices + invert
Here is a sample thread on this topic:
http://ubuntuforums.org/showthread.php?t=1217446
(With a link to a paper on the subject at the very bottom)

Hidden Markov Models ATI Stream
remco Jan 10, 2010 1:38 PM (in response to frankas)Hi Frankas,
Like you already mentioned matrix inversions can be time consuming if the matrices are large and an inversion is often required. However in my implementation the matrix inversion is only done once per covariance matrix. And these covariance matrices never become larger than say 32 by 32 elements. But this is indeed something one could not see from the code. I do not use that many states but the number of training samples is really big and the length of each training samples is in the order of 200. The dimensionality of the observations is in the order of 12 but can be smaller or larger. The bits that take a lot of time are the per element evaluation of a multi dimensional normal distribution (inverse and determinant of the covariance matrices are only computed once but evaluating the exponential function milions of times takes a lot of time) If the number of states grow the complexity of the forward and backward algorithms grows with a power of two. These are the things that take up a lot of time.

Hidden Markov Models ATI Stream
frankas Jan 10, 2010 6:48 PM (in response to remco)You may have figures that I haven't done this kind of calculations before, but I will still try to help. If it all boils down to lots and lots of multiplications and additions, then GPU will be the right tool for the job. But you may have to cut and dice your problem a bit differently.
200 data sets may be a large job, but it isn't a big dataset as such for say a HD 5850 or 5850 type GPU. To keep the 5850 occupied, you need at least 288 'threads' minimum, but it is easier with 4 times that amount. Also if you want to keep your computer responsive during the calculations, it is best to split the work load up into smaller batches that can be executed in a fraction of a second, in fact single computations taking over 10 seconds will often be aborted before completion.
So the challenge might be to split the job into 1000 parallel threads, each running for a short time, and producing a intermediate output (a stream), and then breaking the task down to several such steps, each operating on part of the input and/or the intermediate streams, the finally producing the output (result) you desire. If your dataset doesn't fit in memory, you also need to consider IO requirements.
Also keep in mind that tasks that can't easily be done in parallel may just as well be done in the CPU allowing you to keep your existing code. Moving data between GPU / CPU is generally very fast.

Hidden Markov Models ATI Stream
remco Jan 14, 2010 6:45 PM (in response to frankas)Hi Frankas,
Sorry for the delayed response but I was away for a couple of days. But thank you for your help up until so far. I thought of how I would implement this on a CUDA enabled card because I am familiar with these cards. Hidden Markov models deal with sequences of observations. Now the elements of a sequence often can not be processed in parallel because the computation of a given element depends on the previous element. But for hidden Markov model training one often has several several sequences of observations. And these sequences can always be processed in parallel. For my problem I have about 700 independent sequences that can be processed in parallel. I thought for a CUDA enabled card the best option is to process 16 independent sequences per thread block. This always given coalesced memory transfers. And a very nice granularity for the number of threads per plock. N*16 were N is the number of states. (Already full occupance when the number of states equals eight)
I also did an experiment with the sse2 instruction set but I was really disapointed with the speedup I got over my c implementation. The algorithm that I implemented in sse2 ran in 119 ms over 700 observations. and the c implementation did it in 124 ms. I concluded that the implementation is heavily memory bound. Otherwise one would expect at least a two times speed up. (two operands are processed in parallel and I did some serious loop unrolling with far more efficient adressing)
Were does dis 288 'threads' minimum come from? 64 threads per wokgroup for each simd processor. But 288 is not a multiple of 64?

Hidden Markov Models ATI Stream
frankas Jan 18, 2010 6:02 AM (in response to remco)Originally posted by: remco Hi Frankas,
Were does dis 288 'threads' minimum come from? 64 threads per wokgroup for each simd processor. But 288 is not a multiple of 64?
I use the 5850 as an example, it has 1440 "stream processing units" in marketing speak. They are organised in 18x16x5  18 SIMD arrays of 16 SPUs (each having 5 processing units). Usually 64 threads will be running on a SIMD array at a time, but this can be adjusted by changing the threading group size (haven't tried this myself). In pratice it means that if a few threads (ex 64) takes k time, then you can schedule 1152 such threads, and they will also complete in k time. But if you schedule 1152 + 64 threads  running time will be 2k.
If your aplpication is memory bound, you probably need to have the group size at 64, as this will hide memory latency. And you should then try to keep your thread count as close as you can to 1152 to ensure full utilization.





