科研動(dòng)態(tài)
Leda：利用分塊數(shù)據(jù)流在高帶寬內(nèi)存FPGA上加速圖神經(jīng)網(wǎng)絡(luò)中的稀疏矩陣-稠密矩陣乘
中文題目：Leda：利用分塊數(shù)據(jù)流在高帶寬內(nèi)存FPGA上加速圖神經(jīng)網(wǎng)絡(luò)中的稀疏矩陣-稠密矩陣乘
論文題目：Leda: Leveraging Tiling Dataflow to Accelerate SpMM on HBM-Equipped FPGAs for GNNs
錄用期刊/會(huì)議：43rd ACM/IEEE International Conference on Computer-Aided Design (ICCAD '24) (CCF-B類會(huì)議)
原文DOI：https://doi.org/10.1145/3676536.3676773
錄用/見刊時(shí)間：2024-10-27（錄用時(shí)間）
作者列表：
1）伊恩鑫 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)技術(shù) 碩21
2）白佳睿 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù) 本21
3）聶怡婕 中國石油大學(xué)（北京）人工智能學(xué)院 電子信息工程 本22
4）牛 丹 東南大學(xué) 自動(dòng)化學(xué)院
5）金 洲 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)系教師
6）劉偉峰 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)系教師
摘要:
圖神經(jīng)網(wǎng)絡(luò)（GNNs）在從圖結(jié)構(gòu)中提取數(shù)據(jù)表征方面發(fā)揮著關(guān)鍵作用，推動(dòng)了多個(gè)領(lǐng)域的發(fā)展。稀疏矩陣-稠密矩陣乘（SpMM）是GNN的核心運(yùn)算之一。但是，由于圖矩陣的高度稀疏性和非零元的隨機(jī)分布，加速SpMM面臨著巨大挑戰(zhàn)。新興的高帶寬內(nèi)存（HBM）的高并發(fā)能力為加速SpMM提供了新機(jī)遇。然而，由于負(fù)載不均衡和隨機(jī)內(nèi)存訪問模式，在HBM FPGA上加速SpMM仍然困難重重。
在本文中，我們介紹了配備HBM的FPGA上的高性能SpMM加速器Leda。通過利用分塊稀疏格式來平衡負(fù)載并增強(qiáng)數(shù)據(jù)局部性。最小相似度重排算法顯著改善了寫后讀（RAW）依賴。此外，改進(jìn)的外積數(shù)據(jù)流調(diào)度策略有效緩解了隨機(jī)內(nèi)存訪問瓶頸。最后，我們提出了一種基于定制數(shù)據(jù)流的高度并行的硬件架構(gòu)設(shè)計(jì)，并探索了輸入矩陣的重用性。實(shí)驗(yàn)結(jié)果表明，Leda在幾何平均吞吐量和能效方面，分別比當(dāng)前最先進(jìn)的SpMM加速器Sextans和SDMA，以及K80 GPU高出1.27倍和1.36倍、1.85倍和2.00倍、1.95倍和5.23倍。
背景與動(dòng)機(jī):
目前，現(xiàn)有研究已在通用計(jì)算平臺(tái)（如CPU和GPU）上提出了SpMM的加速方案。然而，由于缺乏專用的內(nèi)存結(jié)構(gòu)和數(shù)據(jù)流設(shè)計(jì)，這些方案在訪存效率和計(jì)算資源占用率方面表現(xiàn)不佳。配備HBM的FPGA因其深度內(nèi)存結(jié)構(gòu)定制和高并發(fā)能力，已成為加速SpMM的極具吸引力的平臺(tái)。然而，充分利用HBM來加速SpMM仍然充滿挑戰(zhàn)，主要包括以下幾個(gè)方面：（1）現(xiàn)有的稀疏存儲(chǔ)格式和并行方法導(dǎo)致處理單元（PE）間的負(fù)載高度不均衡；（2）圖結(jié)構(gòu)的冪律分布引入隨機(jī)內(nèi)存訪問模式和較差的數(shù)據(jù)局部性；（3）RAW依賴導(dǎo)致的高延遲限制了計(jì)算資源占用率和吞吐量。
設(shè)計(jì)與實(shí)現(xiàn):
一、分塊稀疏存儲(chǔ)格式
我們使用稀疏塊作為基本單位，確保PE間相對(duì)負(fù)載平衡；為了利用輸入稠密矩陣的重用性，我們用CSC格式來存儲(chǔ)稀疏塊；為了減少額外控制開銷，我們利用列主序COO格式存儲(chǔ)每個(gè)稀疏塊中的非零元信息；設(shè)置16位無符號(hào)掩碼數(shù)組，存儲(chǔ)非零元位置信息。
圖 1：分塊稀疏存儲(chǔ)格式
二、最小相似度重排算法
我們提出了一種最小相似度重排算法。該算法利用掩碼數(shù)組計(jì)算稀疏塊中列間相似度，進(jìn)而以列為單位進(jìn)行非零元重排，同時(shí)結(jié)合插值操作，有效消除原始數(shù)據(jù)流中的RAW依賴。
圖 2：最小相似度重排算法
三、改進(jìn)的外積數(shù)據(jù)流
我們以16×16固定分區(qū)大小的稀疏塊作為外積數(shù)據(jù)流的基本單元。由于中間積規(guī)模較小，片上緩沖區(qū)可完全容納，既避免了大量片外流量，又提高了輸入矩陣的重用性。
圖 3：改進(jìn)的外積數(shù)據(jù)流
四、Leda的硬件架構(gòu)設(shè)計(jì)
我們精心規(guī)劃了HBM通道的分配方案，以充分利用內(nèi)存帶寬；專用計(jì)算核心陣列中的矩陣乘法單元（MMU）可以跳過稀疏矩陣中的空白結(jié)構(gòu)，以減少冗余的片上內(nèi)存寫入，靈活的重用隊(duì)列暫存可復(fù)用元素，以提高稠密矩陣重用性，設(shè)置多個(gè)PE組以提高計(jì)算并行性；累加器中的矩陣?yán)奂訂卧∕AU）平衡了傳輸與計(jì)算速度，并且支持快速隨機(jī)讀寫。
圖 4：Leda的硬件架構(gòu)設(shè)計(jì)
實(shí)驗(yàn)結(jié)果及分析:
一、Leda與FPGA上的SpMM加速器對(duì)比
Leda的幾何平均吞吐量分別比最新的SpMM加速器Sextans-hls和Sextans-tapa高出1.27倍和1.02倍。此外，幾何平均能源效率分別提高了1.36倍和1.10倍。
圖 5：Leda與Sextans-hls和Sextans-tapa的吞吐量與能效對(duì)比
二、Leda與K80 GPU對(duì)比
Leda與K80 GPU上的cuSPARSE和GE-SpMM相比，幾何平均吞吐量分別提高了1.95倍和1.58倍，幾何平均能效分別提高了5.23倍和4.23倍。
三、Leda與2060 GPU對(duì)比
Leda與2060 GPU上的cuSPARSE和GE-SpMM相比，幾何平均吞吐量分別提高了0.41倍和0.33倍（值得注意的是，2060 GPU的頻率遠(yuǎn)高于Leda，幾乎是其8倍左右），幾何平均能效分別提高了1.49倍和1.18倍。
圖 6：Leda與cuSPARSE和GE-SpMM在K80 GPU和2060 GPU上的吞吐量與能效對(duì)比
四、預(yù)處理開銷分析
我們比較了Leda的預(yù)處理與CPU上單次SpMM的執(zhí)行時(shí)間。在絕大多數(shù)矩陣上，預(yù)處理時(shí)間幾乎等同于單次SpMM的時(shí)間。只有少數(shù)大型圖矩陣的預(yù)處理時(shí)間略高于單次SpMM時(shí)間。不過，由于經(jīng)過一次預(yù)處理后，在聚合階段可以進(jìn)行多次SpMM迭代，因此Leda的預(yù)處理開銷可以忽略不計(jì)。
圖 7：12個(gè)圖矩陣上的預(yù)處理時(shí)間和單次SpMM執(zhí)行時(shí)間的對(duì)比
結(jié)論:
本文中，我們?cè)谂鋫銱BM的FPGA上提出了一種用于GNNs的高性能SpMM加速器Leda。采用分塊稀疏格式的定制數(shù)據(jù)流充分利用了HBM的優(yōu)勢(shì)。最小相似度重排算法顯著改善了累加階段的RAW依賴。改進(jìn)的外積數(shù)據(jù)流緩解了隨機(jī)訪存瓶頸。以MMU為中心的硬件架構(gòu)設(shè)計(jì)進(jìn)一步提高了并行性和數(shù)據(jù)重用性。實(shí)驗(yàn)結(jié)果表明，與當(dāng)前最先進(jìn)的SpMM加速器和GPU實(shí)現(xiàn)相比，Leda在吞吐量和能效方面展現(xiàn)出了顯著的提升。
通訊作者簡介:
金洲，副教授，中國石油大學(xué)（北京）計(jì)算機(jī)系副教授，入選北京市科協(xié)青年人才托舉工程、校青年拔尖人才。主要從事集成電路設(shè)計(jì)自動(dòng)化（EDA）、面向科學(xué)計(jì)算的DSA軟硬件協(xié)同設(shè)計(jì)等方面的研究工作。主持并參與國家自然科學(xué)基金青年項(xiàng)目、重點(diǎn)項(xiàng)目，科技部重點(diǎn)研發(fā)微納電子專項(xiàng)、高性能計(jì)算專項(xiàng)青年科學(xué)家項(xiàng)目，國家重點(diǎn)實(shí)驗(yàn)室開放課題、企業(yè)橫向課題等。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國際會(huì)議和期刊上發(fā)表60余篇高水平學(xué)術(shù)論文。獲EDA2青年科技獎(jiǎng)、SC23最佳論文獎(jiǎng)、ISEDA23榮譽(yù)論文獎(jiǎng)、IEEJ九州支部長獎(jiǎng)等。
聯(lián)系方式：jinzhou@cup.edu.cn