[發明專利]GPU上的基于邊著色與信息更新率優化的置信傳播方法

在審

• 申請號: 202010940904.8
• 申請日: 2020-09-09
• 公開（公告）號: CN112257866A
• 公開（公告）日: 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上的基于邊著色的置信傳播方法，其步驟包括：