（白皮書編號：WP024）

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

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

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

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

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

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

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

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

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

對GraphSAGE算法的介紹

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

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

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

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

圖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、利用聚合信息預(yù)測圖形情況和標(biāo)簽

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

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

Step 1： Sample a sub-graph node with neighborhood function N［}。

步驟1：使用近鄰函數(shù)N［}對子圖節(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：對每個(gè)深度搜索進(jìn)行迭代

Step 8： Final node embedding of node v

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上述特點(diǎn)使Achronix Speedster7t1500器件成為應(yīng)對在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的存儲可擴(kuò)展性

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：用于計(jì)算的高速存儲

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é)議的輕量級版本，用于通過高速以太網(wǎng)進(jìn)行遠(yuǎn)程存儲訪問，以支持海量節(jié)點(diǎn)的圖計(jì)算。
• ?400GE以太網(wǎng)控制器用于承載RoCE-Lite協(xié)議。
• ?GDDR6存儲器用于存儲GNN處理過程中所需的高速訪問數(shù)據(jù)（DDR4作為備用大容量存儲器）。該存儲器用于存儲訪問頻率相對較低的數(shù)據(jù)，例如待預(yù)處理的圖形數(shù)據(jù)。
• ?PCIe Gen5 ×16 接口提供高速主機(jī)接口，用于與服務(wù)器軟件進(jìn)行數(shù)據(jù)交互。

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

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

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

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

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

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

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

• ?聚合器——通過單指令多數(shù)據(jù)（SIMD）處理器陣列，對圖形相鄰節(jié)點(diǎn)進(jìn)行采樣和聚合。單指令可以預(yù)定義為mean（）平均值計(jì)算，或其他適用的聚合函數(shù)；多數(shù)據(jù)是指單次mean（）均值計(jì)算中需要多個(gè)相鄰節(jié)點(diǎn)的特征數(shù)據(jù)作為輸入，這些數(shù)據(jù)來自子圖采樣器。SIMD處理器陣列通過調(diào)度器Agg Scheduler進(jìn)行負(fù)載平衡。子圖采樣器通過NoC從GDDR6或DDR4讀回的鄰接矩陣和節(jié)點(diǎn)特征數(shù)據(jù)h0v分別緩存在鄰接列表緩沖區(qū)（Adjacent List Buffer）和節(jié)點(diǎn)特征緩沖區(qū)（Node Feature Buffer）。聚合的結(jié)果hkN（v）存儲在聚合緩沖區(qū)（Aggregation Buffer）中。
• ?合并器——通過脈動(dòng)矩陣PE對聚合結(jié)果進(jìn)行卷積運(yùn)算。卷積核是Wk權(quán)重矩陣。卷積結(jié)果由ReLU激活函數(shù)進(jìn)行非線性處理，同時(shí)也存儲在Partial Sum Buffer中，以用于下一輪迭代。

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

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

結(jié)論

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