機(jī)器學(xué)習(xí)實(shí)戰(zhàn)：GNN（圖神經(jīng)網(wǎng)絡(luò)）加速器的FPGA解決方案

應(yīng)用Achronix?Speedster7t FPGA設(shè)計(jì)高能效、可擴(kuò)展的GNN加速器

作者：袁光 （Kevin?Yuan），Achronix資深現(xiàn)場(chǎng)應(yīng)用工程師

1.?概述

得益于大數(shù)據(jù)的興起以及算力的快速提升，機(jī)器學(xué)習(xí)技術(shù)在近年取得了革命性的發(fā)展。在圖像分類、語(yǔ)音識(shí)別、自然語(yǔ)言處理等機(jī)器學(xué)習(xí)任務(wù)中，數(shù)據(jù)為大小維度確定且排列有序的歐氏（Euclidean）數(shù)據(jù)。然而，越來(lái)越多的現(xiàn)實(shí)場(chǎng)景中，數(shù)據(jù)是以圖（Graph）這種復(fù)雜的非歐氏數(shù)據(jù)來(lái)表示的。Graph不但包含數(shù)據(jù)，也包含數(shù)據(jù)之間的依賴關(guān)系，比如社交網(wǎng)絡(luò)、蛋白質(zhì)分子結(jié)構(gòu)、電商平臺(tái)客戶數(shù)據(jù)等等。數(shù)據(jù)復(fù)雜度的提升，對(duì)傳統(tǒng)的機(jī)器學(xué)習(xí)算法設(shè)計(jì)以及其實(shí)現(xiàn)技術(shù)帶來(lái)了嚴(yán)峻的挑戰(zhàn)。在此背景之下，諸多基于Graph的新型機(jī)器學(xué)習(xí)算法—GNN（圖神經(jīng)網(wǎng)絡(luò)），在學(xué)術(shù)界和產(chǎn)業(yè)界不斷的涌現(xiàn)出來(lái)。

GNN對(duì)算力和存儲(chǔ)器的要求非常高，其算法的軟件實(shí)現(xiàn)方式非常低效，所以業(yè)界對(duì)GNN的硬件加速有著非常迫切的需求。我們知道傳統(tǒng)的CNN（卷積神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)）硬件加速方案已經(jīng)有非常多的解決方案；但是，GNN的硬件加速尚未得到充分的討論和研究，在本文撰寫之時(shí)，Google和百度皆無(wú)法搜索到關(guān)于GNN硬件加速的中文研究。本文的撰寫動(dòng)機(jī)，旨在將國(guó)外最新的GNN算法、加速技術(shù)研究、以及筆者對(duì)GNN的FPGA加速技術(shù)的探討相結(jié)合起來(lái)，以全景圖的形式展現(xiàn)給讀者。

2.?GNN?簡(jiǎn)介

GNN的架構(gòu)在宏觀層面有著很多與傳統(tǒng)CNN類似的地方，比如卷積層、Polling、激活函數(shù)、機(jī)器學(xué)習(xí)處理器（MLP）和FC層等等模塊，都會(huì)在GNN中得以應(yīng)用。下圖展示了一個(gè)比較簡(jiǎn)單的GNN架構(gòu)。

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

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

lGraph卷積：以鄰居函數(shù)采樣周邊節(jié)點(diǎn)特征并計(jì)算均值，其鄰居節(jié)點(diǎn)數(shù)量不確定且無(wú)序（非歐氏數(shù)據(jù)）。

l2D卷積：以卷積核采樣周邊節(jié)點(diǎn)特征并計(jì)算加權(quán)平均值，其鄰居節(jié)點(diǎn)數(shù)量確定且有序（歐氏數(shù)據(jù)）。

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

3.?GraphSAGE算法簡(jiǎn)介

學(xué)術(shù)界已對(duì)GNN算法進(jìn)行了非常多的研究討論，并提出了數(shù)目可觀的創(chuàng)新實(shí)現(xiàn)方式。其中，斯坦福大學(xué)在2017年提出的GraphSAGE是一種用于預(yù)測(cè)大型圖中動(dòng)態(tài)新增未知節(jié)點(diǎn)類型的歸納式表征學(xué)習(xí)算法，特別針對(duì)節(jié)點(diǎn)數(shù)量巨大、且節(jié)點(diǎn)特征豐富的圖做了優(yōu)化。如下圖所示，GraphSAGE計(jì)算過(guò)程可分為三個(gè)主要步驟：

圖?3：GraphSAGE算法的視覺(jué)表述（來(lái)源：http://snap.stanford.edu/graphsage）

l鄰節(jié)點(diǎn)采樣：用于降低復(fù)雜度，一般采樣2層，每一層采樣若干節(jié)點(diǎn)

l聚合：用于生成目標(biāo)節(jié)點(diǎn)的embedding，即graph的低維向量表征

l預(yù)測(cè)：將embedding作為全連接層的輸入，預(yù)測(cè)目標(biāo)節(jié)點(diǎn)d的標(biāo)簽

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

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

對(duì)于每一個(gè)待處理的目標(biāo)節(jié)點(diǎn)xv，GraphSAGE?執(zhí)行下列操作：

1）通過(guò)鄰居采樣函數(shù)N（v），采樣子圖(subgraph)中的節(jié)點(diǎn)

2）聚合被采樣的鄰節(jié)點(diǎn)特征，聚合函數(shù)可以為mean()、lstm()或者?polling()等

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

4）卷積結(jié)果做非線性處理

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

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

7）迭代若干次以結(jié)束所有K層采樣深度的處理

8）最終迭代結(jié)果zv即為輸入節(jié)點(diǎn)xv的嵌入（embedding）

4.?GNN加速器設(shè)計(jì)挑戰(zhàn)

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

新型GPU的應(yīng)用，可以為GNN的運(yùn)算速度和能效比帶來(lái)顯著收益。然而GPU內(nèi)存擴(kuò)展性的短板，使其無(wú)法勝任海量節(jié)點(diǎn)Graph的處理；GPU的指令執(zhí)行方式，也造成了計(jì)算延遲過(guò)大并且不可確定，無(wú)法勝任需要實(shí)時(shí)計(jì)算Graph的場(chǎng)景。

如上所述種種設(shè)計(jì)挑戰(zhàn)的存在，使得業(yè)界急需一種可以支持高度并發(fā)實(shí)時(shí)計(jì)算、巨大內(nèi)存容量和帶寬、以及在數(shù)據(jù)中心范圍可擴(kuò)展的GNN加速解決方案。

5.?GNN加速器的FPGA設(shè)計(jì)方案

Achronix 公司推出的 Speedster7t系列高性能FPGA，專門針對(duì)數(shù)據(jù)中心和機(jī)器學(xué)習(xí)工作負(fù)載進(jìn)行了優(yōu)化，消除了CPU、GPU以及傳統(tǒng) FPGA 存在的若干性能瓶頸。Speedster7t FPGA 基于臺(tái)積電的 7nm FinFET 工藝，其架構(gòu)采用革命性的新型 2D 片上網(wǎng)絡(luò) （NoC），獨(dú)創(chuàng)的機(jī)器學(xué)習(xí)處理器矩陣 （MLP），并利用高帶寬 GDDR6 控制器、400G 以太網(wǎng)和 PCI Express Gen5 接口，在保障ASIC 級(jí)別性能的同時(shí)，為用戶提供了靈活的硬件可編程能力。下圖展示了Speedster7t1500高性能FPGA的架構(gòu)。

圖5:?Achronix?Speedster7t1500?高性能FPGA?架構(gòu) （來(lái)源：http://www.achronix.com）

如上所述種種特性，使得Achronix?Speedster7t1500 FPGA器件為GNN加速器設(shè)計(jì)中所面臨的各種挑戰(zhàn)，提供了完美的解決方案。

表1：GNN設(shè)計(jì)挑戰(zhàn)與Achronix的Speedster7t1500?FPGA解決方案

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

本GNN加速器針對(duì)GraphSAGE進(jìn)行設(shè)計(jì)，但其架構(gòu)具有一定的通用性，可以適用于其他類似的GNN算法加速，其頂層架構(gòu)如下圖所示。

圖6:?GNN加速器頂層架構(gòu)（來(lái)源：Achronix原創(chuàng)）

圖中GNN?Core為算法實(shí)現(xiàn)的核心部分，其設(shè)計(jì)細(xì)節(jié)將在下文展開(kāi)談?wù)?；RoCE-Lite為RDMA協(xié)議的輕量級(jí)版本，用于通過(guò)高速以太網(wǎng)進(jìn)行遠(yuǎn)程內(nèi)存訪問(wèn)，以支持海量節(jié)點(diǎn)的Graph計(jì)算，其設(shè)計(jì)細(xì)節(jié)將在本公眾號(hào)的后續(xù)文章中討論；400GE以太網(wǎng)控制器用來(lái)承載RoCE-Lite協(xié)議；GDDR6用于存放GNN處理過(guò)程中所需的高速訪問(wèn)數(shù)據(jù)；DDR4作為備用高容量?jī)?nèi)存，可以用于存儲(chǔ)相對(duì)訪問(wèn)頻度較低的數(shù)據(jù)，比如待預(yù)處理的Graph；PCIe?Gen5x16提供高速主機(jī)接口，用于與服務(wù)器軟件交互數(shù)據(jù)；上述所有模塊，皆通過(guò)NoC片上網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)高速互聯(lián)。

5.2?GNN?Core?微架構(gòu)

在開(kāi)始討論GNN?Core?微架構(gòu)之前，我們先回顧一下本文第3節(jié)中的GraphSAGE算法，其內(nèi)層循環(huán)的聚合以及合并（包含卷積）等兩個(gè)操作占據(jù)了算法的絕大部分計(jì)算和存儲(chǔ)器訪問(wèn)。通過(guò)研究，我們得到這兩個(gè)步驟的特征如下：

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

可以看出，聚合操作與合并操作，其對(duì)計(jì)算和存儲(chǔ)器訪問(wèn)的需求完全不同。聚合操作中涉及到對(duì)鄰節(jié)點(diǎn)的采樣，然而Graph屬于非歐氏數(shù)據(jù)類型，其大小維度不確定且無(wú)序，矩陣稀疏，節(jié)點(diǎn)位置隨機(jī)，所以存儲(chǔ)器訪問(wèn)不規(guī)則并難以復(fù)用數(shù)據(jù)；在合并操作中，其輸入數(shù)據(jù)為聚合結(jié)果（節(jié)點(diǎn)的低維表征）以及權(quán)重矩陣，其大小維度固定，存儲(chǔ)位置規(guī)則線性，對(duì)存儲(chǔ)器訪問(wèn)不存在挑戰(zhàn)，但是矩陣的計(jì)算量非常大。

基于以上分析，我們決定在GNN?Core加速器設(shè)計(jì)中用兩種不同的硬件結(jié)構(gòu)來(lái)處理聚合操作與合并操作，功能框圖如下圖所示：

圖7:?GNN?Core功能框圖（來(lái)源：Achronix原創(chuàng)）

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

合并器（Combinator）：通過(guò)脈動(dòng)矩陣PE來(lái)執(zhí)行聚合結(jié)果的卷積操作；卷積核為Wk權(quán)重矩陣；卷積結(jié)果通過(guò)ReLU激活函數(shù)做非線性處理，同時(shí)也存儲(chǔ)在Partial?Sum?Buffer中以方便下一輪迭代。

合并的結(jié)果通過(guò)L2BN歸一化處理之后，即為最終的節(jié)點(diǎn)表征hkv。

在比較典型的節(jié)點(diǎn)分類預(yù)測(cè)應(yīng)用中，該節(jié)點(diǎn)表征hkv可以通過(guò)一個(gè)全連接層（FC），以得到該節(jié)點(diǎn)的分類標(biāo)簽。此過(guò)程屬于傳統(tǒng)的機(jī)器學(xué)習(xí)處理方法之一，沒(méi)有在GraphSAGE論文中體現(xiàn)，此設(shè)計(jì)中也沒(méi)有包含這個(gè)功能。

6.?結(jié)論

本文深入討論了GraphSAGE?GNN?算法的數(shù)學(xué)原理，并從多個(gè)維度分析了GNN加速器設(shè)計(jì)中的技術(shù)挑戰(zhàn)。作者通過(guò)分解問(wèn)題并在架構(gòu)層面逐一解決的方法，綜合運(yùn)用Achronix?Speedster7t1500?FPGA所提供的競(jìng)爭(zhēng)優(yōu)勢(shì)，創(chuàng)造了一個(gè)性能極佳且高度可擴(kuò)展的GNN加速解決方案。