《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 人工智能 > 解決方案 > 一種基于FPGA的圖神經(jīng)網(wǎng)絡(luò)加速器解決方案

一種基于FPGA的圖神經(jīng)網(wǎng)絡(luò)加速器解決方案

2021-08-10
來源:Achronix

  得益于大數(shù)據(jù)的興起和計算能力的快速提升,,機(jī)器學(xué)習(xí)技術(shù)近年來經(jīng)歷了革命性的發(fā)展,。諸如圖像分類、語音識別和自然語言處理等機(jī)器學(xué)習(xí)任務(wù),,都是對具有一定大小,、維度和有序排列的歐幾里得數(shù)據(jù)進(jìn)行處理,。然而,,在許多現(xiàn)實場景中,,數(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è)計及其實現(xiàn)技術(shù)帶來了嚴(yán)峻的挑戰(zhàn)。在這種情況下,,許多全新的基于圖形的機(jī)器學(xué)習(xí)算法或圖神經(jīng)網(wǎng)絡(luò)(GNN)不斷在學(xué)術(shù)界和工業(yè)界涌現(xiàn),。

  GNN對計算能力和存儲有非常高的要求,而且其算法的軟件實現(xiàn)效率非常低,。因此,,業(yè)界對GNN的硬件加速有著非常迫切的需求。盡管傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)(CNN)硬件加速有很多種解決方案,,但GNN的硬件加速還沒有得到充分的討論和研究,。在撰寫本白皮書時,谷歌(Google)和百度(Baidu)都無法搜索到關(guān)于GNN硬件加速的中文研究資料,。本白皮書的寫作動機(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。下圖展示了一個相對簡單的GNN架構(gòu),。

微信截圖_20210810170004.png

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

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

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

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

微信截圖_20210810170040.png

  圖2:圖卷積和二維卷積(來源:https://arxiv.org/abs/1901.00596)

  對GraphSAGE算法的介紹

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

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

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

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

微信截圖_20210810170108.png

  圖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中實現(xiàn)GraphSAGE算法加速,必須了解其數(shù)學(xué)模型,,以便將算法映射到不同的邏輯模塊,。下圖所示的代碼說明了該算法的數(shù)學(xué)過程。

微信截圖_20210810170139.png

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

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

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

  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:標(biāo)準(zhǔn)化

  Step 7: Iterate for each search-depth

  步驟7:對每個深度搜索進(jìn)行迭代

  Step 8: Final node embedding of node v

  步驟8:節(jié)點v的最終節(jié)點嵌入

  對于每個要處理的目標(biāo)節(jié)點xv,,GraphSAGE算法都會執(zhí)行以下操作:

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

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

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

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

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

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

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

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

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

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

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

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

  基于FPGA設(shè)計方案的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),、獨創(chuàng)的機(jī)器學(xué)習(xí)處理器矩陣(MLP),并采用高帶寬GDDR6控制器,、400G以太網(wǎng)和PCI Express Gen5接口,,在確保ASIC級性能的同時,它為用戶提供了靈活的硬件可編程性,。下圖展示了高性能FPGA器件Speedster7t1500的架構(gòu),。

微信截圖_20210810170232.png

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

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

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

微信截圖_20210810170316.png

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

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

微信截圖_20210810170349.png

  圖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的存儲可擴(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:用于計算的高速存儲

  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)核是算法實現(xiàn)的核心部分(詳情如下),。

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

  ·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實現(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)

  微信截圖_20210810170449.png

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

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

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

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

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

微信截圖_20210810170536.png

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

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

  結(jié)論

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




微信圖片_20210517164139.jpg

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,,并不代表本網(wǎng)站贊同其觀點,。轉(zhuǎn)載的所有的文章、圖片,、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容,、版權(quán)和其它問題,,請及時通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,,避免給雙方造成不必要的經(jīng)濟(jì)損失,。聯(lián)系電話:010-82306118;郵箱:[email protected],。