孫詩慧，侯駿騰，王海平

（1.中國電子科技集團(tuán)第十五研究所，北京100083；2.中國科學(xué)院信息工程研究所，北京100093）

0 引言

置信傳播（Belief Propagation，BP）算法是一種在概率圖模型上完成推斷的信息傳遞算法，其廣泛應(yīng)用于數(shù)據(jù)為圖結(jié)構(gòu)的應(yīng)用領(lǐng)域，例如：圖神經(jīng)網(wǎng)絡(luò)、知識(shí)圖譜、5G編碼中的極化碼［1］與低密度奇偶校驗(yàn)編碼［2］等。隨著數(shù)據(jù)獲取與存儲(chǔ)技術(shù)的不斷發(fā)展，需要處理的數(shù)據(jù)規(guī)模越來越大，單純使用CPU處理相應(yīng)的算法已經(jīng)無法滿足快速實(shí)時(shí)的計(jì)算需求。具有幾千甚至幾萬個(gè)線程的GPU設(shè)備為算法的優(yōu)化加速提供了重要的條件，GPU的單指令多線程（Single Instruction Multiple Threads，SIMT）執(zhí)行模式可以對(duì)大量數(shù)據(jù)同時(shí)執(zhí)行相同的操作，從而提升了算法的計(jì)算效率。但是研究表明，在置信傳播算法的計(jì)算中，對(duì)全部未收斂信息同時(shí)進(jìn)行更新不能保證算法達(dá)到最高的計(jì)算效率［3］。因?yàn)橹眯艂鞑ニ惴ㄍㄟ^周圍邊上的信息計(jì)算當(dāng)前頂點(diǎn)的信息，如果周圍的信息均沒有達(dá)到收斂狀態(tài)，則當(dāng)前信息的計(jì)算也是不準(zhǔn)確的，從而造成大量的冗余計(jì)算。并且這些未收斂信息的相互影響導(dǎo)致算法最終的收斂度也不高。

本文針對(duì)以上問題，提出了一種結(jié)合分區(qū)提取與隨機(jī)減少的GPU環(huán)境下的置信傳播算法。首先通過快速分區(qū)的方式將整個(gè)圖數(shù)據(jù)分成若干個(gè)分區(qū)；然后選取每個(gè)分區(qū)中殘差最大的信息進(jìn)行更新，這樣可以保證每次迭代計(jì)算使用較少的時(shí)間對(duì)全局殘差較大的信息進(jìn)行更新；最后，通過逐漸降低所選分區(qū)的數(shù)目保證算法的收斂度逐步上升。

1 相關(guān)工作

在早期的研究中，主要在CPU上進(jìn)行串行的置信傳播算法的計(jì)算。串行算法每次只能更新一條信息，對(duì)于大量未收斂的信息，每次迭代計(jì)算對(duì)殘差最大的信息進(jìn)行更新可有效提升算法的計(jì)算效率［4］。隨著并行計(jì)算設(shè)備計(jì)算能力的提升，并行置信傳播算法的性能優(yōu)勢(shì)逐漸突顯出來。Loopy BP（LBP）是一種最簡(jiǎn)單的并行置信傳播算法，其直接對(duì)所有的未收斂的信息進(jìn)行更新［5］。Joseph等人指出所有未收斂信息的同時(shí)更新無法保證算法性能達(dá)到最優(yōu)［3］，并提出了Residual Splash（RS）算法，其通過選取多個(gè)全局信息殘差最大的頂點(diǎn)，并以此頂點(diǎn)為中心進(jìn)行確定順序的置信傳播計(jì)算，顯著提升了算法的計(jì)算性能。但是這一算法只適用于多核CPU，其中的排序操作在GPU設(shè)備上的計(jì)算非常耗時(shí)。Mark等人通過兩次過濾操作隨機(jī)篩選中部分未收斂的信息進(jìn)行更新，提出了專門針對(duì)GPU的隨機(jī)置信傳播算法（Random Belief Propagation，RnBP）。雖然排序操作不適用于GPU，但是侯駿騰等人提出了ColorWave算法［6］，與Residual Splash（RS）算法具有同樣的信息更新順序。該算法通過著色操作檢測(cè)出多個(gè)分區(qū)，將每個(gè)分區(qū)中著色操作的中心點(diǎn)作為置信傳播計(jì)算的中心點(diǎn)，并以此為中心在每個(gè)分區(qū)中進(jìn)行固定順序的信息更新操作，使圖數(shù)據(jù)中的大多數(shù)信息在短時(shí)間內(nèi)快速收斂。另外，為了提升置信傳播算法每次迭代的計(jì)算效率和算法最終的收斂度，侯駿騰等人還提出了ColorExtract算法與RandomDrop算法。

在基于GPU的各類并行置信傳播算法中，雖然相比于直接對(duì)所有未收斂信息進(jìn)行更新的LBP算法，后來的算法在收斂度與收斂速度上有了很大的提升，但是算法中仍然存在很多的冗余計(jì)算，并且各類算法在置信傳播算法的不同計(jì)算階段中計(jì)算效率差異較大。本文算法充分考慮了不同計(jì)算階段中置信傳播算法的計(jì)算特征。在算法的最初階段，圖數(shù)據(jù)中大多數(shù)信息處于未收斂的狀態(tài)，通過分區(qū)提取的方式更新每個(gè)分區(qū)中殘差最大的信息；隨著迭代的進(jìn)行，越來越多的信息達(dá)到收斂狀態(tài)，并且未收斂的信息相互影響，導(dǎo)致算法整體的收斂度不高。我們通過逐漸降低所選分區(qū)數(shù)目的形式提升算法最終的收斂度。

2 算法實(shí)現(xiàn)

2.1 置信傳播計(jì)算

置信傳播計(jì)算在概率圖上進(jìn)行推斷從而完成信息更新，馬爾科夫隨機(jī)場(chǎng)是一種典型的概率圖，我們以馬爾科夫隨機(jī)場(chǎng)為例介紹置信傳播計(jì)算。圖1（a）是一個(gè)由5個(gè)頂點(diǎn)組成的馬爾科夫隨機(jī)場(chǎng)。以G（V，E）表示馬爾科夫隨機(jī)場(chǎng)對(duì)應(yīng)的圖結(jié)構(gòu)，其中，V為頂點(diǎn)集，E為邊集。每個(gè)頂點(diǎn)vi在標(biāo)簽集Xi中取一個(gè)標(biāo)簽xi。如圖1（a）所示，對(duì)于某個(gè)確定的xi，其對(duì)應(yīng)于一元?jiǎng)莺瘮?shù)Ψi，變量之間的可能關(guān)系對(duì)于二元?jiǎng)莺瘮?shù)Ψi，j，則馬爾科夫隨機(jī)場(chǎng)上X的聯(lián)合分布如式（1）所示。

置信傳播算法通過頂點(diǎn)間的信息更新來更新概率圖模型的標(biāo)記狀態(tài)。如圖1（b）所示，mi→j表示從頂點(diǎn)vi到頂點(diǎn)vj的信息。置信傳播算法的最終目標(biāo)是計(jì)算得到每個(gè)頂點(diǎn)的“置信度”?？梢愿鶕?jù)頂點(diǎn)vi取值的概率分布P（xi）得到當(dāng)前頂點(diǎn)的“置信度”，計(jì)算公式如式（2）所示，其中信息值mi→j的計(jì)算如式（3）所示。在多個(gè)文獻(xiàn)中［3－4，6－7］，通常將前后兩次信息殘差的值小于一個(gè)預(yù)設(shè)的閾值作為判斷算法信息收斂的條件。假設(shè)信息mi→j經(jīng)過t次迭代計(jì)算后變?yōu)樾畔t其信息殘差的計(jì)算如式（4）所示。本文中，我們采用相同的方式判斷置信傳播是否收斂。

圖1 置信傳播計(jì)算示意圖

2.2 算法整體過程

算法根據(jù)用戶預(yù)設(shè)的參數(shù)對(duì)用戶提供的概率圖模型進(jìn)行置信傳播計(jì)算，具體流程如圖2所示。首先加載需要處理的概率圖數(shù)據(jù)與用戶預(yù)設(shè)的參數(shù)，包括需要在多少次分區(qū)提取后再進(jìn)行隨機(jī)減少操作及每次迭代計(jì)算隨機(jī)減少操作的比例。其次，進(jìn)行信息殘差的計(jì)算，由于是首次計(jì)算信息值，無法將前后兩次信息的差作為作為信息殘差，因此直接將當(dāng)前計(jì)算所得的信息值作為信息殘差。分區(qū)提取操作通過當(dāng)前信息與周圍信息殘差的大小關(guān)系判斷需要提取出需要更新的信息。隨機(jī)減少操作根據(jù)當(dāng)前迭代計(jì)算所處的計(jì)算階段對(duì)需要更新的信息進(jìn)一步過濾。通過以上的公式（3）對(duì)兩次過濾后剩余的信息進(jìn)行更新，然后通過公式（4）計(jì)算所有信息的殘差。根據(jù)信息殘差的變化情況判斷算法是否已達(dá)到收斂狀態(tài)；如果未達(dá)到收斂狀態(tài)，則從分區(qū)提取操作開始繼續(xù)進(jìn)行迭代計(jì)算，如果已達(dá)到收斂狀態(tài)，則停止迭代計(jì)算并通過公式（2）計(jì)算每個(gè)頂點(diǎn)的置信度。該算法中的分區(qū)提取策略可以使得算法在計(jì)算的開始階段有較高的收斂速度，分區(qū)提取策略與隨機(jī)減少策略的結(jié)合可以使用算法的收斂度逐步提升，并且使得算法在達(dá)到穩(wěn)定狀態(tài)時(shí)有較高的收斂度。

圖2 置信傳播算法流程

2.3 分區(qū)提取策略

依據(jù)文獻(xiàn)［4］中的結(jié)論，在每次迭代計(jì)算中，相比于隨機(jī)更新任意一個(gè)未收斂的信息，對(duì)殘差最大的信息進(jìn)行更新可以使算法具有更高的收斂速度。但是，在GPU設(shè)備中，對(duì)信息的殘差進(jìn)行排序的算法非常耗時(shí)，并且考慮到具有大規(guī)模并行處理架構(gòu)的GPU設(shè)備可以同時(shí)對(duì)多個(gè)信息進(jìn)行更新處理。本文提出了一種分區(qū)提取策略，該策略可以快速提取出當(dāng)前信息及其鄰接的所有信息中殘差最大的信息，并且只對(duì)該信息進(jìn)行更新處理。相比于對(duì)整個(gè)圖數(shù)據(jù)中所有未收斂的信息同時(shí)進(jìn)行更新處理的傳統(tǒng)并行置信傳播算法及每次只能更新一條信息的串行置信傳播算法，信息分區(qū)提取策略具有以下兩個(gè)優(yōu)勢(shì)：其一，可以對(duì)整個(gè)圖數(shù)據(jù)中所有殘差較大的信息進(jìn)行更新，其中包含整個(gè)圖數(shù)據(jù)中殘差最大的信息，保證算法具有較快的收斂速度，并且減少了并行置信傳播算法中的冗余計(jì)算；其二，如果當(dāng)前信息及其鄰接信息中存在未收斂的信息，則必然會(huì)在這幾條信息中選擇一條信息進(jìn)行更新，這樣在每次迭代計(jì)算時(shí)，有大量的信息參與更新操作，充分利用了GPU的大規(guī)模并行處理能力，提升了算法整體的計(jì)算量。

分區(qū)提取策略的并行處理操作過程為：①為每條信息分配一個(gè)線程，假設(shè)某個(gè)信息mi所在的邊為＜va，vb＞；②將以下所有信息視為處于同一個(gè)分區(qū)中，并對(duì)比各信息的殘差大小情況：信息mi、以頂點(diǎn)va為終點(diǎn)的邊上的信息mx、以頂點(diǎn)vb為終點(diǎn)的邊上的信息my；③將以上分區(qū)中殘差最大的信息標(biāo)記為“需要更新”，其余所有信息標(biāo)記為“不需要更新”，如果所有信息均達(dá)到收斂狀態(tài)，則均標(biāo)記為“不需要更新”。

2.4 隨機(jī)減少策略

在經(jīng)過分區(qū)提取策略處理后，即能保證算法的收斂速度，又能對(duì)保證每次迭代中更新大量的信息。但是，隨著迭代計(jì)算的進(jìn)行，達(dá)到收斂狀態(tài)的信息數(shù)目越來越多，算法的收斂速度逐漸下降，并且當(dāng)算法中未達(dá)到收斂狀態(tài)的信息數(shù)目穩(wěn)定時(shí)，仍然有很多信息沒有達(dá)到收斂狀態(tài)。在文獻(xiàn)［6］中，侯駿騰等人提出，通過逐漸降低信息更新比例的方式，可以進(jìn)一步提高算法的收斂度。因此，本文在分區(qū)提取策略的基礎(chǔ)上增加了隨機(jī)減少策略，通過逐漸減少所選取的分區(qū)的數(shù)目的方式降低整個(gè)圖數(shù)據(jù)中未達(dá)到收斂狀態(tài)的信息的更新比例，使得達(dá)到穩(wěn)定狀態(tài)的置信傳播算法有較高的收斂度。

隨機(jī)減少策略的操作流程及操作目的為：①由用戶預(yù)設(shè)三個(gè)閾值：分區(qū)提取策略操作步數(shù)n、隨機(jī)減少策略減少率pr及信息最小更新率pl；②在算法的前n次處理中，只采用分區(qū)提取策略，不采用隨機(jī)減少策略。在算法的初始階段，大多數(shù)的信息均未達(dá)到收斂狀態(tài)，因此每個(gè)分區(qū)中都會(huì)提取出一條信息進(jìn)行更新操作，并且此時(shí)算法的收斂速度較高。所以，此時(shí)對(duì)所有未達(dá)到收斂狀態(tài)的信息進(jìn)行更新處理；然后根據(jù)隨機(jī)減少策略減少率pr逐漸減少所選分區(qū)數(shù)目，即：在第i次迭代計(jì)算時(shí)，只對(duì)所提取信息中占比為pi的信息進(jìn)行更新，則在第i＋1次迭代計(jì)算時(shí)，需要更新的信息的占比為pi＋1＝pi－pr。隨著迭代的進(jìn)行，算法的收斂速度降低，通過隨機(jī)減少策略可以提升算法收斂速度；最后，當(dāng)信息更新比例pi降低為pl時(shí)，使pi＝pl保持不變，這樣做是為了在每次迭代計(jì)算時(shí)均有一定數(shù)量的信息進(jìn)行更新。

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

實(shí)驗(yàn)環(huán)境為：Intel Core i5-8300H CPU，8G運(yùn)行內(nèi)存與NVIDIA GeForce 1050Ti GPU，4G顯卡內(nèi)存。在CentOS 7.1操作系統(tǒng)下運(yùn)行。編譯器與優(yōu)化設(shè)置為：CUDA Driver Version 10.0，NVCC version 7.5 with-O3 and-arch＝sm_37，GCC 4.8.5－03。實(shí)驗(yàn)所用的概率圖模型為Ising生成圖數(shù)據(jù)，這是一個(gè)由二進(jìn)制變量組成的1500×1500格式的網(wǎng)格圖數(shù)據(jù)。圖3為100秒時(shí)間內(nèi)，采用本文算法、LBP（Loopy Belief Propagation）算法［5］及CE（Color Extract）算法［6］對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理時(shí)，未收斂信息數(shù)隨迭代次數(shù)的變化情況，其中OUR1的參數(shù)為：n＝30，pr＝0.005，pl＝0.2，OUR2的參數(shù)為：n＝20，pr＝0.01，pl＝0.2。從圖中可以看出，相比于對(duì)所有未收斂信息進(jìn)行更新的傳統(tǒng)并行算法，本文算法與CE算法均有較高的收斂速度，并且在算法達(dá)到穩(wěn)定狀態(tài)時(shí)，有較高的收斂度。與CE算法相比，本文算法前期的分區(qū)提取策略與CE算法達(dá)到相近的收斂速度，在采用隨機(jī)減少策略后，本文算法的收斂速度有所下降，但是當(dāng)算法達(dá)到穩(wěn)定狀態(tài)時(shí)，本文算法具有更高的收斂度。

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

4 結(jié)語

本文針對(duì)于在GPU上進(jìn)行并行置信傳播算法計(jì)算時(shí)，大量冗余計(jì)算降低了算法的計(jì)算效率的問題，提出了一種基于分區(qū)提取與隨機(jī)減少的并行置信傳播算法。該算法考慮到并行置信傳播算法在不同計(jì)算階段的算法特征。在算法初始階段，通過對(duì)圖數(shù)據(jù)的快速分區(qū)并選取分區(qū)中殘差最大的信息進(jìn)行更新提升了算法的收斂速度。隨著達(dá)到收斂狀態(tài)的信息數(shù)目的不斷增加，算法的收斂速度下降，通過逐漸減少選取的分區(qū)數(shù)目的方式提升算法的收斂度與收斂速度，保證算法達(dá)到穩(wěn)定時(shí)具有較高的收斂度。但是目前仍采用預(yù)設(shè)參數(shù)的方式減少選取的分區(qū)數(shù)目，通過自適應(yīng)的方式減少選取的分區(qū)數(shù)目是未來的研究重點(diǎn)。