但是， GNN中的Graph數據卷積計算與傳統CNN中的2D卷積計算是不同的。以圖2為例，針對紅色目標節點的卷積計算，其過程如下：

 

l  Graph卷積：以鄰居函數采樣周邊節點特征並計算均值，其鄰居節點數量不確定且無序（非歐氏數據）。

 

l  2D卷積：以卷積核采樣周邊節點特征並計算加權平均值，其鄰居節點數量確定且有序（歐氏數據）。

 

 

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

 

3. GraphSAGE算法簡介

 

學術界已對GNN算法進行了非常多的研究討論
，並提出了數目可觀的創新實現方式。其中，斯坦福大學在2017年提出的GraphSAGE是一種用於預測大型圖中動態新增未知節點類型的歸納式表征學習算法，特別針對節點數量巨大、且節點特征豐富的圖做了優化。如下圖所示
，GraphSAGE計算過程可分為三個主要步驟：

 

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

 

l  鄰節點采樣：用於降低複雜度，一般采樣2層
，每一層采樣若幹節點

 

l  聚合：用於生成目標節點的embedding
，即graph的低維向量表征

 

l  預測：將embedding作為全連接層的輸入，預測目標節點d的標簽

 

為了在FPGA中實現GraphSAGE算法加速，我們需要知悉其數學模型，以便將算法映射到不同的邏輯模塊中。下圖所示的代碼闡述了本算法的數學過程。

 

 

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

 

對於每一個待處理的目標節點xv
，GraphSAGE執行下列操作：

1）通過鄰居采樣函數N（v）
，采樣子圖(subgraph)中的節點

2）聚合被采樣的鄰節點特征，聚合函數可以為mean()
、lstm()或者polling()等

3）將聚合結果與上一次迭代的輸出表征合並，並以Wk做卷積

4）卷積結果做非線性處理

5）迭代若幹次以結束當前第k層所有鄰節點的處理

6）將第k層迭代結果做歸一化處理

7）迭代若幹次以結束所有K層采樣深度的處理

8）最終迭代結果zv即為輸入節點xv的嵌入（embedding）

 

4.GNN加速器設計挑戰

 

GNN的算法中涉及到大量的矩陣計算和內存訪問操作
，在傳統的x86架構的服務器上運行此算法是非常低效的

，表現在速度慢

，能耗高等方麵。

 

新型GPU的應用
，可以為GNN的運算速度和能效比帶來顯著收益。然而GPU內存擴展性的短板，使其無法勝任海量節點Graph的處理
；GPU的指令執行方式，也造成了計算延遲過大並且不可確定，無法勝任需要實時計算Graph的場景。

 

如上所述種種設計挑戰的存在
，使得業界急需一種可以支持高度並發實時計算、巨大內存容量和帶寬、以及在數據中心範圍可擴展的GNN加速解決方案。

 

5.GNN加速器的FPGA設計方案

 

Achronix公司推出的Speedster7t係列高性能FPGA，專門針對數據中心和機器學習工作負載進行了優化，消除了CPU、GPU以及傳統 FPGA 存在的若幹性能瓶頸。Speedster7t FPGA 基於台積電的 7nm FinFET工藝，其架構采用革命性的新型 2D 片上網絡（NoC）

，獨創的機器學習處理器矩陣（MLP），並利用高帶寬 GDDR6 控製器、400G 以太網和 PCI Express Gen5 接口，在保障ASIC 級別性能的同時，為用戶提供了靈活的硬件可編程能力。下圖展示了Speedster7t1500高性能FPGA的架構。

 

圖5: AchronixSpeedster7t1500高性能FPGA架構（來源：http://www.achronix.com）

 

如上所述種種特性
，使得AchronixSpeedster7t1500 FPGA器件為GNN加速器設計中所麵臨的各種挑戰，提供了完美的解決方案。

 

表1：GNN設計挑戰與Achronix的Speedster7t1500 FPGA解決方案

 

5.1GNN加速器頂層架構

 

本GNN加速器針對GraphSAGE進行設計，但其架構具有一定的通用性，可以適用於其他類似的GNN算法加速，其頂層架構如下圖所示。

 

圖6: GNN加速器頂層架構（來源：Achronix原創）

 

圖中GNNCore為算法實現的核心部分，其設計細節將在下文展開談論
；RoCE-Lite為RDMA協議的輕量級版本，用於通過高速以太網進行遠程內存訪問，以支持海量節點的Graph計算，其設計細節將在本公眾號的後續文章中討論；400GE以太網控製器用來承載RoCE-Lite協議
；GDDR6用於存放GNN處理過程中所需的高速訪問數據；DDR4作為備用高容量內存，可以用於存儲相對訪問頻度較低的數據，比如待預處理的Graph；PCIeGen5x16提供高速主機接口，用於與服務器軟件交互數據；上述所有模塊，皆通過NoC片上網絡來實現高速互聯。

 

5.2GNNCore微架構

 

在開始討論GNNCore微架構之前，我們先回顧一下本文第3節中的GraphSAGE算法，其內層循環的聚合以及合並（包含卷積）等兩個操作占據了算法的絕大部分計算和存儲器訪問。通過研究
，我們得到這兩個步驟的特征如下：

 

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

 

可以看出，聚合操作與合並操作，其對計算和存儲器訪問的需求完全不同。聚合操作中涉及到對鄰節點的采樣，然而Graph屬於非歐氏數據類型，其大小維度不確定且無序，矩陣稀疏
，節點位置隨機，所以存儲器訪問不規則並難以複用數據；在合並操作中，其輸入數據為聚合結果（節點的低維表征）以及權重矩陣，其大小維度固定，存儲位置規則線性，對存儲器訪問不存在挑戰，但是矩陣的計算量非常大。

 

基於以上分析，我們決定在GNNCore加速器設計中用兩種不同的硬件結構來處理聚合操作與合並操作，功能框圖如下圖所示：

 

圖7: GNNCore功能框圖（來源：Achronix原創）

 

聚合器（Aggregator）：通過SIMD（單指令多數據處理器）陣列來對Graph進行鄰居節點采樣並進行聚合操作。其中的“單指令”可以預定義為mean()均值計算
，或者其他適用的聚合函數；“多數據”則表示單次mean()均值計算中需要多個鄰居節點的特征數據作為輸入
，而這些數據來自於子圖采樣器（SubgraphSampler）

；SIMD陣列通過調度器Agg Scheduler做負載均衡；子圖采樣器通過NoC從GDDR6或DDR4讀回的鄰接矩陣和節點特征數據h0v
，分別緩存在AdjacentListBuffer和NodeFeature Buffer之中；聚合的結果hkN(v)存儲在AggBuffer之中。

 

合並器（Combinator）：通過脈動矩陣PE來執行聚合結果的卷積操作
；卷積核為Wk權重矩陣
；卷積結果通過ReLU激活函數做非線性處理，同時也存儲在PartialSumBuffer中以方便下一輪迭代。

 

合並的結果通過L2BN歸一化處理之後，即為最終的節點表征hkv。

 

在比較典型的節點分類預測應用中，該節點表征hkv可以通過一個全連接層（FC），以得到該節點的分類標簽。此過程屬於傳統的機器學習處理方法之一，沒有在GraphSAGE論文中體現，此設計中也沒有包含這個功能。

 

6.結論

 

本文深入討論了GraphSAGEGNN算法的數學原理，並從多個維度分析了GNN加速器設計中的技術挑戰。作者通過分解問題並在架構層麵逐一解決的方法
，綜合運用AchronixSpeedster7t1500FPGA所提供的競爭優勢
，創造了一個性能極佳且高度可擴展的GNN加速解決方案。