得益于大數據的興起和計算能力的快速提升，機器學習技術近年來經歷了革命性的發展。諸如圖像分類、語音識別和自然語言處理等機器學習任務，都是對具有一定大小、維度和有序排列的歐幾里得數據進行處理。然而，在許多現實場景中，數據是由復雜的非歐幾里得數據（例如圖形）表示的。這些圖形不僅包含數據，還包含數據之間的依賴關系，例如社交網絡、蛋白質分子結構、電子商務平臺中的客戶數據等。數據復雜性的提升給傳統的機器學習算法設計及其實現技術帶來了嚴峻的挑戰。在這種情況下，許多全新的基于圖形的機器學習算法或圖神經網絡（GNN）不斷在學術界和工業界涌現。

 

GNN 對計算能力和存儲有非常高的要求，而且其算法的軟件實現效率非常低。因此，業界對 GNN 的硬件加速有著非常迫切的需求。盡管傳統的卷積神經網絡（CNN）硬件加速有很多種解決方案，但 GNN 的硬件加速還沒有得到充分的討論和研究。在撰寫本白皮書時，谷歌（Google）和百度（Baidu）都無法搜索到關于 GNN 硬件加速的中文研究資料。本白皮書的寫作動機是將國外最新的 GNN 算法、對加速技術的研究以及對基于現場可編程邏輯門陣列（FPGA）的 GNN 加速技術的探討相結合，并以概述的形式呈現給讀者。

 

對圖神經網絡（GNN）的介紹

 

在宏觀層面上，GNN 的架構與傳統 CNN 有很多相似之處，諸如卷積層、池化、激活函數、機器學習處理器（MLP）、全連接層（FC layer）等模塊，這些都可以應用到 GNN。下圖展示了一個相對簡單的 GNN 架構。

但是，GNN 中的圖形數據卷積計算與傳統 CNN 中的二維卷積計算不同。以下圖為例，紅色目標節點的卷積計算過程如下所示：

1、圖卷積 - 使用近鄰函數對周圍節點的特征進行采樣，并計算平均值。相鄰節點的數量是不確定且無序的（非歐幾里得數據）

2、二維卷積——使用卷積核對周圍節點的特征進行采樣，并計算加權平均值。相鄰節點的數量是確定且有序的（歐幾里得數據）

 

圖 2：圖卷積和二維卷積（來源：https://arxiv.org/abs/1901.00596）

 

對 GraphSAGE 算法的介紹

 

學術界對 GNN 算法進行了大量的研究和探討，提出了相當多的創新實現方法。其中，由斯坦福大學（Stanford University）于 2017 年提出的 GraphSAGE 是一種歸納表示學習算法，用于預測大規模圖中動態的、全新的、未知的節點類型，還專門針對節點數量龐大、節點特征豐富的圖進行了優化。如下圖所示，

GraphSAGE 算法的計算過程可以分為三個主要步驟：

1、相鄰節點采樣——用于降低復雜性，一般采樣兩層，每層采樣幾個節點。

2、聚合——用于嵌入目標節點，即圖的低維向量表示。

3、預測——使用嵌入作為全連接層的輸入，以預測目標節點 d 的標簽。

 

圖 3：GraphSAGE 算法的可視化表示（來源：http://snap.stanford.edu/graphsage）

 

1.Sample neighborhood

1、樣本鄰域

2.Aggregate feature information from neighbors

2、聚合來自鄰域的特征信息

3.Predict graph context and label using aggregated information

3、利用聚合信息預測圖形情況和標簽

 

為了在 FPGA 中實現 GraphSAGE 算法加速，必須了解其數學模型，以便將算

法映射到不同的邏輯模塊。下圖所示的代碼說明了該算法的數學過程。

 

圖 4：GraphSAGE 算法的數學模型（來源：http://snap.stanford.edu/graphsage）

 

Step 1: Sample a sub-graph node with neighborhood function N[}.

步驟 1：使用近鄰函數 N[}對子圖節點進行采樣。

Step 2: Aggregate features from neighbor nodes, e.g. mean[}, lstm[}, polling[}

步驟 2：聚合相鄰節點的特征，例如 mean[}、lstm[}、polling[}

Step3: Combine aggregated node features. E.g. convolution[}

步驟 3：合并聚合的節點特征。例如卷積[}

Step 4: Nonlinear activation, e.g, relu[}

步驟 4：非線性激活，例如 relu[}

Step 5: Iterate for each neighbor with a sub-graph

步驟 5：使用子圖迭代每個鄰域

Step 6: Normalize

步驟 6：標準化

Step 7: Iterate for each search-depth

步驟 7：對每個深度搜索進行迭代

Step 8: Final node embedding of node v

步驟 8：節點 v 的最終節點嵌入

 

對于每個要處理的目標節點 xv，GraphSAGE 算法都會執行以下操作：

1、通過近鄰采樣函數 N(v)對子圖中的節點進行采樣。

2、聚合要采樣的相鄰節點的特征。聚合函數可以是 mean()、lstm()或 polling()

等。

3、將聚合結果與上一次迭代的輸出表示合并起來，并使用 Wk 進行卷積。

4、對卷積結果進行非線性處理。

5、多次迭代以結束當前第 k 層的所有相鄰節點的處理。

6、對第 k 層迭代的結果進行標準化處理。

7、多次迭代以結束對所有 K 層采樣深度的處理。

8、將最終的迭代結果 zv 嵌入到輸入節點 xv。

 

GNN 加速器設計所面臨的挑戰

 

GNN 算法涉及大量的矩陣計算和存儲訪問操作。在傳統的 x86 架構服務器上運行這種算法的效率是非常低的，表現為速度慢、能耗高等。

 

新型圖形處理器（GPU）的應用可以顯著提高 GNN 的計算速度與能效比。但是，GPU 在存儲可擴展性方面存在短板，使其無法處理圖形中的海量節點。GPU 的指令執行方式也會導致計算延遲過大和不確定性；因此，它不適用于需要實時計算圖形的場景。

 

上面提到的各種設計挑戰，使得業界迫切需要一種能夠支持高并發、實時計算，擁有巨大存儲容量和帶寬，并可擴展到數據中心的 GNN 加速解決方案。

 

基于 FPGA 設計方案的 GNN 加速器

 

Achronix 的 Speedster®7t 系列 FPGA 產品（以及該系列的第一款器件AC7t1500）是針對數據中心和機器學習工作負載進行了優化的高性能 FPGA器件，消除了基于中央處理器（CPU）、GPU 和傳統 FPGA 的解決方案中存在的若干性能瓶頸。Speedster7t 系列 FPGA 產品采用了臺積電（TSMC）的7nm FinFET 工藝，其架構采用了一種革命性的全新二維片上網絡（NoC）、獨創的機器學習處理器矩陣（MLP），并采用高帶寬 GDDR6 控制器、400G 以太網和 PCI Express Gen5 接口，在確保 ASIC 級性能的同時，它為用戶提供了靈活的硬件可編程性。下圖展示了高性能 FPGA 器件 Speedster7t1500 的架構。

 

圖 5：Achronix 高性能 FPGA 器件 Speedster AC7t1500 的架構

 

上述特點使 Achronix Speedster7t1500 器件成為應對在 GNN 加速器設計中面臨的各種挑戰的完美解決方案。

 

表 1：GNN 設計面臨的挑戰和 Achronix Speedster7t1500 FPGA 器件提供的

解決方案

 

 

GNN 加速器頂層架構

 

此 GNN 加速器是為 GraphSAGE 算法設計的，但是它的設計也可以應用于其他類似的 GNN 算法加速。其頂層架構如下圖所示。

 

圖 6：GNN 加速器頂層架構

 

Synthesizable IPs

可綜合的 IP

GNN Core: Preforms GNN computation

GNN 內核：執行 GNN 計算

RoCE-Lite: Memory scalability with RDMA

RoCE-Lite：采用 RDMA 的存儲可擴展性

Harden IPs

硬化 IP

NoC: High speed and unified IP connectivity

NoC：高速、統一的 IP 連接

DDR4 Ctrl: Large memory for graph storage

DDR4 Ctrl：用于圖形存儲的大存儲容量

GDDR6 Ctrl: High speed memory for computing

GDDR6 Ctrl：用于計算的高速存儲

PCIe Gen5×16: High throughout host interface

PCIe Gen5×16：高吞吐量的主機接口

Ethernet 400GE: High speed network

以太網 400GE：高速網絡

 

該架構由以下模塊組成：

 

 ●圖中的 GNN 內核是算法實現的核心部分（詳情如下）。

 ●RoCE-Lite 是 RDMA 協議的輕量級版本，用于通過高速以太網進行遠程存儲訪問，以支持海量節點的圖計算。

 ●400GE 以太網控制器用于承載 RoCE-Lite 協議。

 ●GDDR6 存儲器用于存儲 GNN 處理過程中所需的高速訪問數據（DDR4 作為備用大容量存儲器）。該存儲器用于存儲訪問頻率相對較低的數據，例如

 ●PCIe Gen5 ×16 接口提供高速主機接口，用于與服務器軟件進行數據交互。

 

上述所有模塊均通過具有高帶寬的 NoC 實現互連。

 

 

GNN 內核微架構

 

在開始討論 GNN 內核的微架構之前，有必要先回顧一下 GraphSAGE 算法。

 

其內層循環的聚合和合并（包括卷積）占據了該算法的大部分計算和存儲訪問。通過研究，我們得出這兩個步驟的特點，具體如下。

 

表 2：GNN 算法中聚合和合并操作的對比（來源：https://arxiv.org/abs/1908.10834）

 

 

可以看出，聚合操作和合并操作在計算和存儲訪問模式上有著完全不同的需求。聚合操作涉及相鄰節點的采樣。然而，圖形是一種非歐幾里得數據類型——它的大小和維度是不確定且無序，矩陣稀疏，節點位置隨機。因此，存儲訪問是不規則的，并且難以重復利用數據。

 

在合并操作中，輸入數據是聚合結果（節點的低維表示）和權重矩陣。它的大小和維度是固定的，具有線性存儲位置。因此對存儲訪問沒有挑戰，但是矩陣的計算量非常大。

 

基于上述分析，我們決定在 GNN 內核加速器設計中選擇使用兩種不同的硬件結構來分別處理聚合和合并操作（如下圖示）：

 

聚合器——通過單指令多數據（SIMD）處理器陣列，對圖形相鄰節點進行采樣和聚合。單指令可以預定義為 mean()平均值計算，或其他適用的聚合函數；多數據是指單次 mean()均值計算中需要多個相鄰節點的特征數據作為輸入，這些數據來自子圖采樣器。SIMD 處理器陣列通過調度器 AggScheduler 進行負載平衡。子圖采樣器通過 NoC 從 GDDR6 或 DDR4 讀回的鄰接矩陣和節點特征數據 h0v 分別緩存在鄰接列表緩沖區（Adjacent ListBuffer）和節點特征緩沖區（Node Feature Buffer）。聚合的結果 hkN(v)存儲在聚合緩沖區（Aggregation Buffer）中。

 

合并器——通過脈動矩陣 PE 對聚合結果進行卷積運算。卷積核是 Wk 權重矩陣。卷積結果由 ReLU 激活函數進行非線性處理，同時也存儲在 PartialSum Buffer 中，以用于下一輪迭代。

 

圖 7：GNN 內核功能框圖

 

合并結果經過 L2BN 標準化處理后，即為最終的節點表示 hkv。在一個典型的節點分類預測應用中，節點表示 hkv 可以通過一個全連接層（FC）來獲取節點的分類標簽。這個過程是傳統的機器學習處理方法之一，在 GraphSAGE 文獻資料中沒有體現，這個功能也沒有包含在這個架構中。

 

結論

本白皮書探討了 GraphSAGE GNN 算法的數學原理，并從多個角度分析了GNN 加速器設計中的技術挑戰。通過分析問題并在架構層面逐一解決，提出了一種架構，利用 Achronix Speedster7t AC7t1500 FPGA 器件提供的具有競爭性的優勢，創建了一種高度可擴展的、能夠提供卓越性能的 GNN 加速解決方案。