圖神經網路加速器深度調研（中）

摘要

近年來，圖神經網路（Graph Neural Networks,GNNs）因為具有對圖結構資料進行建模和學習的能力，而引起了機器學習領域研究者的廣泛關注。在化學、網路、社交媒體、知識表示等領域，由於資料本身具有複雜的聯絡，通常採用圖（Graph）作為資料結構來表示這種關係。隨著各種GNN演算法變體的發展，給這類可以建模為圖結構資料處理任務的領域，帶來了突破性結果。但是，在目前的研究階段，GNN的高效計算仍然是一個非常開放的問題。最主要的原因來自於GNN的計算圖依賴於同時存在的輸入複雜結構的圖資料，計算密集的操作和稀疏訪存的操作等複雜行為，使得傳統的通用計算架構、平行計算架構，或者是定製的圖處理架構在面對GNN任務時都遇到了一定的困難。為此，出現了一系列軟體框架工作或硬體加速器設計工作，分別希望更加充分地利用現有平行計算器件的能力進行GNN的計算，或設計適應GNN計算任務特點的專用硬體達到更高的速度或能效。

不過，目前的架構設計工作還是探索性的，針對GNN計算任務進行特定架構設計的目標、關鍵問題定義、通用技術等還不清晰，不同架構的比較也沒有明確統一的標準。此外，從計算任務上來說，各種GNN演算法變體之間的計算圖差異較大，且新演算法迭代很快，相同的演算法用於不同的任務，計算負載特徵也會有較大不同。所以，現有的加速器研究還不能滿足要求。針對這樣的情況，我們透過對GNN演算法的調研，給出了GNN演算法的統一建模框架，便於分析GNN計算的特點，指導加速器設計工作，也為下一步從GNN計算任務到構建特定硬體架構並部署的完整流程研究提供了橋樑；透過對現有GNN加速器的調研，我們指出了現有GNN加速器設計的優劣，總結了關建問題、一般設計方法，提出未來的發展趨勢，指導加速器設計工作。

本系列文章筆者鍾凱為清華大學電子工程系博士生；戴國浩為清華大學電子工程系助理研究員、博士後。該文工作得到清華大學和壁仞科技研究院聯合研究專案的支援。

前文回顧：圖神經網路加速器深度調研（上）

GNN加速器分析

3.1 GNN加速器評價指標

一般來說，一個神經網路加速系統的設計應該考慮至少三個主要指標¹：模型準確率（ModelAccuracy）、吞吐量（Throughput）、能量效率（EnergyEfficiency），在有些場景下，延時（Latency）比吞吐量更關鍵，有時靈活性（Flexibility）也非常關鍵。GNN的加速器設計也需要從這些方面進行考察。

(1)準確率

在沒有涉及到軟硬體聯合最佳化的情況下，模型準確率主要是個演算法問題，重要的影響因素包括如何進行資料預處理、如何設計GNN結構並設定相應引數、如何選擇訓練策略等，不過這些因素不是加速器設計和評價的重點；在涉及到軟硬體協同最佳化時，則需要考慮模型準確率，一般來說，透過類似於已經廣泛應用於CNN的高效計算中的壓縮²、量化³、設計低計算量網路結構⁴等技術，可以在吞吐量、能量效率和準確率指標間尋找合適的平衡，並有可能做到在達到同樣準確率的前提下提高能量效率和吞吐量，這也將是之後GNN加速器乃至整個GNN計算系統的關鍵研究點。

(2)吞吐量

GNN計算加速器的吞吐量可以透過下列公式定義：

這一公式與通用的特定任務加速器吞吐效率衡量方式一致，

一般從計算量角度定義，如對一個批次節點生成的Nodeflow進行GNN模型計算時需要的乘法和加法的次數。我們可以透過模型壓縮、新模型設計等方法減少

。

則取決於加速器的片上計算單元數量和時鐘頻率。除了透過純電路最佳化的方法來提高時鐘頻率，或透過增加設計方案的資源預算來增加電路並行度以外，還可以透過軟硬體協同最佳化的方式進行最佳化。比如透過量化演算法那將GNN計算中的資料位寬降低，從而簡化硬體上對應計算單元的資源開銷（甚至可以降低到一位元，從而將乘法簡化為異或⁵）。這樣可以增加計算單元密度，在同等電路面積功耗資源下，提高

。最佳化過程最複雜的影響因素是

，即所有計算單元是否每個週期都能有效工作，這一點在GNN這一具有隨機稀疏計算模式的任務中尤其難以提高，同時也說明具有較大的最佳化空間。該因素會受到訪存能力、架構設計、編譯執行策略的影響，一般來說，透過較好的並行度設計、多模組的流水線設計、高效的儲存排布和合理的資料通路，能夠提高

。同時，透過軟硬體協同最佳化設計，如進行離線資料預處理、線上編譯排程階段進行任務執行順序調整、對模型進行壓縮量化減少訪存壓力和片上快取需求等方式，都有望提高

。

(3)能量效率

GNN計算加速器的能耗可以劃分為計算能耗和訪存能耗：

對於計算能耗，實際執行的計算量是重要因素，一方面可以透過模型壓縮技術減少，另一方面值得注意的是可以透過整個計算系統來減少，包括能支援在Nodeflow上做GNN模型計算的加速器的架構設計。在最初的GNN計算實現中，GNN模型每次都在整個圖資料上進行，其實造成了很多不必要的計算量，透過預處理階段適當的Nodeflow提取，得到最小計算量的流圖，對於減少計算量是必要的。此外，GNN中可能出現中間結果的複用，如前文介紹的GraphSage中的邊訊息提取結果

，以及GAT中邊訊息提取的結果之一

，其實都與

無關而只取決於

，在多個目標節點之間可以複用，可以透過較好的儲存排程和資料通路的支援來避免重複計算。計算能耗的另一個影響因素為單次計算的平均能耗，這一點可以透過量化簡化硬體計算單元實現，也受到基本功能電路IP效能的影響。

對於訪存能耗，訪存數量與架構設計和排程策略相關，在硬體資源預算限制下，設計足夠大小的片上快取、區域性性較好的互聯結構、高命中率的快取策略非常重要。而單次訪存的能耗，則可以透過量化減少資料位寬的方式進行減少。

對於相同的初始GNN計算任務，能量效率是能耗的反比，完成同樣的任務能耗越低，則能量效率越高。一般透過模型壓縮等方式減少了計算量與資料量從而降低能耗，也算作相比於原任務能量效率的提升，不過目前採用這樣技術的加速器設計工作還沒有出現。

3.2 典型工作介紹

圖神經網路的計算模式比較獨特，既有與傳統深度學習一致的密集矩陣乘法計算，也有需要由圖的連線關係決定的稀疏訪存的計算，除了透過演算法、系統的最佳化提高資料訪問的效率，設計相應的圖神經網路計算加速器架構也是提高圖神經網路計算效率的重要方式。目前這類加速器架構設計並不多，大致可以分為兩大類。一類是針對圖神經網路的兩種計算模式設計兩種對應的硬體單元，並對它們之間的片上快取和資料流進行最佳化，稱之為雙段式架構（TwoStage Architecture）；還有一類是用同樣的硬體單元完成稀疏矩陣計算和稠密矩陣計算，稱之為統一式架構（UniformArchitecture）。

(1)雙段式架構

1）HyGCN

⁶這是一篇提出較早的雙段式GNN推理加速器，其架構如圖5所示，兩大主要計算模組分別執行GNN中的聚合操作和組合操作。聚合部分由包含稀疏消除的訪存控制器和多個單指令多資料（SingleInstruction MultipleData，SIMD）核構成，透過在硬體上實現取樣和稀疏消除的單元，該架構可以動態地在稀疏矩陣上進行“滑動”和“收縮”，減少訪存量，多個單指令多資料核可以靈活地配置，以較高的利用率進行聚合。組合部分是由可配置的多個脈動陣列（SystolicArray，SA）架構構成的矩陣乘法單元，多個陣列可以獨立工作或協同工作。本工作實現了GNN計算的基本功能，設計了雙階段流水線，優化了訪存開銷，不過沒有仔細考慮快取中資料複用的設計和層次化的儲存結構。

圖5 HyGCN提出的雙段式GNN加速器架構圖

2）GraphACT

GraphACT⁷提出了一個主機CPU加FPGA加速器實現的GNN訓練系統。主機部分除了執行softmax函式等結果和訓練過程中loss函式的計算，還透過一個精心設計的匹配演算法，對待計算GNN任務進行預處理，將需要計算的資料按照最有利於複用的方式排列好，傳輸到FPGA板卡上的記憶體中；FPGA部分則包含了兩大硬體功能模組，分別進行向量計算和矩陣計算，以及相應的片上快取。由於該工作用於訓練場景，主機上的預處理能夠與FPGA加速器的任務計算並行進行，所以效率較高，圖6是該系統進行GNN訓練任務的時序流程圖。

圖6 GraphACT系統進行GNN訓練任務時的排程時序流程圖

3）GRIP

GReTA⁸和GRIP⁹是一個系列的前後兩篇工作，分別對GNN的計算環節進行了抽象總結，並提出了雙段式架構的GNN推理加速器。相比於HyGCN，GRIP設計的加速器架構強調了Nodeflow的概念：在GNN的推理任務中，通常不需要計算所有節點的輸出，而是隻計算少數節點，從少數輸出節點透過圖的連線關係反推出GNN各層的輸入節點及其連線關係，構成的即最小計算量的一個子圖。GRIP設計了相應的多個快取以及對應的預取模組處理Nodeflow資料，透過交叉陣列的方式傳送給多個並行執行多個節點的聚合任務的單元；節點特徵變換部分則透過權重分塊快取進行加速，總體架構如圖7所示。該工作透過組合各個中間快取之間的資料流動，可以支援多種GNN變體，透過多個快取和計算單元儘可能實現了資料的空間複用，不過交叉陣列還不夠最佳化，也較少考慮資料的時間複用。

圖7 GRIP的架構圖

4）Two-Mode-GCN

¹⁰這是一篇基於FPGA的GNN加速器設計工作。這篇工作相比於之前研究的優勢，一方面在於基於FPGA平臺對加速器架構進行了實際檢驗，另一方面體現在其比較完備的計算流程考慮上。首先本文對預處理環節進行了研究，提出了稀疏化和重排序兩種演算法，分別用於減少鄰邊數量從而減少訪存，以及提高片上資料複用能力。另一方面，本文提出的架構設計雖然也是比較常規的雙階段流水線設計，如圖8所示，但在資料流上明確了乒乓快取的設計，同時將啟用模組獨立出來，並設計了兩種資料流動模式（Mode1和Mode2）。兩種模式分別對應計算流程上的先計算聚合和先計算特徵變換，這兩種模式的詳細設計使得該工作能支援一些GNN變體，也能根據每層輸入輸出特徵維度的不同，選擇合適的模式來增加資料複用量。不過，該工作也存在一些問題：預處理演算法是對全域性離線處理設計的，對採用動態提取Nodeflow的應用場景影響如何沒有明確結論。兩種計算模式其實在同一網路不同層之間想切換時存在困難，以及能夠支援的GNN種類也不足。此外該設計預設採用了32位浮點數格式表示，應該有軟硬體協同最佳化的空間，可以透過資料壓縮或量化進一步提高加速器效能。

圖8 Two-Mode-GCN提出的架構以及兩種資料流模式示意圖

（2）統一式架構

區別於雙段式架構用不同的硬體單元執行圖神經網路的不同部分，統一式架構採用一致的硬體單元完成稀疏和稠密兩種計算。

1）EnGN

EnGN¹¹是統一式架構的一個典型代表，該工作提出了一個神經圖處理單元（NeuralGraph ProcessingUnit，NGPU）來進行GNN中的稀疏矩陣或稠密矩陣乘法計算。具體來說，NGPU由一些彼此相連的處理單元（ProcessingElement，PE）二維陣列構成，每個PE包含乘累加計算單元、度感知的特徵快取、權重快取，能夠更好地利用資料時間複用特性。此外每一列的PE透過被稱之為環邊縮減（RingEdgeReduce，RER）的拓撲結構連線起來，EnGN正是透過這一資料通路進行稀疏矩陣操作，配合圖資料的預處理，將需要聚合的特徵資料通過幾個週期的資料傳遞聚合起來。該工作的架構圖如圖9所示，其優點是度感知的快取減少了訪存數量，且二維陣列結構電路特性更好，不足之處是對GNN的聚合操作支援並不好，RER結構進行聚合存在額外開銷。

圖9 EnGN的架構圖

2）AWB-GCN

AWB-GCN¹²也是一個採用統一式架構的GNN加速器，主要聚焦於稀疏矩陣乘法計算中負載不均衡的問題，提出了分佈平滑、遠端交換、特殊行重對映三種技術進行負載均衡，並在硬體上設計了相應的資料通路支援，從而提高結構統一的PE單元的利用率。由於GNN中稀疏矩陣乘法計算的稀疏矩陣由任務決定，各任務稀疏性不同，所以本文還提出了一個自動調優模組，通過當前週期執行情況，調整下一週期的部署策略，從而可以在同一資料集上多次執行GNN演算法的情況下，自動調優使得硬體利用率提高。

3）GNNA

GNNA¹³提出的加速器架構比較特殊，頂層是由同一結構的模組構成的陣列，互相之間透過片上網路（NetworkonChip，NoC）連線，但模組內部採用了不同單元執行GNN演算法的不同部分，其一個模組的內部結構如圖10所示。透過配置NoC網路彙總計算模組和訪存模組的不同比例，GNNA架構可以實現與GPU相同計算量、相同訪存頻寬、與CPU相同頻寬等配置。透過將複雜的隨機地址資料訪問交給NoC，使得該工作頂層架構簡單，模組內部也不用過多考慮訪存的問題，但是NoC和交叉陣列的開銷很大。

圖10 GNNA提出的透過NoC連線的計算模組內部結構

未完待續。。。

作者介紹

鍾凱，2019年本科畢業於清華大學電子工程系，目前在清華大學電子工程系電路與系統研究所攻讀博士學位，在汪玉教授和戴國浩博士後的指導下，主要從事神經網路的量化演算法、硬體加速、基於FPGA的加速器開發等工作。

戴國浩，現清華大學電子工程系助理研究員、博士後，分別於2019年和2014年在清華大學電子工程系獲得博士與學士學位。主要研究方向為大規模圖計算、異構計算、存算一體、虛擬化等，曾獲ASPDAC 2019最佳論文獎、DATE 2018最佳論文提名。

參考文獻

1、

Guo, Kaiyuan, et al. “[DL] A Survey of FPGA Based Neural Network Accelerator.” ACM Transactions on Reconfigurable Technology and Systems, vol. 9, no. 4, p. 22.

2、 Han, Song, et al. “Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding.” ArXiv:1510.00149 [Cs], Feb. 2016. arXiv.org, http://arxiv.org/abs/1510.00149.

3、 Jacob, Benoit, et al. “Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 2704–13.

4、 Tan, Mingxing, and Quoc V. Le. “EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks.” ArXiv:1905.11946 [Cs, Stat], Sept. 2020. arXiv.org, http://arxiv.org/abs/1905.11946.

5、 Bahri, Mehdi, et al. “Binary Graph Neural Networks.” ArXiv:2012.15823 [Cs], Dec. 2020. arXiv.org, http://arxiv.org/abs/2012.15823.

6、 Yan, Mingyu, et al. “HyGCN: A GCN Accelerator with Hybrid Architecture.” 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), IEEE, 2020, pp. 15–29. DOI.org (Crossref), doi:10.1109/HPCA47549.2020.00012.

7、 Zeng, Hanqing, and Viktor Prasanna. “GraphACT: Accelerating GCN Training on CPU-FPGA Heterogeneous Platforms.” The 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Feb. 2020, pp. 255–65. arXiv.org, doi:10.1145/3373087.3375312.

8、 Kevin, Kiningham, et al. “GReTA: Hardware Optimized Graph Processing for GNNs.” Proceedings of the Second SysML Conference, ACM, 2017, pp. 1–5. DOI.org (Crossref), doi:10.1145/3079856.3080246.

9、 Kiningham, Kevin, et al. “GRIP: A Graph Neural Network Accelerator Architecture.” ArXiv:2007.13828 [Cs], July 2020. arXiv.org, http://arxiv.org/abs/2007.13828.

10、 Zhang, B., et al. “Hardware Acceleration of Large Scale GCN Inference.” 2020 IEEE 31st International Conference on Application-Specific Systems, Architectures and Processors (ASAP), 2020, pp. 61–68. IEEE Xplore, doi:10.1109/ASAP49362.2020.00019.

11、 Liang, Shengwen, et al. “EnGN: A High-Throughput and Energy-Efficient Accelerator for Large Graph Neural Networks.” ArXiv:1909.00155 [Cs], Apr. 2020. arXiv.org, http://arxiv.org/abs/1909.00155.

12、 Geng, Tong, et al. “AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing.” ArXiv:1908.10834 [Cs], Apr. 2020. arXiv.org, http://arxiv.org/abs/1908.10834.

13、 Auten, A., et al. “Hardware Acceleration of Graph Neural Networks.” 2020 57th ACM/IEEE Design Automation Conference (DAC), 2020, pp. 1–6. IEEE Xplore, doi:10.1109/DAC18072.2020.9218751.

往期推薦

1、圖神經網路加速器深度調研（上）

2、片上系統設計案例分析-Xbox主機

3、深度反演方法的可靠性分析