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

　　GNN對(duì)計(jì)算能力和存儲(chǔ)有非常高的要求，而且其算法的軟件實(shí)現(xiàn)效率非常低。因此，業(yè)界對(duì)GNN的硬件加速有著非常迫切的需求。盡管傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)（CNN）硬件加速有很多種解決方案，但GNN的硬件加速還沒(méi)有得到充分的討論和研究。在撰寫(xiě)本白皮書(shū)時(shí)，谷歌（Google）和百度（Baidu）都無(wú)法搜索到關(guān)于GNN硬件加速的中文研究資料。本白皮書(shū)的寫(xiě)作動(dòng)機(jī)是將國(guó)外最新的GNN算法、對(duì)加速技術(shù)的研究以及對(duì)基于現(xiàn)場(chǎng)可編程邏輯門(mén)陣列（FPGA）的GNN加速技術(shù)的探討相結(jié)合，并以概述的形式呈現(xiàn)給讀者。

　　對(duì)圖神經(jīng)網(wǎng)絡(luò)（GNN）的介紹

　　在宏觀層面上，GNN的架構(gòu)與傳統(tǒng)CNN有很多相似之處，諸如卷積層、池化、激活函數(shù)、機(jī)器學(xué)習(xí)處理器（MLP）、全連接層（FC layer）等模塊，這些都可以應(yīng)用到GNN。下圖展示了一個(gè)相對(duì)簡(jiǎn)單的GNN架構(gòu)。

　　圖1：典型的GNN架構(gòu)（來(lái)源：https://arxiv.org/abs/1901.00596）

　　但是，GNN中的圖形數(shù)據(jù)卷積計(jì)算與傳統(tǒng)CNN中的二維卷積計(jì)算不同。以下圖為例，紅色目標(biāo)節(jié)點(diǎn)的卷積計(jì)算過(guò)程如下所示：

　　1、圖卷積 - 使用近鄰函數(shù)對(duì)周?chē)?jié)點(diǎn)的特征進(jìn)行采樣，并計(jì)算平均值。相鄰節(jié)點(diǎn)的數(shù)量是不確定且無(wú)序的（非歐幾里得數(shù)據(jù)）

　　2、二維卷積——使用卷積核對(duì)周?chē)?jié)點(diǎn)的特征進(jìn)行采樣，并計(jì)算加權(quán)平均值。相鄰節(jié)點(diǎn)的數(shù)量是確定且有序的（歐幾里得數(shù)據(jù)）

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

　　對(duì)GraphSAGE算法的介紹

　　學(xué)術(shù)界對(duì)GNN算法進(jìn)行了大量的研究和探討，提出了相當(dāng)多的創(chuàng)新實(shí)現(xiàn)方法。其中，由斯坦福大學(xué)（Stanford University）于2017年提出的GraphSAGE是一種歸納表示學(xué)習(xí)算法，用于預(yù)測(cè)大規(guī)模圖中動(dòng)態(tài)的、全新的、未知的節(jié)點(diǎn)類(lèi)型，還專(zhuān)門(mén)針對(duì)節(jié)點(diǎn)數(shù)量龐大、節(jié)點(diǎn)特征豐富的圖進(jìn)行了優(yōu)化。如下圖所示，GraphSAGE算法的計(jì)算過(guò)程可以分為三個(gè)主要步驟：

　　1、相鄰節(jié)點(diǎn)采樣——用于降低復(fù)雜性，一般采樣兩層，每層采樣幾個(gè)節(jié)點(diǎn)。

　　2、聚合——用于嵌入目標(biāo)節(jié)點(diǎn)，即圖的低維向量表示。

　　3、預(yù)測(cè)——使用嵌入作為全連接層的輸入，以預(yù)測(cè)目標(biāo)節(jié)點(diǎn)d的標(biāo)簽。

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

　　1.Sample neighborhood

　　1、樣本鄰域

　　2.Aggregate feature information from neighbors

　　2、聚合來(lái)自鄰域的特征信息

　　3.Predict graph context and label using aggregated information

　　3、利用聚合信息預(yù)測(cè)圖形情況和標(biāo)簽

　　為了在FPGA中實(shí)現(xiàn)GraphSAGE算法加速，必須了解其數(shù)學(xué)模型，以便將算法映射到不同的邏輯模塊。下圖所示的代碼說(shuō)明了該算法的數(shù)學(xué)過(guò)程。

　　圖4：GraphSAGE算法的數(shù)學(xué)模型（來(lái)源：http://snap.stanford.edu/graphsage）

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

　　步驟1：使用近鄰函數(shù)N[}對(duì)子圖節(jié)點(diǎn)進(jìn)行采樣。

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

　　步驟2：聚合相鄰節(jié)點(diǎn)的特征，例如mean[}、lstm[}、polling[}

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

　　步驟3：合并聚合的節(jié)點(diǎn)特征。例如卷積[}

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

　　步驟4：非線(xiàn)性激活，例如relu[}

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

　　步驟5：使用子圖迭代每個(gè)鄰域

　　Step 6: Normalize

　　步驟6：標(biāo)準(zhǔn)化

　　Step 7: Iterate for each search-depth

　　步驟7：對(duì)每個(gè)深度搜索進(jìn)行迭代

　　Step 8: Final node embedding of node v

　　步驟8：節(jié)點(diǎn)v的最終節(jié)點(diǎn)嵌入

　　對(duì)于每個(gè)要處理的目標(biāo)節(jié)點(diǎn)xv，GraphSAGE算法都會(huì)執(zhí)行以下操作：

　　1、通過(guò)近鄰采樣函數(shù)N（v）對(duì)子圖中的節(jié)點(diǎn)進(jìn)行采樣。

　　2、聚合要采樣的相鄰節(jié)點(diǎn)的特征。聚合函數(shù)可以是mean（）、lstm（）或polling（）等。

　　3、將聚合結(jié)果與上一次迭代的輸出表示合并起來(lái)，并使用Wk進(jìn)行卷積。

　　4、對(duì)卷積結(jié)果進(jìn)行非線(xiàn)性處理。

　　5、多次迭代以結(jié)束當(dāng)前第k層的所有相鄰節(jié)點(diǎn)的處理。

　　6、對(duì)第k層迭代的結(jié)果進(jìn)行標(biāo)準(zhǔn)化處理。

　　7、多次迭代以結(jié)束對(duì)所有K層采樣深度的處理。

　　8、將最終的迭代結(jié)果zv嵌入到輸入節(jié)點(diǎn)xv。

　　GNN加速器設(shè)計(jì)所面臨的挑戰(zhàn)

　　GNN算法涉及大量的矩陣計(jì)算和存儲(chǔ)訪(fǎng)問(wèn)操作。在傳統(tǒng)的x86架構(gòu)服務(wù)器上運(yùn)行這種算法的效率是非常低的，表現(xiàn)為速度慢、能耗高等。

　　新型圖形處理器（GPU）的應(yīng)用可以顯著提高GNN的計(jì)算速度與能效比。但是，GPU在存儲(chǔ)可擴(kuò)展性方面存在短板，使其無(wú)法處理圖形中的海量節(jié)點(diǎn)。GPU的指令執(zhí)行方式也會(huì)導(dǎo)致計(jì)算延遲過(guò)大和不確定性；因此，它不適用于需要實(shí)時(shí)計(jì)算圖形的場(chǎng)景。

　　上面提到的各種設(shè)計(jì)挑戰(zhàn)，使得業(yè)界迫切需要一種能夠支持高并發(fā)、實(shí)時(shí)計(jì)算，擁有巨大存儲(chǔ)容量和帶寬，并可擴(kuò)展到數(shù)據(jù)中心的GNN加速解決方案。

　　基于FPGA設(shè)計(jì)方案的GNN加速器

　　Achronix的Speedster?7t系列FPGA產(chǎn)品（以及該系列的第一款器件AC7t1500）是針對(duì)數(shù)據(jù)中心和機(jī)器學(xué)習(xí)工作負(fù)載進(jìn)行了優(yōu)化的高性能FPGA器件，消除了基于中央處理器（CPU）、GPU和傳統(tǒng)FPGA的解決方案中存在的若干性能瓶頸。Speedster7t系列FPGA產(chǎn)品采用了臺(tái)積電（TSMC）的7nm FinFET工藝，其架構(gòu)采用了一種革命性的全新二維片上網(wǎng)絡(luò)（NoC）、獨(dú)創(chuàng)的機(jī)器學(xué)習(xí)處理器矩陣（MLP），并采用高帶寬GDDR6控制器、400G以太網(wǎng)和PCI Express Gen5接口，在確保ASIC級(jí)性能的同時(shí)，它為用戶(hù)提供了靈活的硬件可編程性。下圖展示了高性能FPGA器件Speedster7t1500的架構(gòu)。

　　圖5：Achronix高性能FPGA器件Speedster AC7t1500的架構(gòu)

　　上述特點(diǎn)使Achronix Speedster7t1500器件成為應(yīng)對(duì)在GNN加速器設(shè)計(jì)中面臨的各種挑戰(zhàn)的完美解決方案。

　　表1：GNN設(shè)計(jì)面臨的挑戰(zhàn)和Achronix Speedster7t1500 FPGA器件提供的解決方案

　　GNN加速器頂層架構(gòu)

　　此GNN加速器是為GraphSAGE算法設(shè)計(jì)的，但是它的設(shè)計(jì)也可以應(yīng)用于其他類(lèi)似的GNN算法加速。其頂層架構(gòu)如下圖所示。

　　圖6：GNN加速器頂層架構(gòu)

　　Synthesizable IPs

　　可綜合的IP

　　GNN Core: Preforms GNN computation

　　GNN內(nèi)核：執(zhí)行GNN計(jì)算

　　RoCE-Lite: Memory scalability with RDMA

　　RoCE-Lite：采用RDMA的存儲(chǔ)可擴(kuò)展性

　　Harden IPs

　　硬化IP

　　NoC: High speed and unified IP connectivity

　　NoC：高速、統(tǒng)一的IP連接

　　DDR4 Ctrl: Large memory for graph storage

　　DDR4 Ctrl：用于圖形存儲(chǔ)的大存儲(chǔ)容量

　　GDDR6 Ctrl: High speed memory for computing

　　GDDR6 Ctrl：用于計(jì)算的高速存儲(chǔ)

　　PCIe Gen5×16: High throughout host interface

　　PCIe Gen5×16：高吞吐量的主機(jī)接口

　　Ethernet 400GE: High speed network

　　以太網(wǎng)400GE：高速網(wǎng)絡(luò)

　　該架構(gòu)由以下模塊組成：

　　·圖中的GNN內(nèi)核是算法實(shí)現(xiàn)的核心部分（詳情如下）。

　　·RoCE-Lite是RDMA協(xié)議的輕量級(jí)版本，用于通過(guò)高速以太網(wǎng)進(jìn)行遠(yuǎn)程存儲(chǔ)訪(fǎng)問(wèn)，以支持海量節(jié)點(diǎn)的圖計(jì)算。

　　·400GE以太網(wǎng)控制器用于承載RoCE-Lite協(xié)議。

　　·GDDR6存儲(chǔ)器用于存儲(chǔ)GNN處理過(guò)程中所需的高速訪(fǎng)問(wèn)數(shù)據(jù)（DDR4作為備用大容量存儲(chǔ)器）。該存儲(chǔ)器用于存儲(chǔ)訪(fǎng)問(wèn)頻率相對(duì)較低的數(shù)據(jù)，例如待預(yù)處理的圖形數(shù)據(jù)。

　　·PCIe Gen5 ×16 接口提供高速主機(jī)接口，用于與服務(wù)器軟件進(jìn)行數(shù)據(jù)交互。

　　上述所有模塊均通過(guò)具有高帶寬的NoC實(shí)現(xiàn)互連。

　　GNN內(nèi)核微架構(gòu)

　　在開(kāi)始討論GNN內(nèi)核的微架構(gòu)之前，有必要先回顧一下GraphSAGE算法。其內(nèi)層循環(huán)的聚合和合并（包括卷積）占據(jù)了該算法的大部分計(jì)算和存儲(chǔ)訪(fǎng)問(wèn)。通過(guò)研究，我們得出這兩個(gè)步驟的特點(diǎn)，具體如下。

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

　　可以看出，聚合操作和合并操作在計(jì)算和存儲(chǔ)訪(fǎng)問(wèn)模式上有著完全不同的需求。聚合操作涉及相鄰節(jié)點(diǎn)的采樣。然而，圖形是一種非歐幾里得數(shù)據(jù)類(lèi)型——它的大小和維度是不確定且無(wú)序，矩陣稀疏，節(jié)點(diǎn)位置隨機(jī)。因此，存儲(chǔ)訪(fǎng)問(wèn)是不規(guī)則的，并且難以重復(fù)利用數(shù)據(jù)。

　　在合并操作中，輸入數(shù)據(jù)是聚合結(jié)果（節(jié)點(diǎn)的低維表示）和權(quán)重矩陣。它的大小和維度是固定的，具有線(xiàn)性存儲(chǔ)位置。因此對(duì)存儲(chǔ)訪(fǎng)問(wèn)沒(méi)有挑戰(zhàn)，但是矩陣的計(jì)算量非常大。

　　基于上述分析，我們決定在GNN內(nèi)核加速器設(shè)計(jì)中選擇使用兩種不同的硬件結(jié)構(gòu)來(lái)分別處理聚合和合并操作（如下圖示）：

　　·聚合器——通過(guò)單指令多數(shù)據(jù)（SIMD）處理器陣列，對(duì)圖形相鄰節(jié)點(diǎn)進(jìn)行采樣和聚合。單指令可以預(yù)定義為mean（）平均值計(jì)算，或其他適用的聚合函數(shù)；多數(shù)據(jù)是指單次mean（）均值計(jì)算中需要多個(gè)相鄰節(jié)點(diǎn)的特征數(shù)據(jù)作為輸入，這些數(shù)據(jù)來(lái)自子圖采樣器。SIMD處理器陣列通過(guò)調(diào)度器Agg Scheduler進(jìn)行負(fù)載平衡。子圖采樣器通過(guò)NoC從GDDR6或DDR4讀回的鄰接矩陣和節(jié)點(diǎn)特征數(shù)據(jù)h0v分別緩存在鄰接列表緩沖區(qū)（Adjacent List Buffer）和節(jié)點(diǎn)特征緩沖區(qū)（Node Feature Buffer）。聚合的結(jié)果hkN（v）存儲(chǔ)在聚合緩沖區(qū)（Aggregation Buffer）中。

　　 ·合并器——通過(guò)脈動(dòng)矩陣PE對(duì)聚合結(jié)果進(jìn)行卷積運(yùn)算。卷積核是Wk權(quán)重矩陣。卷積結(jié)果由ReLU激活函數(shù)進(jìn)行非線(xiàn)性處理，同時(shí)也存儲(chǔ)在Partial Sum Buffer中，以用于下一輪迭代。

　　圖7：GNN內(nèi)核功能框圖

　　合并結(jié)果經(jīng)過(guò)L2BN標(biāo)準(zhǔn)化處理后，即為最終的節(jié)點(diǎn)表示hkv。在一個(gè)典型的節(jié)點(diǎn)分類(lèi)預(yù)測(cè)應(yīng)用中，節(jié)點(diǎn)表示hkv可以通過(guò)一個(gè)全連接層（FC）來(lái)獲取節(jié)點(diǎn)的分類(lèi)標(biāo)簽。這個(gè)過(guò)程是傳統(tǒng)的機(jī)器學(xué)習(xí)處理方法之一，在GraphSAGE文獻(xiàn)資料中沒(méi)有體現(xiàn)，這個(gè)功能也沒(méi)有包含在這個(gè)架構(gòu)中。

　　結(jié)論

　　本白皮書(shū)探討了GraphSAGE GNN算法的數(shù)學(xué)原理，并從多個(gè)角度分析了GNN加速器設(shè)計(jì)中的技術(shù)挑戰(zhàn)。通過(guò)分析問(wèn)題并在架構(gòu)層面逐一解決，提出了一種架構(gòu)，利用Achronix Speedster7t AC7t1500 FPGA器件提供的具有競(jìng)爭(zhēng)性的優(yōu)勢(shì)，創(chuàng)建了一種高度可擴(kuò)展的、能夠提供卓越性能的GNN加速解決方案。