基于OpenCL的隱馬爾可夫模型的GPU并行實現(xiàn)

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

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

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

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

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

1 隱馬爾可夫模型

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

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

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

，

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

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

，

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

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

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

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

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

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

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

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

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

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

2 OpenCL簡介

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

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

3 并行化設(shè)計

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

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

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

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

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

4 實驗結(jié)果

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

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

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

5 結(jié)語

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

參考文獻

[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.