[發明專利]基于FPGA異構平臺的馬爾科夫蒙特卡洛算法加速方法

在審

• 申請號: 201710632320.2
• 申請日: 2017-07-28
• 公開（公告）號: CN107423030A
• 公開（公告）日: 2017-12-01
• 發明（設計）人: 張新;陳繼承;王洪偉
• 申請（專利權）人: 鄭州云海信息技術有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京集佳知識產權代理有限公司11227
• 代理人: 羅滿

技術領域

本發明涉及計算機應用技術領域，特別涉及一種基于FPGA異構平臺的馬爾科夫蒙特卡洛算法加速方法及系統。

背景技術

隨著計算技術的發展蒙特卡洛算法的應用場景越來越多，例如分子動力學、量子計算，計算化學等，蒙特卡洛算法有很多種實現方式，其中基于重要性采樣(Metropolis采樣)的馬爾科夫鏈蒙特卡洛(Markov Chain Monte Carlo,MCMC)是應用最廣泛的方法，MCMC的基礎理論為馬爾科夫過程，其過程為，首先構造一個已知的概率空間使該概率空間和原始積分函數盡可能相似，為了在該分布上采樣需從任一狀態出發，不斷進行狀態轉移，最終收斂到平穩分布。穩定后可以做加權平均。隨著計算場景的復雜度提高，原有的串行算法已經無法勝任，研究并行蒙特卡洛算法迫在眉睫。

現有技術中，并行蒙特卡洛算法應用最多的是基于馬爾科夫鏈的并行和數值計算的并行。馬爾卡夫鏈的并行，MCMC這種特殊的結構特別適合并行計算，可以用每個線程(或者進行)計算一條馬爾科夫鏈，每條馬爾科夫鏈之間不需要通信，所以并行效率較高，這種方法的問題是由于每條馬爾科夫鏈需要預熱(剛開始的樣本需要去除)，所以會造成計算資源的浪費，而且并行度和核數呈正比，這種方法依賴于大規模計算技術(尤其是集群)，所以成本較高；數值計算的并行，只生成一條馬爾卡夫鏈，數據計算部分并行，這種方式預熱成本較小，但是需要通信，所以并行效率較低。而且并行度也依賴于核數，也是以集群為基礎的，所以成本也較高。因此，如何實現高效率的并行蒙特卡洛算法，并且減低所需的成本，是現今急需解決的問題。

發明內容

本發明的目的是提供一種基于FPGA異構平臺的馬爾科夫蒙特卡洛算法加速方法及系統，以利用FPGA(Field－Programmable Gate Array，現場可編程門陣列)對蒙特卡洛算法進行并行流水加速，減少成本，同時提高并行效率。

為解決上述技術問題，本發明提供一種基于FPGA異構平臺的馬爾科夫蒙特卡洛算法加速方法，包括：

主機端完成初始化，并將產生的隨機數數據通過PCI-e接口發送到FPGA端的DDR內存；其中，所述初始化包括構造概率空間和產生隨機數；

所述FPGA端讀取所述DDR內存中的所述隨機數數據，并利用構造的馬爾科夫鏈對所述隨機數數據進行并行的流水線運算，獲取并發送對應的結果數據到所述主機端。

可選的，所述利用構造的馬爾科夫鏈對所述隨機數數據進行并行的流水線運算，包括：

利用#pragma unroll的方式將所述馬爾科夫鏈完全展開；

展開的每條馬爾科夫鏈分別采用流水的方式對所述隨機數數據中的部分數據進行運算；其中，所述部分數據中的隨機數的數量為所述隨機數數據中的隨機數的數量除以所述馬爾科夫鏈的數量。

可選的，所述利用#pragma unroll的方式將所述馬爾科夫鏈完全展開之前，還包括：

根據所述隨機數數據中的隨機數的數量，構造所述馬爾科夫鏈。

可選的，該方法還包括：

所述主機端對接收的所述結果數據進行積分運算；其中，所述積分運算包括加權平均運算。

此外，本發明還提供了一種基于FPGA異構平臺的馬爾科夫蒙特卡洛算法加速系統，包括：

主機端，用于完成初始化，并將產生的隨機數數據通過PCI-e接口發送到FPGA端的DDR內存；其中，所述初始化包括構造概率空間和產生隨機數；

所述FPGA端，用于讀取所述DDR內存中的所述隨機數數據，并利用構造的馬爾科夫鏈對所述隨機數數據進行并行的流水線運算，獲取并發送對應的結果數據到所述主機端。

可選的，所述FPGA端，包括：

展開模塊，用于利用#pragma unroll的方式將所述馬爾科夫鏈完全展開；

運算模塊，用于展開的每條馬爾科夫鏈分別采用流水的方式對所述隨機數數據中的部分數據進行運算；其中，所述部分數據中的隨機數的數量為所述隨機數數據中的隨機數的數量除以所述馬爾科夫鏈的數量。

可選的，所述FPGA端，還包括：

構造模塊，用于根據所述隨機數數據中的隨機數的數量，構造所述馬爾科夫鏈。

可選的，所述主機端，還包括：

積分模塊，用于對接收的所述結果數據進行積分運算；其中，所述積分運算包括加權平均運算。