[發明專利]一種基于OpenCL的FPGA圖處理加速方法和系統

有效

• 申請號: 201911029448.5
• 申請日: 2019-10-25
• 公開（公告）號: CN110852930B
• 公開（公告）日: 2021-06-29
• 發明（設計）人: 廖小飛;趙杰山;鄭龍;金海;王慶剛
• 申請（專利權）人: 華中科技大學
• 主分類號: G06T1/20
• 分類號: G06T1/20;G06F15/78;G06F9/30;G06F9/38
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智

本發明公開了一種基于OpenCL的FPGA圖處理加速方法和系統，屬于大數據處理領域。包括：根據反匯編得到的中間代碼IR，生成完整的控制數據流圖CDFG；對完整的CDFG圖，根據Load和Store指令進行重新分塊，得到新的CDFG指令塊，確定各CDFG指令塊之間的并行模式；對所有新CDFG指令塊中的Load和Store指令進行分析，確定FPGA片上BRAM的劃分方式；采用所述BRAM的劃分方式，對FPGA片上內存進行重新組織，根據指令塊之間的并行模式，將所有新CDFG指令塊翻譯成相應的硬件描述語言，編譯生成可在FPGA上面運行的二進制文件，燒至到FPGA上面進行運行。本發明采用管道技術和重新調整指令塊中指令，減少訪存次數，降低訪存延時；采用片上存儲分塊，減少不同流水線對同一個內存塊的寫沖突，從而提升系統效率。

技術領域

本發明屬于大數據處理技術領域，更具體地，涉及一種基于OpenCL的FPGA圖處理加速方法和系統。

背景技術

圖是一種經典的數據結構，在理論方面有圖論領域，同時在現實生活中，很多關系都可以轉化抽象為圖。比如說電力數據分析、社交網絡、交易網絡、交通網絡等等。人們通過分析網絡的特征來獲取想要的信息。比如說設計網絡中獲取哪些人物是“網絡紅人”，交通網絡中獲取兩個地方的最優路線等等。圖計算就是將上述常見的現實問題抽象為幾個經典的問題，如SSSP算法即獲取兩點之間的最短距離，PageRank算法即獲取每一個節點的重要程度等。經典的圖計算包括PageRank、BFS、DFS、SSSP等。如何快速獲取這些圖計算的結果是一個具有挑戰性的問題。

基于GPU的圖計算加速系統，由于使用GPU平臺的功耗和能耗過高，而基于傳統通用處理器CPU的計算效率有限，因此，為了提高圖計算的計算和訪存效率，一種基于定制硬件的方式進行圖計算加速的方式應用而生。其中包括基于ASIC的圖計算加速器和基于FPGA的圖計算加速器。雖然基于ASIC的圖計算加速器具有更高的計算效率，但是其本身靈活性不足，在面對多種圖計算算法的時候，FPGA可重構性的特定更能適應。使用FPGA作為圖計算系統的硬件平臺相比CPU具有更高的并行度，相比GPU具有更高的能效。

已有的基于FPGA的圖計算系統主要有兩類，即CPU-FPGA的異構系統以及基于FPGA的圖計算系統。基于CPU-FPGA的異構系統主要是考慮到圖數據本身的Power-Law特性，其中CPU是一種通用處理器，對計算和訪存分散的任務比較友好，而針對計算和訪存密集型的任務可以使用FPGA進行加速。首先，FPGA具有大量的可編程邏輯單元，可以針對不同的算法設計特定的片上邏輯，而且這些片上邏輯還可以實現流水線，從而實現高并行度，所以使用FPGA對計算和訪存密集型的任務進行加速是非常合理的。然而，如何確定任務是適合在CPU上進行執行還是適合在FPGA上進行執行顯得尤為重要和困難。現有的一些策略是根據節點的度數來確定適合在哪種平臺上面進行運行，節點的度數很小，意味著是適合在CPU上面進行計算；節點度數很大，意味著適合在FPGA上面進行計算。然而，這種方式有很大的缺點：(1)上述的決策策略是一種靜態的方式，對于動態過程中產生的分散節點無法判斷。有很多圖計算算法是根據節點的收斂與否來確定該節點在下一次迭代過程中是否需要計算。這樣就會導致節點度數很大的點在迭代過程中的有效邊減少，從而將一個計算或訪存密集型的節點變成一個計算或訪存分散的節點，從而使系統整體性能變差。(2)CPU和FPGA之間信息的同步。由于CPU負責一部分計算任務，FPGA負責另外一部分計算任務。而且，大部分情況下，這兩部分計算任務之間通常有依賴關系或者需要進行信息同步的操作。這時，需要將FPGA或者CPU計算的中間結果通過PCIe總線進行信息的同步。如果說這兩部分之間進行頻繁的通信，勢必會對整體的性能產出很大的影響。基于FPGA的圖計算系統是將整個圖計算算法通過FPGA上的可編程邏輯單元進行實現。相比于上述的異構執行模式，去掉了通信的開銷，然而也帶了很多問題：(1)對于計算或者訪存不是很密集的任務，浪費了FPGA高并行度的優勢。(2)FPGA片上緩存有限，如何在有限資源的前提下達到很高的性能，這對開發用戶來說很不友好。