FPGA implementation of logarithmic versions of Baum-Welch and Viterbi algorithms for reduced precision hidden Markov models

• Autorzy: Pietras M. , Klęsk P.

Identyfikatory

DOI

10.1515/bpasts-2017-0101

• Języki publikacji: EN

Abstrakty

EN

This paper presents a programmable system-on-chip implementation to be used for acceleration of computations within hidden Markov models. The high level synthesis (HLS) and “divide-and-conquer” approaches are presented for parallelization of Baum-Welch and Viterbi algorithms. To avoid arithmetic underflows, all computations are performed within the logarithmic space. Additionally, in order to carry out computations efficiently – i.e. directly in an FPGA system or a processor cache – we postulate to reduce the floating-point representations of HMMs. We state and prove a lemma about the length of numerically unsafe sequences for such reduced precision models. Finally, special attention is devoted to the design of a multiple logarithm and exponent approximation unit (MLEAU). Using associative mapping, this unit allows for simultaneous conversions of multiple values and thereby compensates for computational efforts of logarithmic-space operations. Design evaluation reveals absolute stall delay occurring by multiple hardware conversions to logarithms and to exponents, and furthermore the experiments evaluation reveals HMMs computation boundaries related to their probabilities and floating-point representation. The performance differences at each stage of computation are summarized in performance comparison between hardware acceleration using MLEAU and typical software implementation on an ARM or Intel processor.

Słowa kluczowe

EN

hidden Markov models; numerical stability; Viterbi algorithm; parallel architecture; field-programmable gate array

PL

ukryte modele Markowa; stabilność numeryczna; algorytm Viterbiego; architektura równoległa

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2017
• Tom: Vol. 65, nr 6
• Strony: 935--946
• Opis fizyczny: Bibliogr. 33 poz., rys., wykr., tab.

Twórcy

autor

Pietras M.

autor

Klęsk P.

• Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, 49 Żołnierska Street, Szczecin, Poland

Bibliografia

• [1] J.-F. Mari and F. L. Ber, “Temporal and spatial data mining with second-order hidden Markov models”, Soft Computing 10 (5), 406–414, 2005. doi 10.1007/s00500‒005‒0501‒0
• [2] A. Panuccio, M. Bicego, and V. Murino, “A hidden Markov model-based approach to sequential data clustering”, Structural, Syntactic, and Statistical Pattern Recognition, 734–743, 2002. doi 10.1007/3‒540‒70659‒3_77
• [3] M. Narasimhan, P.A. Viola, and M. Shilman, “Online decoding of Markov models under latency constraints”, in ICML, pp. 657‒664, 2006. doi 10.1145/1143844.1143927
• [4] R.E.F. Behnam, “Stats-calculus pose descriptor feeding a discrete HMM low-latency detection and recognition system for 3D skeletal actions”, arXiv preprint arXiv:1509.09014, 2015.
• [5] M. Shannon, H. Zen, and W. Byrne, “Autoregressive models for statistical parametric speech synthesis”, EEE Trans. Audio Speech Language Process. 21, 587–597, 2013. doi 10.1109/tasl.2012.2227740
• [6] M. Kubanek, J. Bobulski, and L. Adrjanowicz, “Characteristics of the use of coupled hidden Markov models for audio-visual Polish speech recognition”, Bull. Pol. Ac.: Tech. 60 (2), 307‒316, 2012. doi 10.2478/v10175‒012‒0041‒6
• [7] A. Mannini, V. Genovese, and A. M. Sabatini, “Online decoding of hidden Markov models for gait event detection using footmounted gyroscopes”, IEEE Journal of Biomedical and Health Informatics 18 (4), 1122‒1130, 2014. doi 10.1109/jbhi.2013.2293887
• [8] A. Manandhar, P.A. Torrione, L.M. Collins, and K.D. Morton, “Multiple-instance hidden Markov model for gpr-based landmine detection”, IEEE Transactions on Geoscience and Remote Sensing 53 (4), 1737‒1745, 2015. doi 10.1109/tgrs.2014.2346954
• [9] K. Taehwan and B. Keunsung, “HMM-based underwater target classification with synthesized active sonar signals”, IEICE Trans. Fundamentals E94-A (10, 2039‒2042, 2011. doi 10.1587/transfun.e94.a.2039
• [10] U.K. Singh, V. Padmanabhan, and A. Agarwal, “Dynamic classification of ballistic missiles using neural networks and hidden Markov models”, Applied Soft Computing 19, 280‒289, 2014. doi 10.1016/j.asoc.2014.02.015
• [11] O.A. Bapat, R.M. Fastow, and J. Olson, “Acoustic coprocessor for hmm based embedded speech recognition systems”, IEEE Transactions on Consumer Electronics 59 (3), 629‒633, 2013. doi 10.1109/TCE.2013.6626249
• [12] Y. Choi, K. You, J. Choi, and W. Sung, “A real-time FPGA-based 20,000-word speech recognizer with optimized DRAM access”, IEEE Trans. Circuits Syst. I, Reg. Papers 57 (8), 2119‒2131, 2010. doi 10.1109/tcsi.2010.2041501
• [13] C.H. Hsieh, H.P. Chu, and Y. H. Huang, “An HMM-based eye movement detection system using EEG brain-computer interface”, 2014 IEEE International Symposium on Circuits and Systems (ISCAS), 662‒665, Melbourne VIC, 2014. doi 10.1109/ISCAS.2014.6865222
• [14] Y. Lyu, Q. Pan, C. Zhao, H. Zhu, T. Tang, and Y. Zhang, “A vision based sense and avoid system for small unmanned helicopter”, 2015 International Conference on Unmanned Aircraft Systems (ICUAS), 586‒592, Denver, 2015. doi 10.1109/ICUAS.2015.7152339
• [15] L.R. Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition”, Proceedings of the IEEE 77 (2), 257–286, 1989. doi 10.1016/b978‒0‒08‒051584‒7.50027‒9
• [16] D.G. Brown and D. Golod, “A tutorial of techniques for improving standard hidden Markov model algorithms”, J. Bioinformatics and Computational Biology 7, 737‒754, 2009. doi 10.1142/s0219720009004242
• [17] G. Chrysos et al., “Opportunities from the use of FPGAs as platforms for bioinformatics algorithms”, International Conference on Bioinformatics & Bioengineering (BIBE), 559‒565, Larnaca, 2012. doi 10.1109/BIBE.2012.6399733
• [18] I. Atef, E. Hamed, A. Abdullah, and G. Fayez, “Reconfigurable hardware accelerator for profile hidden Markov models”, Arabian Journal for Science and Engineering 41 (8), 3267‒3277, 2016. doi 10.1007/s13369‒016‒2162-y
• [19] F.L. Vargas, R.D.R. Fagundes, and D.B. Junior, “A FPGA-based Viterbi algorithm implementation for speech recognition systems”, IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’01) 2, 1217‒1220, 2001. doi 10.1109/ICASSP.2001.941143
• [20] Y. Sun, P. Li, G. Gu, Y. Wen, Y. Liu, and D. Liu, “Accelerating HMMer on FPGAs using systolic array based architecture”, Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS ‘09), 2009. doi 10.1109/ipdps.2009.5160927
• [21] T. Majumder, P. Pande, and A. Kalyanaraman, “Hardware accelerators in computational biology: application, potential, and challenges”, IEEE Design & Test 31 (1), 8‒18, 2014. doi 10.1109/MDAT.2013.2290118
• [22] A. Churbanov and S. Winters-Hilt, “Implementing EM and Viterbi algorithms for hidden Markov model in linear memory”, BMC Bioinformatics 9, 1‒15, 2008. doi 10.1186/1471‒2105‒9‒224
• [23] U.R. Tatavarty, “Implementation of numerically stable hidden Markov model”, UNLV Theses, Dissertations, Professional Papers, and Capstones. Paper 1018, 2011.
• [24] D. Varma, D. Mackay, and P. Thiruchelvam, “Easing the verification bottleneck using high level synthesis”, 28th VLSI Test Symposium (VTS), 253‒254, Santa Cruz, 2010. doi 10.1109/VTS.2010.5469565
• [25] D. O’Loughlin, A. Coffey, F. Callaly, D. Lyons, and F. Morgan, “Xilinx vivado high level synthesis: case studies”, Irish Signals and Systems Conference 2014, Limerick, 352‒356, 2014. doi 10.1049/cp.2014.0713
• [26] A.T. Anisha and C. Sunitha, “A hybrid Parts Of Speech tagger for Malayalam language”, International Conference on Advances in Computing, Communications and Informatics, 1502‒1507, Kochi, 2015. doi 10.1109/ICACCI.2015.7275825
• [27] T.P. Mann, “Numerically stable hidden Markov model implementation”, HMM scaling tutorial, 1‒8, 2006.
• [28] O. Vinyals and G. Friedland, “A Hardware-independent fast logarithm approximation with adjustable accuracy”, IEEE International Symposium on Multimedia, 61‒65. Berkeley, 2008. doi 10.1109/ISM.2008.83
• [29] U. Dhawan and A. DeHon, “Area-efficient near-associative memories on FPGAs”, ACM Transactions on Reconfigurable Technology and Systems 7 (4), 30‒41, 2015. doi 10.1145/2435264.2435298
• [30] D. Knuth, “The art of computer programming”, Section 5.2.4: Sorting by Merging. Sorting and Searching. 2nd ed. Addison-Wesley. 158–168, 1998.
• [31] Jun Li, Shuangping Chen, and Yanhui Li. “The fast evaluation of hidden Markov models on GPU”, IEEE International Conference on Intelligent Computing and Intelligent Systems, 426‒430, Shanghai, 2009. doi 10.1109/icicisys.2009.5357649
• [32] L. Yu, Y. Ukidave, and D. Kaeli, “GPU-Accelerated HMM for speech recognition”, 43rd International Conference on Parallel Processing Workshops, Minneapolis, 395‒402, 2014. doi 10.1109/ICPPW.2014.59
• [33] M. Pietras, “Hidden Markov models with affix based observation in the field of syntactic analysis”, In: Hard and Soft Computing for Artificial Intelligence, Multimedia and Security, S. Kobayashi, A. Piegat, J. Pejaś, I. El Fray, J. Kacprzyk J. (eds) 534, 17‒26, Springer, Cham, 2016. doi 10.1007/978‒3‒319‒48429‒7_2

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).