基于GPU的并行置信傳播算法優化加速研究

孫詩慧，侯駿騰，王海平

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

0 引言

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

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

1 相關工作

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

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

2 算法實現

2.1 置信傳播計算

置信傳播計算在概率圖上進行推斷從而完成信息更新，馬爾科夫隨機場是一種典型的概率圖，我們以馬爾科夫隨機場為例介紹置信傳播計算。圖1（a）是一個由5個頂點組成的馬爾科夫隨機場。以G（V，E）表示馬爾科夫隨機場對應的圖結構，其中，V為頂點集，E為邊集。每個頂點vi在標簽集Xi中取一個標簽xi。如圖1（a）所示，對于某個確定的xi，其對應于一元勢函數Ψi，變量之間的可能關系對于二元勢函數Ψi，j，則馬爾科夫隨機場上X的聯合分布如式（1）所示。

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

圖1 置信傳播計算示意圖

2.2 算法整體過程

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

圖2 置信傳播算法流程

2.3 分區提取策略

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

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

2.4 隨機減少策略

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

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

3 實驗結果

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

圖3 實驗結果

4 結語

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