（白皮書編號(hào)：WP024）

得益于大數(shù)據(jù)的興起和計(jì)算能力的快速提升，機(jī)器學(xué)習(xí)技術(shù)近年來(lái)經(jīng)歷了革命性的發(fā)展。諸如圖像分類、語(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ù)之間的依賴關(guān)系，例如社交網(wǎng)絡(luò)、蛋白質(zhì)分子結(jié)構(gòu)、電子商務(wù)平臺(tái)中的客戶數(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)有得到充分的討論和研究。在撰寫本白皮書時(shí)，谷歌（Google）和百度（Baidu）都無(wú)法搜索到關(guān)于GNN硬件加速的中文研究資料。本白皮書的寫作動(dòng)機(jī)是將國(guó)外最新的GNN算法、對(duì)加速技術(shù)的研究以及對(duì)基于現(xiàn)場(chǎng)可編程邏輯門陣列（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ì)周圍節(jié)點(diǎn)的特征進(jìn)行采樣，并計(jì)算平均值。相鄰節(jié)點(diǎn)的數(shù)量是不確定且無(wú)序的（非歐幾里得數(shù)據(jù)）

2、二維卷積——使用卷積核對(duì)周圍節(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)類型，還專門針對(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：非線性激活，例如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)行非線性處理。

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ǔ)訪問(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í)，它為用戶提供了靈活的硬件可編程性。下圖展示了高性能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)用于其他類似的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ǔ)訪問(wèn)，以支持海量節(jié)點(diǎn)的圖計(jì)算。
• ?400GE以太網(wǎng)控制器用于承載RoCE-Lite協(xié)議。
• ?GDDR6存儲(chǔ)器用于存儲(chǔ)GNN處理過(guò)程中所需的高速訪問(wèn)數(shù)據(jù)（DDR4作為備用大容量存儲(chǔ)器）。該存儲(chǔ)器用于存儲(chǔ)訪問(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ǔ)訪問(wèn)。通過(guò)研究，我們得出這兩個(gè)步驟的特點(diǎn)，具體如下。

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

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

在合并操作中，輸入數(shù)據(jù)是聚合結(jié)果（節(jié)點(diǎn)的低維表示）和權(quán)重矩陣。它的大小和維度是固定的，具有線性存儲(chǔ)位置。因此對(duì)存儲(chǔ)訪問(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)行非線性處理，同時(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)分類預(yù)測(cè)應(yīng)用中，節(jié)點(diǎn)表示hkv可以通過(guò)一個(gè)全連接層（FC）來(lái)獲取節(jié)點(diǎn)的分類標(biāo)簽。這個(gè)過(guò)程是傳統(tǒng)的機(jī)器學(xué)習(xí)處理方法之一，在GraphSAGE文獻(xiàn)資料中沒(méi)有體現(xiàn)，這個(gè)功能也沒(méi)有包含在這個(gè)架構(gòu)中。

結(jié)論

本白皮書探討了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加速解決方案。