|
Achronix 白皮書(shū)，編號：WP024 得益于大數據的興起和計算能力的快速提升，機器學(xué)習技術(shù)近年來(lái)經(jīng)歷了革命性的發(fā)展。諸如圖像分類(lèi)、語(yǔ)音識別和自然語(yǔ)言處理等機器學(xué)習任務(wù)，都是對具有一定大小、維度和有序排列的歐幾里得數據進(jìn)行處理。然而，在許多現實(shí)場(chǎng)景中，數據是由復雜的非歐幾里得數據（例如圖形）表示的。這些圖形不僅包含數據，還包含數據之間的依賴(lài)關(guān)系，例如社交網(wǎng)絡(luò )、蛋白質(zhì)分子結構、電子商務(wù)平臺中的客戶(hù)數據等。數據復雜性的提升給傳統的機器學(xué)習算法設計及其實(shí)現技術(shù)帶來(lái)了嚴峻的挑戰。在這種情況下，許多全新的基于圖形的機器學(xué)習算法或圖神經(jīng)網(wǎng)絡(luò )（GNN）不斷在學(xué)術(shù)界和工業(yè)界涌現。 GNN對計算能力和存儲有非常高的要求，而且其算法的軟件實(shí)現效率非常低。因此，業(yè)界對GNN的硬件加速有著(zhù)非常迫切的需求。盡管傳統的卷積神經(jīng)網(wǎng)絡(luò )（CNN）硬件加速有很多種解決方案，但GNN的硬件加速還沒(méi)有得到充分的討論和研究。在撰寫(xiě)本白皮書(shū)時(shí)，谷歌（Google）和百度（Baidu）都無(wú)法搜索到關(guān)于GNN硬件加速的中文研究資料。本白皮書(shū)的寫(xiě)作動(dòng)機是將國外最新的GNN算法、對加速技術(shù)的研究以及對基于現場(chǎng)可編程邏輯門(mén)陣列（FPGA）的GNN加速技術(shù)的探討相結合，并以概述的形式呈現給讀者。 對圖神經(jīng)網(wǎng)絡(luò )（GNN）的介紹 在宏觀(guān)層面上，GNN的架構與傳統CNN有很多相似之處，諸如卷積層、池化、激活函數、機器學(xué)習處理器（MLP）、全連接層（FC layer）等模塊，這些都可以應用到GNN。下圖展示了一個(gè)相對簡(jiǎn)單的GNN架構。 
圖1：典型的GNN架構（來(lái)源：https://arxiv.org/abs/1901.00596） 但是，GNN中的圖形數據卷積計算與傳統CNN中的二維卷積計算不同。以下圖為例，紅色目標節點(diǎn)的卷積計算過(guò)程如下所示： 1、圖卷積 - 使用近鄰函數對周?chē)濣c(diǎn)的特征進(jìn)行采樣，并計算平均值。相鄰節點(diǎn)的數量是不確定且無(wú)序的（非歐幾里得數據） 2、二維卷積——使用卷積核對周?chē)濣c(diǎn)的特征進(jìn)行采樣，并計算加權平均值。相鄰節點(diǎn)的數量是確定且有序的（歐幾里得數據）
圖2：圖卷積和二維卷積（來(lái)源：https://arxiv.org/abs/1901.00596） 對GraphSAGE算法的介紹 學(xué)術(shù)界對GNN算法進(jìn)行了大量的研究和探討，提出了相當多的創(chuàng )新實(shí)現方法。其中，由斯坦福大學(xué)（Stanford University）于2017年提出的GraphSAGE是一種歸納表示學(xué)習算法，用于預測大規模圖中動(dòng)態(tài)的、全新的、未知的節點(diǎn)類(lèi)型，還專(zhuān)門(mén)針對節點(diǎn)數量龐大、節點(diǎn)特征豐富的圖進(jìn)行了優(yōu)化。如下圖所示，GraphSAGE算法的計算過(guò)程可以分為三個(gè)主要步驟： 1、相鄰節點(diǎn)采樣——用于降低復雜性，一般采樣兩層，每層采樣幾個(gè)節點(diǎn)。 2、聚合——用于嵌入目標節點(diǎn)，即圖的低維向量表示。 3、預測——使用嵌入作為全連接層的輸入，以預測目標節點(diǎn)d的標簽。
圖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、利用聚合信息預測圖形情況和標簽 為了在FPGA中實(shí)現GraphSAGE算法加速，必須了解其數學(xué)模型，以便將算法映射到不同的邏輯模塊。下圖所示的代碼說(shuō)明了該算法的數學(xué)過(guò)程。
圖4：GraphSAGE算法的數學(xué)模型（來(lái)源：http://snap.stanford.edu/graphsage） Step 1: Sample a sub-graph node with neighborhood function N[}. 步驟1：使用近鄰函數N[}對子圖節點(diǎn)進(jìn)行采樣。 Step 2: Aggregate features from neighbor nodes, e.g. mean[}, lstm[}, polling[} 步驟2：聚合相鄰節點(diǎn)的特征，例如mean[}、lstm[}、polling[} Step3: Combine aggregated node features. E.g. convolution[} 步驟3：合并聚合的節點(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：標準化 Step 7: Iterate for each search-depth 步驟7：對每個(gè)深度搜索進(jìn)行迭代 Step 8: Final node embedding of node v 步驟8：節點(diǎn)v的最終節點(diǎn)嵌入 對于每個(gè)要處理的目標節點(diǎn)xv，GraphSAGE算法都會(huì )執行以下操作： 1、通過(guò)近鄰采樣函數N(v)對子圖中的節點(diǎn)進(jìn)行采樣。 2、聚合要采樣的相鄰節點(diǎn)的特征。聚合函數可以是mean()、lstm()或polling()等。 3、將聚合結果與上一次迭代的輸出表示合并起來(lái)，并使用Wk進(jìn)行卷積。 4、對卷積結果進(jìn)行非線(xiàn)性處理。 5、多次迭代以結束當前第k層的所有相鄰節點(diǎn)的處理。 6、對第k層迭代的結果進(jìn)行標準化處理。 7、多次迭代以結束對所有K層采樣深度的處理。 8、將最終的迭代結果zv嵌入到輸入節點(diǎn)xv。 GNN加速器設計所面臨的挑戰 GNN算法涉及大量的矩陣計算和存儲訪(fǎng)問(wèn)操作。在傳統的x86架構服務(wù)器上運行這種算法的效率是非常低的，表現為速度慢、能耗高等。 新型圖形處理器（GPU）的應用可以顯著(zhù)提高GNN的計算速度與能效比。但是，GPU在存儲可擴展性方面存在短板，使其無(wú)法處理圖形中的海量節點(diǎn)。GPU的指令執行方式也會(huì )導致計算延遲過(guò)大和不確定性；因此，它不適用于需要實(shí)時(shí)計算圖形的場(chǎng)景。 上面提到的各種設計挑戰，使得業(yè)界迫切需要一種能夠支持高并發(fā)、實(shí)時(shí)計算，擁有巨大存儲容量和帶寬，并可擴展到數據中心的GNN加速解決方案。 基于FPGA設計方案的GNN加速器 Achronix的Speedster®7t系列FPGA產(chǎn)品（以及該系列的第一款器件AC7t1500）是針對數據中心和機器學(xué)習工作負載進(jìn)行了優(yōu)化的高性能FPGA器件，消除了基于中央處理器（CPU）、GPU和傳統FPGA的解決方案中存在的若干性能瓶頸。Speedster7t系列FPGA產(chǎn)品采用了臺積電（TSMC）的7nm FinFET工藝，其架構采用了一種革命性的全新二維片上網(wǎng)絡(luò )（NoC）、獨創(chuàng )的機器學(xué)習處理器矩陣（MLP），并采用高帶寬GDDR6控制器、400G以太網(wǎng)和PCI Express Gen5接口，在確保ASIC級性能的同時(shí)，它為用戶(hù)提供了靈活的硬件可編程性。下圖展示了高性能FPGA器件Speedster7t1500的架構。
圖5：Achronix高性能FPGA器件Speedster AC7t1500的架構 上述特點(diǎn)使Achronix Speedster7t1500器件成為應對在GNN加速器設計中面臨的各種挑戰的完美解決方案。 表1：GNN設計面臨的挑戰和Achronix Speedster7t1500 FPGA器件提供的解決方案
GNN加速器頂層架構 此GNN加速器是為GraphSAGE算法設計的，但是它的設計也可以應用于其他類(lèi)似的GNN算法加速。其頂層架構如下圖所示。
圖6：GNN加速器頂層架構 Synthesizable IPs 可綜合的IP GNN Core: Preforms GNN computation GNN內核：執行GNN計算 RoCE-Lite: Memory scalability with RDMA RoCE-Lite：采用RDMA的存儲可擴展性 Harden IPs 硬化IP NoC: High speed and unified IP connectivity NoC：高速、統一的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：高吞吐量的主機接口 Ethernet 400GE: High speed network 以太網(wǎng)400GE：高速網(wǎng)絡(luò ) 該架構由以下模塊組成： 圖中的GNN內核是算法實(shí)現的核心部分（詳情如下）。 RoCE-Lite是RDMA協(xié)議的輕量級版本，用于通過(guò)高速以太網(wǎng)進(jìn)行遠程存儲訪(fǎng)問(wèn)，以支持海量節點(diǎn)的圖計算。 400GE以太網(wǎng)控制器用于承載RoCE-Lite協(xié)議。 GDDR6存儲器用于存儲GNN處理過(guò)程中所需的高速訪(fǎng)問(wèn)數據（DDR4作為備用大容量存儲器）。該存儲器用于存儲訪(fǎng)問(wèn)頻率相對較低的數據，例如待預處理的圖形數據。 PCIe Gen5 ×16 接口提供高速主機接口，用于與服務(wù)器軟件進(jìn)行數據交互。 上述所有模塊均通過(guò)具有高帶寬的NoC實(shí)現互連。 GNN內核微架構 在開(kāi)始討論GNN內核的微架構之前，有必要先回顧一下GraphSAGE算法。其內層循環(huán)的聚合和合并（包括卷積）占據了該算法的大部分計算和存儲訪(fǎng)問(wèn)。通過(guò)研究，我們得出這兩個(gè)步驟的特點(diǎn)，具體如下。 表2：GNN算法中聚合和合并操作的對比（來(lái)源：https://arxiv.org/abs/1908.10834）
可以看出，聚合操作和合并操作在計算和存儲訪(fǎng)問(wèn)模式上有著(zhù)完全不同的需求。聚合操作涉及相鄰節點(diǎn)的采樣。然而，圖形是一種非歐幾里得數據類(lèi)型——它的大小和維度是不確定且無(wú)序，矩陣稀疏，節點(diǎn)位置隨機。因此，存儲訪(fǎng)問(wèn)是不規則的，并且難以重復利用數據。 在合并操作中，輸入數據是聚合結果（節點(diǎn)的低維表示）和權重矩陣。它的大小和維度是固定的，具有線(xiàn)性存儲位置。因此對存儲訪(fǎng)問(wèn)沒(méi)有挑戰，但是矩陣的計算量非常大。 基于上述分析，我們決定在GNN內核加速器設計中選擇使用兩種不同的硬件結構來(lái)分別處理聚合和合并操作（如下圖示）： 聚合器——通過(guò)單指令多數據（SIMD）處理器陣列，對圖形相鄰節點(diǎn)進(jìn)行采樣和聚合。單指令可以預定義為mean()平均值計算，或其他適用的聚合函數；多數據是指單次mean()均值計算中需要多個(gè)相鄰節點(diǎn)的特征數據作為輸入，這些數據來(lái)自子圖采樣器。SIMD處理器陣列通過(guò)調度器Agg Scheduler進(jìn)行負載平衡。子圖采樣器通過(guò)NoC從GDDR6或DDR4讀回的鄰接矩陣和節點(diǎn)特征數據h0v分別緩存在鄰接列表緩沖區（Adjacent List Buffer）和節點(diǎn)特征緩沖區（Node Feature Buffer）。聚合的結果hkN(v)存儲在聚合緩沖區（Aggregation Buffer）中。 合并器——通過(guò)脈動(dòng)矩陣PE對聚合結果進(jìn)行卷積運算。卷積核是Wk權重矩陣。卷積結果由ReLU激活函數進(jìn)行非線(xiàn)性處理，同時(shí)也存儲在Partial Sum Buffer中，以用于下一輪迭代。
圖7：GNN內核功能框圖 合并結果經(jīng)過(guò)L2BN標準化處理后，即為最終的節點(diǎn)表示hkv。在一個(gè)典型的節點(diǎn)分類(lèi)預測應用中，節點(diǎn)表示hkv可以通過(guò)一個(gè)全連接層（FC）來(lái)獲取節點(diǎn)的分類(lèi)標簽。這個(gè)過(guò)程是傳統的機器學(xué)習處理方法之一，在GraphSAGE文獻資料中沒(méi)有體現，這個(gè)功能也沒(méi)有包含在這個(gè)架構中。 結論 本白皮書(shū)探討了GraphSAGE GNN算法的數學(xué)原理，并從多個(gè)角度分析了GNN加速器設計中的技術(shù)挑戰。通過(guò)分析問(wèn)題并在架構層面逐一解決，提出了一種架構，利用Achronix Speedster7t AC7t1500 FPGA器件提供的具有競爭性的優(yōu)勢，創(chuàng )建了一種高度可擴展的、能夠提供卓越性能的GNN加速解決方案。 有關(guān)Speedster7t系列FPGA器件的更多信息，請訪(fǎng)問(wèn)www.achronix.com。 |
