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

摘要

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

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

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

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

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

關鍵技術點總結

透過對上述工作的對比分析，我們可以總結得出GNN加速器設計工作的一些關鍵技術點。首先就像上文中的兩大類分類那樣，基本的架構選擇上存在雙階段式和統一式兩種架構，他們各有優劣。其次是資料格式上，資料格式作為基本計算單位，對演算法準確率和硬體效能有本質影響，目前這部分的研究還比較少。對於具體的加速器最佳化，最容易想到的是針對GNN稀疏連線關係的特性，最佳化訪問片外記憶體的資料量。其次是片上的資料複用方案，儘可能減少計算單元空閒等待時間，也能減少片外訪存量；具體計算流程上，GNN同樣與CNN類似有多層迴圈，迴圈展開的順序的不同選擇也會影響資料快取方式和計算效能。下面我們將對每一點進行更詳細的介紹。

4.1 整體架構

正如上文中的分類，GNN加速器的整體架構可分為兩大類，對應的是計算流程上如何處理資訊聚合這類稀疏操作和資訊提取特徵變換這類稠密操作。雙階段是架構採用並行結構，設計兩個固定比例的專門的單元分別進行這兩類操作。採用這種模式的好處是單模組的專用性增強，效率更高，尤其是資訊聚合這種稀疏操作，採用專用的計算陣列和片上記憶體訪問邏輯，能夠減少衝突和等待，提高硬體利用率；缺點首先是固定的模組比例，難以在所有網路任務上取得較高的硬體利用率，不可避免出現等待的情況，其次是需要設計相應的資料迴圈順序、模組間快取單元，從而確保兩個重要的功能：前一個模組的部分輸出結果能夠作為後一個模組的輸入、兩個模組的執行先後順序可以改變從而適應不同的網路結構。作為雙階段式代表工作的HyGCN對兩個階段的迴圈順序和模組間快取進行了設計，支援兩個階段的模組片上流水線，透過並行度靈活的任務對映，提出不同的流水線最佳化策略，但是該設計沒有考慮到兩個階段不同的先後執行順序，在支援GraphSage、GAT等先進行稠密計算的任務時存在一定困難。GRIP則考慮到這一點，設計了多個數據可以互相傳遞的片上快取，支援不同的執行順序，並且也透過權重分塊等方式實現片上流水線。不同於雙階段式架構，統一式架構採用同樣的硬體單元支援兩種操作，優勢之一是可以採用本地資料快取，給每個PE設計本地快取，前一個計算完成的資訊提取階段的計算輸出可以直接用於後一個稀疏聚合操作，這種設計的主要缺點是通用處理陣列支援稀疏操作的效率通常不高，要麼需要較為複雜的資料通路設計，比如AWB-GCN，要麼採用邏輯比較簡單但是效率難以保證的邏輯進行稀疏聚合，比如EnGN。雙階段式和統一式架構各有優劣，目前還沒有兩全其美的解決方案和定論，透過資料路徑設計讓兩種模組內部的計算單元或儲存能夠動態排程和複用、基於FPGA等動態可重構平臺面向不同任務進行自動化硬體設計與生成，是兩種比較有潛力的方案。

4.2 資料格式

資料格式是加速器設計不能迴避的關鍵問題，在經典的CNN加速器設計研究歷程中，資料格式由浮點到定點，由高位寬到低位寬，並出現一系列研究量化演算法的研究和一系列支援特殊量化方案的軟硬體系統最佳化設計工作。目前，出現了一些研究GNN模型量化的研究，甚至達到了二值化的量化效果¹²，但是目前的GNN加速器設計還沒有詳細考慮到這一最佳化點進行最佳化，採用的資料格式普遍較為保守。上文中詳細介紹的幾篇工作具體採用資料格式情況如下表所示。可以發現大部分工作採用32位浮點或定點資料格式，但CNN計算任務的加速研究³普遍表明，經過軟硬體協同最佳化，將資料格式轉化為8位定點數普遍是沒有問題的，在這一點上現有GNN加速工作仍有較多的探索空間。

各GNN加速器工作採用的資料格式

此外，CNN加速研究中還有一個很重要的技術稱之為壓縮，或是在原本稠密的CNN計算中尋找稀疏性，或是透過減少通道⁴、權重特徵值分解（SVD）、傅立葉變換（FFT）⁵等方式，減少計算量。在GNN中，雖然鄰接矩陣已經是稀疏的，且這給GNN加速工作帶來了本質困難，但權重、特徵向量的資料規模更大，原本就存在的稀疏性和冗餘性還沒有被髮掘利用，透過類似於CNN中稀疏化、剪枝、壓縮的方案，有希望進一步減小計算量。

4.3 訪存最佳化

在GNN的加速器設計中，片外訪存最佳化是很重要的一步，片外訪存最佳化的目標是讓訪存總量小、單次訪問資料量大。對於GNN計算任務，考慮單層進行分析，多個輸出節點所需要的所有輸入節點集合通常較大，很難全都存到片上，只能先快取部分輸出節點所需要的輸入節點，在這個過程中，可以透過跳過暫時不用的輸入節點資料，減少讀取量，但是在節點特徵長度不長的情況下，按稀疏的方式訪存，單次訪問資料量小，頻寬不能被有效利用。現有的GNN加速器方案中，HyGCN明確提出了新穎的訪存最佳化策略，即透過視窗滑動和收縮，儘可能減少片外訪存量，同時又保證一定的連續性；但是這一方案的具體效能對資料特徵的依賴程度很高，不同資料特徵情況下這種最佳化策略的效果差距很大，而且該方案也沒有考慮到不同的特徵長度情況下的策略，如前所述，當節點特徵長度較長時，以節點為粒度進行記憶體訪問就可以達到訪存量小、訪存規則性高的效果，但節點特徵長度較短時，則多個相鄰節點的資料同時訪問更好。

進行GNN加速器的訪存最佳化，除了上述訪存規模的最佳化外，還有兩個關鍵技術，分別是預處理（資料重排序，Data Reordering）⁶和資料預取（Data Pre-Fetching）⁷。Two-Stage-GCN這篇工作就採用了稀疏化、節點重排序兩種預處理演算法，增加了計算圖中的節點聚集性，減少了額外的資料訪問，同時增加了資料訪問的區域性性，有利於複用。GraphACT也採用了複雜的資料匹配演算法，找到最適合節點間資料重用的計算順序，儘可能減少對片外記憶體資料的訪問。採用預處理的方法好處明顯，但是效果更好的預處理演算法本身開銷也很大，需要綜合考慮整個計算任務的排程能否掩蓋或平攤開銷、整體得到最佳化。比如Two-Stage-GCN提出的場景是圖結構不常變化而節點資料可能變化的場景，針對圖結構進行的預處理能夠多次複用，屬於開銷可以平攤的場景；GraphACT面向的則是訓練場景，每個批次的計算和下個批次的預處理可以並行，屬於開銷可以掩蓋的場景。資料預取則是更加常見的一種方案，可以說每個加速器設計都或多或少用到了資料預取的思想，其中HyGCN、EnGN明確提出資料預取的概念，並設計了相應的單元，其中EnGN作為統一式架構，資料預取單元還為提高聚合操作階段的硬體利用效率起到了作用。GRIP的架構中雖然有名為“pre-fetch”的單元，但其執行的是片上資料的按輸入節點粒度的讀取，並非訪存最佳化中的預取。從上述分析可以看到，資料重排和資料預取作為兩種在傳統圖處理領域廣泛研究並應用的最佳化訪存瓶頸的技術，在GNN加速器的設計中研究的還比較基礎，有較大的探索空間。

4.4 資料複用

資料複用一方面有助於減少加速器整體從片外訪存的資料量，降低訪存瓶頸的影響，另一方面使得片上計算單元資料供給充足，減少等待時間，提高效率。資料複用包含兩個層面，空間複用和時間複用。空間複用是指同樣的資料被不同計算單元需要，主要發生在網路權重上，以及採用與目標節點無關的邊訊息提取方式的網路結構中的邊訊息複用、任何型別的邊訊息提取過程中的輸入節點特徵複用。對於權重的複用，資料流動方式比較規則，利用廣播資料通路就比較容易支援。對於邊訊息和節點特徵的複用則比較複雜，除了透過設計加速器在聚合階段輸出節點上一定的並行度來實現輸入資料的複用外，還需要相應的計算順序排程策略和廣播資料通路，一方面讓能夠複用的資料能夠儘量同時使用完畢，減少單位快取量，相當於增加了片上快取能力，另一方面使資料通路在沒有複用的稀疏情境下也能保持較好的效率不至於額外開銷過大。時間複用是指當前計算單元使用或產生的資料，在之後的時刻被其他計算單元使用，最常見的情況有：聚合階段的結果被變換階段作為輸入使用、聚合或變換階段的部分結果需要繼續累加、權重需要迴圈使用、當前輸入節點會被下一批次的輸出節點使用。這幾種情況都與GNN計算的迴圈展開順序有關，其中前兩種的具體解決方案都是設計足夠的片上快取支援複用，快取規模由計算並行度方案可以理論推匯出；後兩種由於資料規模可能較大，則不能保證完全片上覆用，要設計相應的片外儲存排程策略。目前的加速器設計工作中，針對通常的GNN場景進行了靜態方案設計，但GNN的一大特點是計算流圖由資料本身（鄰接矩陣）決定，在大規模GNN任務計算中，輸入到GNN加速器的任務通常是提取出來的Node flow，在這一過程中可以透過編譯、排程等方式進行最佳化，GRIP提出了支援以Node flow為格式的輸入資料，但沒有設計相應的最佳化，在這方面的軟硬體協同工作還很值得探索。

4.5 迴圈展開

迴圈展開不只是潛在的最佳化技術點，更是加速器設計無法迴避的最基礎的問題，目前被研究的較多，每篇工作都有自己的迴圈展開方案選擇，EnGN、Two-Stage-GCN兩篇工作更是對迴圈展開順序進行了研究，正如上文所述，迴圈展開的順序對片上快取數量、片外訪存數量的部分影響可以透過理論推導得出，這兩篇文章正是基於這樣的理論進行最佳化設計，Two-Stage-GCN的一大貢獻點正是基於此設計了兩種不同順序的資料通路。不過具體的加速器迴圈展開順序、並行度設計是耦合的，整體空間也比目前探究的要大，還需要完整的建模和設計分析工作。

啟發與展望

透過對上述工作的詳細介紹、關鍵最佳化技術點的分析，我們可以發現現有的GNN加速器工作完成了基本的GNN計算功能，發展出了雙階段式和統一式兩種各有優劣的架構，但是普遍存在缺乏軟硬體協同最佳化設計的問題，具體體現在如下方方面。

資料格式

目前的資料格式通常為32位浮點數或定點數，對於訓練任務是否存在冗餘還可以進一步探究，對於推理任務來說顯然精度冗餘較大，但如何浮點訓練的得到的模型轉化為低位寬定點模型，或者如何在訓練階段就考慮到量化誤差進行專門的低位寬模型訓練，還需要深入研究提出具體方案。同樣，在硬體上如何支援相應的低位寬資料格式計算、保持精度的累加器、計算後量化等操作，需要根據量化方案選擇進行協同設計。另一方面，透過稀疏化、分解等方式進行模型壓縮，減少計算量的方案目前在GNN的加速工作中還沒有較好的應用。

預處理、預取

預處理在前文的演算法階段分析中已經有所介紹，包含離線靜態預處理、線上動態預處理等不同種類，在增加稀疏矩陣聚集性、減少片外訪存、增加片上覆用等多方面都有很大潛力，但預處理本身的開銷必須被仔細考慮，具體效果必須面向具體任務得到實踐的檢驗，現有加速器工作利用這一點的還比較少，對系統性能的比較也不清晰。預取和預處理一樣是傳統圖計算加速的典型方法，實際應用中的大規模GNN計算系統同樣具有多層次的儲存單元，目前的加速器工作一方面只涉及到片外片內共兩個層次，另一方面這兩個層次之間的資料預取策略和快取單元設計還不明確，在演算法、硬體兩方面對資料結構和層次都有很大的最佳化空間。

編譯排程

CNN的加速器設計工作也經歷了從固定狀態機驅動的基本功能、配置驅動的多資料通路支援、協同編譯器的指令集架構這樣的發展歷程。GNN加速器的研究，目前一方面還剛發展到配置驅動的多資料通路，還沒有涉及到指令集，另一方面GNN的計算由於不規則性、資料驅動效應明顯，可排程空間其實更大，所帶來的收益也更多。在大規模GNN計算任務中，真正需要加速器執行的計算之前，還有計算圖構建、取樣、預處理環節，這當中可以根據實際場景進行簡單或複雜的排程設計。針對GNN加速器的指令集、編譯器、排程最佳化方案還是一片可以研究的新領域。

在本文編寫期間，又出現了一些新的GNN加速器工作，比如DeepBurningGL⁸，BlockGNN⁹，本文沒有詳細分析對比，但也不會脫離上述演算法分析框架、硬體關鍵最佳化技術點。總體來說，GNN計算任務有不同於CNN和傳統圖計算任務的特點，GNN專用加速器也有較大的設計空間，目前的工作完成了探索性的設計，但具體最佳化點還有很多沒有被詳細研究，尤其是軟硬體協同最佳化的一系列方面，有希望帶來較大的整體效能提升，但因為比較複雜，需要演算法和硬體的同步設計而還沒有被充分研究，這給之後的GNN加速器研究工作帶來了很有希望和潛力的方向。

作者介紹

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

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

參考文獻

1、 Wang, Hanchen, et al. “Binarized Graph Neural Network.” ArXiv:2004.11147 [Cs, Stat], Apr. 2020. arXiv.org, http://arxiv.org/abs/2004.11147.

2、 Wang, Junfu, et al. “Bi-GCN: Binary Graph Convolutional Network.” ArXiv:2010.07565 [Cs], Oct. 2020. arXiv.org, http://arxiv.org/abs/2010.07565.

3、 Qiu, Jiantao, et al. “Going Deeper with Embedded FPGA Platform for Convolutional Neural Network.” Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays – FPGA ’16, ACM Press, 2016, pp. 26–35. doi:10.1145/2847263.2847265.

4、 Schindler, Guenther, et al. “Parameterized Structured Pruning for Deep Neural Networks.” ArXiv:1906.05180 [Cs, Stat], June 2019. arXiv.org, http://arxiv.org/abs/1906.05180.

5、 Wu, D., et al. “SpWMM: A High-Performance Sparse-Winograd Matrix-Matrix Multiplication Accelerator for CNNs.” 2019 International Conference on Field-Programmable Technology (ICFPT), 2019, pp. 255–58. IEEE Xplore, doi:10.1109/ICFPT47387.2019.00041.

6、 Chen, YuAng, and Yeh-Ching Chung. POSTER: Corder: Cache-Aware Reordering for Optimizing Graph Analytics. p. 2.

7、 Kaushik, Anirudh Mohan, et al. “Gretch: A Hardware Prefetcher for Graph Analytics.” ACM Transactions on Architecture and Code Optimization, vol. 18, no. 2, Mar. 2021, pp. 1–25. doi:10.1145/3439803.

8、 Liang, Shengwen, et al. “DeepBurning-GL: An Automated Framework for Generating Graph Neural Network Accelerators.” Proceedings of the 39th International Conference on Computer-Aided Design, ACM, 2020, pp. 1–9. doi:10.1145/3400302.3415645.

9、 Zhou, Zhe, et al. “BlockGNN: Towards Efficient GNN Acceleration Using Block-Circulant Weight Matrices.” ArXiv:2104.06214 [Cs], Apr. 2021. arXiv.org, http://arxiv.org/abs/2104.06214.

往期推薦

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

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

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