GPU-Aware Genetic Estimation of Hidden Markov Models for Workload Classification Problems

Hidden Markov models (HMM) have been an important analysis framework in many computer science applications. The estimation of the HMM parameters is crucial as regards the performance of the whole HMM. Generally, HMM parameters estimation is performed with iterative algorithm like the Baum-Welch method, or gradient based methods. The advantage of the iterative algorithms is their computational efficiency. The disadvantage is that their performance depend on the initial value of the parameters and thus they usually yield to local optimum parameter values. In this paper, a Genetic Algorithm (GA) is used to compute optimized HMM parameters. The algorithm has been implemented on a GPU to face the high demand of computational resources of GA. We used this optimized computation of HMM parameters in a process workload classification, and we made experimental assessment and analysis via using the well-known SPEC-2006 benchmarks. The obtained classification accuracy is significantly better than that obtained with the Baum-Welch algorithms. On the other hand, the time needed to obtain the HMM parameters is of the same order than that required by Baum-Welch algorithm.