[發明專利]一種GPU上的基于著色優化的置信傳播方法

在審

• 申請號: 202010940174.1
• 申請日: 2020-09-09
• 公開（公告）號: CN112257865A
• 公開（公告）日: 2021-01-22
• 發明（設計）人: 侯駿騰;王樹鵬;吳廣君;張磊;孫嘉偉
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06N5/04
• 分類號: G06N5/04;G06T1/20
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

本發明公開了一種GPU上的基于著色優化的置信傳播方法。本發明通過使用信息殘差大的頂點對信息殘差小的頂點進行固定步長的著色操作，在整個圖模型上形成多個以信息殘差大的頂點為中心的分區，將該頂點命名為中心點；在每個分區中，按照最遠頂點到中心點以及中心點到最遠點的順序對邊上的信息進行更新操作，以完成每次迭代的置信傳播計算。本發明能夠保證置信傳播方法在短時間內收斂大多數頂點。

技術領域

本發明涉及使用異構系統進行置信傳播計算的方法，具體的說是一種GPU上的基于著色優化的置信傳播方法。

背景技術

置信傳播(Belief Propagation,BP)是一種在概率隨機圖上進行近似推斷的信息傳遞算法，它是很多重要領域的基礎算法，包括：在通信領域廣泛應用的極化碼編碼(Polarcodes)和低密度奇偶校驗編碼(Low-Density Parity-Check,LDPC)、計算機視覺、蛋白質折疊等。例如：在計算機視覺中，立體匹配和圖像去噪這種“像素標記”相關的應用需求可以直接看成最大后驗(MAP)問題，這些問題可以通過最大乘積置信傳播方法(Max-Product BP)成功解決。在概率圖模型中，每個結點表示一個隨機變量，其按照不同的概率取不同的標記值，結點之間的邊表示這些隨機變量之間的概率關系。其中，所有隨機變量的聯合概率分布可以表示成若干隨機變量子集的乘積。置信傳播算法利用結點與結點之間相互傳遞信息而更新當前整個概率圖模型的標記狀態。置信傳播的計算往往需要多次迭代。經過多次迭代，無環路的概率圖模型可以保證所有結點的置信度不再發生變化，即所有結點達到收斂狀態。有環路的概率圖模型不能保證所有結點達到收斂狀態，但在多次迭代后，其未收斂的結點數目會逐漸穩定。早期的置信傳播大多為串行方法，通過調整邊上信息的更新順序達到性能優化的效果。如：殘差置信傳播(Residual belief propagation,RBP)每次只更新信息殘差最大的邊上的信息。Loopy BP(LBP)是最直接的并行方案，其每次迭代更新所有未收斂邊上的信息。但是研究表明這種方法最終的收斂度非常低。Residual Splash(RS)方法以信息殘差最大的點為中心，按廣度優先遍歷順序的正、反方向對邊上的信息進行更新。近些年來，圖形處理器(Graphics Processing Units，GPU)在并行圖計算領域得到了廣泛的應用，信息更新計算是置信傳播中的主要計算任務，其非常適合于并行處理，因此GPU能顯著提升置信傳播計算的速度。RnBP方法是一種在GPU上實現的置信傳播算法，其按一定比例更新未收斂信息使算法在收斂速度與收斂度間進行權衡。以上方法都存在明顯缺陷，RS方法中的頂點排序操作不適合GPU的并行架構，并且RS需要申請大量內存來記錄每個步長中需要處理的頂點值。而RnBP算法未考慮信息的更新順序，導致計算資源的浪費。

發明內容

針對現有技術中存在的技術問題，本發明的目的在于提供一種GPU上的基于著色優化的置信傳播方法，本發明充分考慮GPU的架構特征與置信傳播中信息更新順序，作為提升并行置信傳播計算效率的關鍵因素，利用著色操作對未收斂的信息進行分區并規定更新順序，提升了置信傳播方法整體的運行效率，并根據用戶的不同計算需求，提出不同的置信傳播方法，對相應的計算階段進行專門優化。

本發明的技術方案如下：

一種GPU上的基于著色優化的置信傳播方法，其步驟包括：

1)將需要處理的概率圖數據G(V,E,Ψ)加載到設備內存中；其中V為概率圖的頂點集，E為概率圖的邊集，Ψ為概率集，包括概率圖中每個頂點取不同標記的概率值和每條邊對應的轉移概率值；每個頂點v_i對應于集合中的一個離散隨機變量X_i，n為頂點總數，X_i∈A_i，A_i為有限標簽集；每一條邊(v_i,v_j)對應于兩個頂點v_i和v_j上變量不同取值之間的概率關系；設置每次著色操作的迭代次數C_n、判斷信息是否收斂的閾值ξ以及置信傳播結束計算的時間閾值T_ξ；