摘 要：隱馬爾可夫模型（HMM）是建立在馬爾可夫鏈的基礎(chǔ)上的統(tǒng)計(jì)模型。雖然隱馬爾可夫模型是一種計(jì)算高效的機(jī)器學(xué)習(xí)模型，但是當(dāng)處理的數(shù)據(jù)集規(guī)模過于龐大時(shí)，分析的時(shí)間太長。因此，我們有必要研究隱馬爾可夫模型的并行化設(shè)計(jì)，以提高模型的運(yùn)算速度。近年來，開放計(jì)算語言（OpenCL）的出現(xiàn)，使得設(shè)計(jì)通用的并行程序成為可能。該文，我們分析了隱馬爾可夫模型三類算法的并行特性，并設(shè)計(jì)基于OpenCL的并行實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，隱馬爾可夫模型在GPU上的并行化實(shí)現(xiàn)最高獲得了640倍的加速比。

關(guān)鍵詞：隱馬爾可夫模型 GPU通用計(jì)算 OpenCL 并行計(jì)算

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2013）05（c）-0030-02

隱馬爾可夫模型作為一個(gè)時(shí)間序列的統(tǒng)計(jì)分析模型在語音識別、生物序列分析等領(lǐng)域中有著重要的應(yīng)用。雖然HMM是一種計(jì)算高效的機(jī)器學(xué)習(xí)模型，但是當(dāng)處理數(shù)百萬長度的序列或同時(shí)處理多個(gè)序列時(shí)，分析的時(shí)間往往需要幾小時(shí)、幾天。因此，設(shè)計(jì)HMM的并行算法，提升模型的訓(xùn)練速度，具有重要的意義。

在該文，我們詳細(xì)分析了HMM相關(guān)的三類關(guān)鍵算法的并行化設(shè)計(jì)，并在對三種關(guān)鍵算法深入研究的基礎(chǔ)上，開發(fā)了基于開放式計(jì)算語言（OpenCL）的并行實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明在各種情況下獲得了良好的加速比性能。

1 隱馬爾可夫模型

隱馬可夫模型實(shí)際上是一個(gè)雙重的隨機(jī)過程，由一個(gè)隱藏的具有有限狀態(tài)的馬爾可夫鏈和一個(gè)與馬爾可夫鏈狀態(tài)相關(guān)聯(lián)的隨機(jī)函數(shù)集組成。本文只專注于離散時(shí)間系統(tǒng)。

為了方便討論，根據(jù)文獻(xiàn)[1]，本文首先定義一些基本符號：

（1）隱藏的狀態(tài)集合記為

，

其中為狀態(tài)個(gè)數(shù)，并記時(shí)刻的狀態(tài)為，；

（2）觀察值的取值集合記為

，

其中為可能取值的個(gè)數(shù)，并記時(shí)刻的觀察值為，；

（3）當(dāng)步長為1時(shí)，條件概率為轉(zhuǎn)移概率，簡記為，所有的構(gòu)成轉(zhuǎn)移概率矩陣，且；

（4）觀察值的概率分布矩陣設(shè)為，每個(gè)代表從一個(gè)狀態(tài)生成觀察值的概率，即；

（5）初始的狀態(tài)概率分布向量記為，其中，；

（6）確定了、和后，HMM由參數(shù)所描述。

根據(jù)文獻(xiàn)[1]，HMM所涉及的3個(gè)基本問題分別為評估問題、識別問題和學(xué)習(xí)問題，其描述分別下：

①評估問題指的是在給定模型和觀察序列的情況下，如何計(jì)算條件概率；

②識別問題指的是在給出模型和觀察序列的情況下，如何選擇最佳的狀態(tài)序列；

③學(xué)習(xí)問題是指給定觀察序列的情況下，如何有效地調(diào)用模型，使得條件概率最大。

對應(yīng)于上述隱馬爾可夫模型三個(gè)基本問題的求解，相應(yīng)的解決方案分別為：前向（Forward）算法、Viterbi算法、Baum-Welch算法。三種算法的具體描述均可在[1]一文找到。

2 OpenCL簡介

OpenCL是一個(gè)面向異構(gòu)平臺編程的開放性計(jì)算語言，其將各類計(jì)算設(shè)備抽象成為一個(gè)統(tǒng)一的平臺。OpenCL將并行設(shè)備看成為由一個(gè)或多個(gè)計(jì)算單元（CU）組成，而CU又由一個(gè)或多個(gè)處理單元（PE）組成，CU可以看成為一個(gè)單指多數(shù)據(jù)流處理器。在設(shè)備端執(zhí)行的一個(gè)完整程序稱為核函數(shù)。

OpenCL的執(zhí)行模型是在工作空間的每個(gè)工作節(jié)點(diǎn)上執(zhí)行一份核函數(shù)的拷貝，每個(gè)工作節(jié)點(diǎn)擁有自己的唯一的標(biāo)識，核函數(shù)可以根據(jù)工作節(jié)點(diǎn)的標(biāo)識來劃分每個(gè)工作節(jié)點(diǎn)處理的數(shù)據(jù)范圍，從而達(dá)到單指令多數(shù)據(jù)流的執(zhí)行描述。該工作空間可以采用工作組對工作節(jié)點(diǎn)進(jìn)一步細(xì)分，每一個(gè)工作組在一個(gè)CU上執(zhí)行。OpenCL的出現(xiàn)有效地解決了平臺異構(gòu)性所帶來的各種兼容性問題。

3 并行化設(shè)計(jì)

3.1 前向算法與Viterbi算法的并行化設(shè)計(jì)

針對前向算法，在算法1中的第3行循環(huán)內(nèi)部，可以并行地計(jì)算每個(gè)時(shí)刻下所有狀態(tài)的前向概率。以計(jì)算為例，如圖1的虛線所示。因此，我們可以將每個(gè)前向概率的計(jì)算分配給一個(gè)工作組執(zhí)行，而在工作組內(nèi)部，使用并行縮減[2]的方式進(jìn)行并行求和（如表1）。

Viterbi算法的并行化策略與前向算法是一致的，只是將并行求和改為并行求最大值，并記錄下相應(yīng)的狀態(tài)指針。在此不詳細(xì)介紹。

3.2 Baum-Welch的并行化設(shè)計(jì)

針對算法2，該文采用先行計(jì)算所有時(shí)刻的前向概率α和后向概率β的策略，然后在每一時(shí)刻，使用一個(gè)工作組計(jì)算一個(gè)狀態(tài)均值：一個(gè)工作節(jié)點(diǎn)計(jì)算一個(gè)序列中的一個(gè)狀態(tài)值（算法2中的第5行循環(huán)），然后再采用并行縮減的方式求得每一個(gè)狀態(tài)的均值。這樣設(shè)計(jì)存在的問題是算法的空間復(fù)雜度高達(dá)，然而由于序列與序列之間擁有很好的獨(dú)立性，當(dāng)較大、較小的情況下，可以大大縮減算法對空間的要求（如表2）。

4 實(shí)驗(yàn)結(jié)果

在本節(jié)中我們給出各類算法的實(shí)驗(yàn)數(shù)據(jù)。由于前向算法和Viterbi算法的并行化設(shè)計(jì)策略是一致的，所以我們重點(diǎn)分析前向算法在GPU上的加速性能。實(shí)驗(yàn)環(huán)境為IntelCorei5-2460M、4GB內(nèi)存和GeForcegt240顯卡，顯存為1GB。

前向算法并行實(shí)驗(yàn)結(jié)果如表3所示。當(dāng)數(shù)據(jù)規(guī)模為512×512時(shí)，在CPU上執(zhí)行的運(yùn)行時(shí)間接近7 min，而在GPU上執(zhí)行的OpenCL程序只需要0.6 s便可完成計(jì)算的過程，獲得了640倍左右的加速比。

Baum-Welch算法并行實(shí)驗(yàn)結(jié)果如表4所示。從表4可以看出，并行程序在GPU上的執(zhí)行仍然獲得了較好的加速比，在數(shù)據(jù)規(guī)模為512×512時(shí)，串行執(zhí)行使用20.4 min，而OpenCL程序僅使用8 s，獲得了150倍左右的加速比。

5 結(jié)語

該文設(shè)計(jì)隱馬爾可夫模型的三個(gè)經(jīng)典算法基于OpenCL的并行化實(shí)現(xiàn)。結(jié)果表明，基于OpenCL的并行實(shí)現(xiàn)獲得了最高640倍的加速比。然而我們的并行程序仍未達(dá)到硬件的性能峰值，未來我們將進(jìn)一步驗(yàn)證程序在不同硬件平臺下的加速性能。

參考文獻(xiàn)

[1]Rabiner，Lawrence R.\"A tutorial on hidden Markov models and selected applications in speech recognition.\"Proceedings of the IEEE 77.2（1989）：257-286.

[2]Bryan Catanzaro.OpenCL Optimization Case Study：Simple Reductions.AMD Developer Central，2010.