313
得益于大數(shù)據(jù)的興起和計算能力的快速提升，機器學習技術(shù)近年來經(jīng)歷了革命性的發(fā)展。諸如圖像分類、語音識別和自然語言處理等機器學習任務，都是對具有一定大小、維度和有序排列的歐幾里得數(shù)據(jù)進行處理。然而，在許多現(xiàn)實場景中，數(shù)據(jù)是由復雜的非歐幾里得數(shù)據(jù)（例如圖形）表示的。這些圖形不僅包含數(shù)據(jù)，還包含數(shù)據(jù)之間的依賴關系，例如社交網(wǎng)絡、蛋白質(zhì)分子結(jié)構(gòu)、電子商務平臺中的客戶數(shù)據(jù)等。數(shù)據(jù)復雜性的提升給傳統(tǒng)的機器學習算法設計及其實現(xiàn)技術(shù)帶來了嚴峻的挑戰(zhàn)。在這種情況下，許多全新的基于圖形的機器學習算法或圖神經(jīng)網(wǎng)絡（GNN）不斷在學術(shù)界和工業(yè)界涌現(xiàn)。
GNN對計算能力和存儲有非常高的要求，而且其算法的軟件實現(xiàn)效率非常低。因此，業(yè)界對GNN的硬件加速有著非常迫切的需求。盡管傳統(tǒng)的卷積神經(jīng)網(wǎng)絡（CNN）硬件加速有很多種解決方案，但GNN的硬件加速還沒有得到充分的討論和研究。在撰寫本白皮書時，谷歌（Google）和百度（Baidu）都無法搜索到關于GNN硬件加速的中文研究資料。本白皮書的寫作動機是將國外最新的GNN算法、對加速技術(shù)的研究以及對基于現(xiàn)場可編程邏輯門陣列（FPGA）的GNN加速技術(shù)的探討相結(jié)合，并以概述的形式呈現(xiàn)給讀者。
對圖神經(jīng)網(wǎng)絡（GNN）的介紹
在宏觀層面上，GNN的架構(gòu)與傳統(tǒng)CNN有很多相似之處，諸如卷積層、池化、激活函數(shù)、機器學習處理器（MLP）、全連接層（FC layer）等模塊，這些都可以應用到GNN。下圖展示了一個相對簡單的GNN架構(gòu)。
圖1：典型的GNN架構(gòu)（來源：https://arxiv.org/abs/1901.00596）
但是，GNN中的圖形數(shù)據(jù)卷積計算與傳統(tǒng)CNN中的二維卷積計算不同。以下圖為例，紅色目標節(jié)點的卷積計算過程如下所示：
1、圖卷積 - 使用近鄰函數(shù)對周圍節(jié)點的特征進行采樣，并計算平均值。相鄰節(jié)點的數(shù)量是不確定且無序的（非歐幾里得數(shù)據(jù)）
2、二維卷積——使用卷積核對周圍節(jié)點的特征進行采樣，并計算加權(quán)平均值。相鄰節(jié)點的數(shù)量是確定且有序的（歐幾里得數(shù)據(jù)）
圖2：圖卷積和二維卷積（來源：https://arxiv.org/abs/1901.00596）
對GraphSAGE算法的介紹
學術(shù)界對GNN算法進行了大量的研究和探討，提出了相當多的創(chuàng)新實現(xiàn)方法。其中，由斯坦福大學（Stanford University）于2017年提出的GraphSAGE是一種歸納表示學習算法，用于預測大規(guī)模圖中動態(tài)的、全新的、未知的節(jié)點類型，還專門針對節(jié)點數(shù)量龐大、節(jié)點特征豐富的圖進行了優(yōu)化。如下圖所示，GraphSAGE算法的計算過程可以分為三個主要步驟：
1、相鄰節(jié)點采樣——用于降低復雜性，一般采樣兩層，每層采樣幾個節(jié)點。
2、聚合——用于嵌入目標節(jié)點，即圖的低維向量表示。
3、預測——使用嵌入作為全連接層的輸入，以預測目標節(jié)點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中實現(xiàn)GraphSAGE算法加速，必須了解其數(shù)學模型，以便將算法映射到不同的邏輯模塊。下圖所示的代碼說明了該算法的數(shù)學過程。
圖4：GraphSAGE算法的數(shù)學模型（來源：http://snap.stanford.edu/graphsage）
Step 1: Sample a sub-graph node with neighborhood function N[}.
步驟1：使用近鄰函數(shù)N[}對子圖節(jié)點進行采樣。
Step 2: Aggregate features from neighbor nodes, e.g. mean[}, lstm[}, polling[}
步驟2：聚合相鄰節(jié)點的特征，例如mean[}、lstm[}、polling[}
Step3: Combine aggregated node features. E.g. convolution[}
步驟3：合并聚合的節(jié)點特征。例如卷積[}
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：節(jié)點v的最終節(jié)點嵌入
對于每個要處理的目標節(jié)點xv，GraphSAGE算法都會執(zhí)行以下操作：
1、通過近鄰采樣函數(shù)N(v)對子圖中的節(jié)點進行采樣。
2、聚合要采樣的相鄰節(jié)點的特征。聚合函數(shù)可以是mean()、lstm()或polling()等。
3、將聚合結(jié)果與上一次迭代的輸出表示合并起來，并使用Wk進行卷積。
4、對卷積結(jié)果進行非線性處理。
5、多次迭代以結(jié)束當前第k層的所有相鄰節(jié)點的處理。
6、對第k層迭代的結(jié)果進行標準化處理。
7、多次迭代以結(jié)束對所有K層采樣深度的處理。
8、將最終的迭代結(jié)果zv嵌入到輸入節(jié)點xv。
GNN加速器設計所面臨的挑戰(zhàn)
GNN算法涉及大量的矩陣計算和存儲訪問操作。在傳統(tǒng)的x86架構(gòu)服務器上運行這種算法的效率是非常低的，表現(xiàn)為速度慢、能耗高等。
新型圖形處理器（GPU）的應用可以顯著提高GNN的計算速度與能效比。但是，GPU在存儲可擴展性方面存在短板，使其無法處理圖形中的海量節(jié)點。GPU的指令執(zhí)行方式也會導致計算延遲過大和不確定性；因此，它不適用于需要實時計算圖形的場景。
上面提到的各種設計挑戰(zhàn)，使得業(yè)界迫切需要一種能夠支持高并發(fā)、實時計算，擁有巨大存儲容量和帶寬，并可擴展到數(shù)據(jù)中心的GNN加速解決方案。
基于FPGA設計方案的GNN加速器
Achronix的Speedster?7t系列FPGA產(chǎn)品（以及該系列的第一款器件AC7t1500）是針對數(shù)據(jù)中心和機器學習工作負載進行了優(yōu)化的高性能FPGA器件，消除了基于中央處理器（CPU）、GPU和傳統(tǒng)FPGA的解決方案中存在的若干性能瓶頸。Speedster7t系列FPGA產(chǎn)品采用了臺積電（TSMC）的7nm FinFET工藝，其架構(gòu)采用了一種革命性的全新二維片上網(wǎng)絡（NoC）、獨創(chuàng)的機器學習處理器矩陣（MLP），并采用高帶寬GDDR6控制器、400G以太網(wǎng)和PCI Express Gen5接口，在確保ASIC級性能的同時，它為用戶提供了靈活的硬件可編程性。下圖展示了高性能FPGA器件Speedster7t1500的架構(gòu)。
圖5：Achronix高性能FPGA器件Speedster AC7t1500的架構(gòu)
上述特點使Achronix Speedster7t1500器件成為應對在GNN加速器設計中面臨的各種挑戰(zhàn)的完美解決方案。
表1：GNN設計面臨的挑戰(zhàn)和Achronix Speedster7t1500 FPGA器件提供的解決方案
?
GNN加速器頂層架構(gòu)
此GNN加速器是為GraphSAGE算法設計的，但是它的設計也可以應用于其他類似的GNN算法加速。其頂層架構(gòu)如下圖所示。
圖6：GNN加速器頂層架構(gòu)
Synthesizable IPs
可綜合的IP
GNN Core: Preforms GNN computation
GNN內(nèi)核：執(zhí)行GNN計算
RoCE-Lite: Memory scalability with RDMA
RoCE-Lite：采用RDMA的存儲可擴展性
Harden IPs
硬化IP
NoC: High speed and unified IP connectivity
NoC：高速、統(tǒng)一的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
以太網(wǎng)400GE：高速網(wǎng)絡
該架構(gòu)由以下模塊組成：
- 圖中的GNN內(nèi)核是算法實現(xiàn)的核心部分（詳情如下）。
- RoCE-Lite是RDMA協(xié)議的輕量級版本，用于通過高速以太網(wǎng)進行遠程存儲訪問，以支持海量節(jié)點的圖計算。
- 400GE以太網(wǎng)控制器用于承載RoCE-Lite協(xié)議。
- GDDR6存儲器用于存儲GNN處理過程中所需的高速訪問數(shù)據(jù)（DDR4作為備用大容量存儲器）。該存儲器用于存儲訪問頻率相對較低的數(shù)據(jù)，例如待預處理的圖形數(shù)據(jù)。
- PCIe Gen5 ×16 接口提供高速主機接口，用于與服務器軟件進行數(shù)據(jù)交互。
上述所有模塊均通過具有高帶寬的NoC實現(xiàn)互連。
GNN內(nèi)核微架構(gòu)
在開始討論GNN內(nèi)核的微架構(gòu)之前，有必要先回顧一下GraphSAGE算法。其內(nèi)層循環(huán)的聚合和合并（包括卷積）占據(jù)了該算法的大部分計算和存儲訪問。通過研究，我們得出這兩個步驟的特點，具體如下。
表2：GNN算法中聚合和合并操作的對比（來源：https://arxiv.org/abs/1908.10834）
可以看出，聚合操作和合并操作在計算和存儲訪問模式上有著完全不同的需求。聚合操作涉及相鄰節(jié)點的采樣。然而，圖形是一種非歐幾里得數(shù)據(jù)類型——它的大小和維度是不確定且無序，矩陣稀疏，節(jié)點位置隨機。因此，存儲訪問是不規(guī)則的，并且難以重復利用數(shù)據(jù)。
在合并操作中，輸入數(shù)據(jù)是聚合結(jié)果（節(jié)點的低維表示）和權(quán)重矩陣。它的大小和維度是固定的，具有線性存儲位置。因此對存儲訪問沒有挑戰(zhàn)，但是矩陣的計算量非常大。
基于上述分析，我們決定在GNN內(nèi)核加速器設計中選擇使用兩種不同的硬件結(jié)構(gòu)來分別處理聚合和合并操作（如下圖示）：
- 聚合器——通過單指令多數(shù)據(jù)（SIMD）處理器陣列，對圖形相鄰節(jié)點進行采樣和聚合。單指令可以預定義為mean()平均值計算，或其他適用的聚合函數(shù)；多數(shù)據(jù)是指單次mean()均值計算中需要多個相鄰節(jié)點的特征數(shù)據(jù)作為輸入，這些數(shù)據(jù)來自子圖采樣器。SIMD處理器陣列通過調(diào)度器Agg Scheduler進行負載平衡。子圖采樣器通過NoC從GDDR6或DDR4讀回的鄰接矩陣和節(jié)點特征數(shù)據(jù)h0v分別緩存在鄰接列表緩沖區(qū)（Adjacent List Buffer）和節(jié)點特征緩沖區(qū)（Node Feature Buffer）。聚合的結(jié)果hkN(v)存儲在聚合緩沖區(qū)（Aggregation Buffer）中。
- 合并器——通過脈動矩陣PE對聚合結(jié)果進行卷積運算。卷積核是Wk權(quán)重矩陣。卷積結(jié)果由ReLU激活函數(shù)進行非線性處理，同時也存儲在Partial Sum Buffer中，以用于下一輪迭代。
圖7：GNN內(nèi)核功能框圖
合并結(jié)果經(jīng)過L2BN標準化處理后，即為最終的節(jié)點表示hkv。在一個典型的節(jié)點分類預測應用中，節(jié)點表示hkv可以通過一個全連接層（FC）來獲取節(jié)點的分類標簽。這個過程是傳統(tǒng)的機器學習處理方法之一，在GraphSAGE文獻資料中沒有體現(xiàn)，這個功能也沒有包含在這個架構(gòu)中。
結(jié)論
本白皮書探討了GraphSAGE GNN算法的數(shù)學原理，并從多個角度分析了GNN加速器設計中的技術(shù)挑戰(zhàn)。通過分析問題并在架構(gòu)層面逐一解決，提出了一種架構(gòu)，利用Achronix Speedster7t AC7t1500 FPGA器件提供的具有競爭性的優(yōu)勢，創(chuàng)建了一種高度可擴展的、能夠提供卓越性能的GNN加速解決方案。
?
版權(quán)所有?2021 Achronix半導體公司保留所有權(quán)利。Achronix、Speedcore、Speedster和ACE是Achronix半導體公司在美國和/或其他國家/地區(qū)的商標。所有其他商標均為其各自所有者的財產(chǎn)。所有規(guī)格如有更改，恕不另行通知。
