基于“部分向量復(fù)制”的高帶寬利用率 SpMV FPGA 加速器：架構(gòu)、公式與實(shí)驗(yàn)復(fù)現(xiàn)

作者：時(shí)間：2025-11-06 來(lái)源：

加入技術(shù)交流群
- 掃碼加入
  和技術(shù)大咖面對(duì)面交流
  海量資料庫(kù)查詢

摘要

稀疏矩陣-向量乘（SpMV）在圖計(jì)算、機(jī)器學(xué)習(xí)和工程仿真等場(chǎng)景中廣泛使用，并常常主導(dǎo)整體運(yùn)行時(shí)間。針對(duì) FPGA 的高外存帶寬與可定制數(shù)據(jù)通路，本文重構(gòu)并評(píng)述 ASP-DAC’23 提出的“通過(guò)部分向量復(fù)制實(shí)現(xiàn)高帶寬利用率的 SpMV”方案。該方案以讀無(wú)沖突的向量緩沖區(qū)、寫(xiě)無(wú)沖突的加法樹(shù)以及乒乓寄存器為核心，目標(biāo)是在不顯著增加數(shù)據(jù)冗余的前提下，提升歸一化帶寬利用率（BU）。作者在真實(shí)平臺(tái)上報(bào)告相較最新方案的**平均 1.10×**性能提升。

1. 問(wèn)題與動(dòng)機(jī)

1.1 SpMV 的瓶頸本質(zhì)

SpMV 只對(duì)非零元進(jìn)行乘加，導(dǎo)致輸入向量訪問(wèn)按列索引呈不規(guī)則跳轉(zhuǎn)，CPU/GPU 端常出現(xiàn)緩存未命中與帶寬受限，難以發(fā)揮算力；而 FPGA 具備更高效的外存帶寬使用潛力與可編程流水線，更契合存儲(chǔ)受限應(yīng)用。因此，如何在 FPGA 上提高 BU（Bandwidth Utilization） 成為關(guān)鍵。

1.2 既有路線的不足

三類典型做法：

列流式執(zhí)行（CSC/列優(yōu)先）：容易產(chǎn)生部分和的寫(xiě)后讀沖突，拖慢流水；
用向量值替代列索引（ReDESK）：假設(shè)極稀疏，且以寬數(shù)據(jù)替代窄索引，會(huì)引入顯著數(shù)據(jù)冗余；
整向量上片+重排（ReOrder）：用大 BRAM/URAM 存全向量，再做元素級(jí)重排以緩解端口沖突；但效果強(qiáng)依賴非零分布，難以消除全部沖突，復(fù)雜度與延遲上升。

結(jié)論：核心矛盾是向量不規(guī)則訪問(wèn)引發(fā)的端口沖突與失衡，這是 BU 下降的根源。

2. 方案總覽：部分向量復(fù)制 + 兩類“無(wú)沖突”單元

基本思想：把大矩陣按列切成塊（block），每塊對(duì)應(yīng)的向量片段足夠小時(shí)，在片上做雙份復(fù)制，為多 PE 并行提供足夠讀端口；同時(shí)在寫(xiě)回端用寫(xiě)無(wú)沖突加法樹(shù)提前合并同一行的部分和，避免寫(xiě)地址沖突；批（batch）間用乒乓寄存器隱藏部分和裝/存的訪存開(kāi)銷。

作者標(biāo)注的三點(diǎn)貢獻(xiàn)如下：

讀無(wú)沖突向量緩沖區(qū)：在多于 2 次并發(fā)訪問(wèn)時(shí)仍不阻塞流水；
寫(xiě)無(wú)沖突加法樹(shù)：消除對(duì)同一累加器地址的并發(fā)寫(xiě)入沖突，最小化批內(nèi)寫(xiě)延遲；
乒乓寄存器：批切換時(shí)并行完成“上批存/下批裝”，隱藏訪存開(kāi)銷。

3. 數(shù)學(xué)刻畫(huà)與復(fù)雜度

3.1 BU 定義與性能分解

論文采用歸一化 BU：

$N_{text{nonzero}}}{text{Datawidth}_{text{byte}}cdot C_{text{total}}}$

其中 $N_{text{nonzero}}$ 來(lái)自每非零元一次乘法一次加法。流水執(zhí)行下的總周期：

$Ctotal=Cldv+Cexe+CpipeC_{text{total}}=C_{text{ldv}}+C_{text{exe}}+C_{text{pipe}}$

分別為向量裝載、所有批執(zhí)行與流水起始的開(kāi)銷（ $CpipeC_{text{pipe}}$ 為常數(shù)）。

3.2 向量裝載與批執(zhí)行模型

若向量長(zhǎng)度為 $N_v$ ，單元素字節(jié)數(shù) $B_v$ ，外設(shè)接口字寬 $Datawidthbytetext{Datawidth}_{text{byte}}$ ：

$Cldv=Nv?BvDatawidthbyteC_{text{ldv}}=frac{N_vcdot B_v}{text{Datawidth}_{text{byte}}}$

。

批執(zhí)行周期取計(jì)算與部分和訪存二者的較大者。設(shè)第 $i$ 批含非零元 $N_i$ ，PE 數(shù)為 $N$ ，部分和訪存開(kāi)銷為 $CpsumC_{text{psum}}$ ，則

$?NiN?)C_{text{exe}}=sum_{i=0}^{N_{text{batch}}}max!left(C_{text{psum}}, leftlceilfrac{N_i}{N}rightrceilright)$

。

注：后續(xù)數(shù)據(jù)預(yù)處理會(huì)補(bǔ)零對(duì)齊，以滿足批內(nèi)整除與隱藏 $CpsumC_{text{psum}}$ 的需要，從而簡(jiǎn)化控制并穩(wěn)定流水。

4. 數(shù)據(jù)預(yù)處理與矩陣分塊

4.1 雙向分塊：列向塊 + 行成批

列向塊（block width 由 BRAM 約束）：保證每塊對(duì)應(yīng)的向量片段能在 BRAM 中一份變兩份；
行向批（batch height 由 LUT/累加器資源約束）：控制加法樹(shù)/累加器資源規(guī)模。
示例中把 $12 \times 12$ 矩陣切為 2 個(gè)塊、每塊 3 個(gè)批，對(duì)應(yīng)地向量切為 2 個(gè)長(zhǎng)度為 6 的片段，塊內(nèi)批-批執(zhí)行、塊間順序推進(jìn)，最終把各塊的部分和合并成輸出。

4.2 預(yù)處理算法（要點(diǎn)）

為每批統(tǒng)計(jì)非零元 $N_p$ ，按 PE 數(shù)補(bǔ)零，使 $N_p/Nrceil$ 對(duì)齊；
比較 $N_p/Nrceil$ 與 $CpsumC_{text{psum}}$ ，若前者更小，再額外補(bǔ)零以隱藏部分和訪問(wèn)開(kāi)銷；
輸出數(shù)據(jù)順序：向量段 + 若干批（含對(duì)齊零），利于順序 DMA 裝載與簡(jiǎn)單控制。
算法總體復(fù)雜度 $O(N_bN_p)$ ，在實(shí)際分塊/分批下遠(yuǎn)小于矩陣規(guī)模，具備良好擴(kuò)展性。

5. 關(guān)鍵硬件模塊

5.1 系統(tǒng)數(shù)據(jù)通路

數(shù)據(jù)自 DRAM 進(jìn)入解碼器，根據(jù)類型送至向量緩沖區(qū)、矩陣緩沖區(qū)與累加器；4×PE 取數(shù)相乘，產(chǎn)物進(jìn)入寫(xiě)無(wú)沖突加法樹(shù)，再由累加器累計(jì)到片上部分和緩沖（PSB, URAM），塊完成后回寫(xiě) DRAM。

5.2 讀無(wú)沖突向量緩沖區(qū)（核心：部分復(fù)制）

外設(shè) 512-bit 帶寬每拍可裝 8 個(gè) 64-bit 向量元素；BRAM 每拍僅 2 寫(xiě)口，故將每個(gè)向量段復(fù)制兩份組成兩個(gè)子緩沖，并在每份內(nèi)用 4 片 BRAM + 4:1 MUX 組織讀路，由兩份合計(jì)提供4 個(gè)獨(dú)立讀端口對(duì)接 4×PE；
BRAM 端口時(shí)分復(fù)用：裝載階段用作寫(xiě)口、計(jì)算階段用作讀口，保持資源可控。

5.3 寫(xiě)無(wú)沖突加法樹(shù)（核心：地址沖突提前合并）

當(dāng)多個(gè) PE 產(chǎn)物指向同一行時(shí)，通過(guò)MUX 選擇 + 多級(jí)流水加法把沖突項(xiàng)先加在樹(shù)內(nèi)，再輸出到不同“無(wú)沖突”端口寫(xiě)累加器，典型兩路沖突 $P_{0,0}$ 與 $P_{2,0}$ 的處理流程被給出（含寄存級(jí)數(shù)與交叉開(kāi)關(guān)選擇）。

5.4 乒乓寄存器（批間裝/存隱藏）

每個(gè)累加器從單寄存器拓展為 R1/R2/R3：當(dāng)前批累計(jì)、下批裝載、上批存儲(chǔ)三者并行，按“R1→R2→R3”輪轉(zhuǎn)，完全隱藏批切換過(guò)程中的部分和裝/存開(kāi)銷。

6. 動(dòng)機(jī)示例復(fù)盤：為何它更快？

以 $6 \times 6$ 的玩具矩陣（8 個(gè)非零）為例：

ReOrder：受 BRAM 2 讀口限制與部分和寫(xiě)沖突影響，需要5 拍完成；
本文方案：向量復(fù)制提供 4 讀口，同周期釋放 4 個(gè)非零；加法樹(shù)消除寫(xiě)沖突，2 組（4+4）在3 拍完成。
該例還說(shuō)明：我們無(wú)需依賴重排即可獲得穩(wěn)定并行度——但為避免“整向量復(fù)制”超出 BRAM，必須先分塊再?gòu)?fù)制向量片段。

7. 實(shí)驗(yàn)設(shè)置與對(duì)比

平臺(tái)與頻率：Xilinx Zynq UltraScale ZCU106（XCZU7EV，外設(shè) 512-bit），設(shè)計(jì)運(yùn)行在 100 MHz。
關(guān)鍵參數(shù)：列塊寬度設(shè)置為 $2^{14}$ （由 BRAM 約束），批高 64（由 LUT/累加器約束）。
基線：對(duì)比 ReDESK 與 ReOrder（同平臺(tái)）。
數(shù)據(jù)集：UF Sparse 集合 12 個(gè)矩陣（如 pwtk, stanford, rma10 等），規(guī)模與稀疏度見(jiàn)表。

7.1 理論峰值 BU

在 64 B 數(shù)據(jù)寬下，每拍處理 4 個(gè)非零（值+索引在本設(shè)計(jì)的 512-bit 通道組織下達(dá)成），理論最少周期 $Nnonzero/4N_{text{nonzero}}/4$ ，代入式 (2) 得

$BUpeak=2Nnonzero64?(Nnonzero/4)=0.125BU_{text{peak}}=frac{2N_{text{nonzero}}}{64cdotleft(N_{text{nonzero}}/4right)}=0.125$

。

7.2 整體性能

在 12 個(gè)矩陣上，本文方案的平均 BU 高于 ReDESK（1.26×）與 ReOrder（1.10×），且對(duì) stanford 等列極稀疏矩陣，重排法難以避免向量端口沖突，我們?nèi)员３謨?yōu)勢(shì)。

7.3 資源占用與批高權(quán)衡

批高增大可提升平均 BU，但會(huì)顯著增加累加器 LUT 消耗，實(shí)踐中選 64 折中；
與 ReOrder 同平臺(tái)對(duì)比：我們用手寫(xiě) Verilog 管線乘法器，DSP 占用僅 ~2%；乒乓寄存器雖增 FF，但總體 FF 仍更少；LUT 因累加器側(cè)更高；BRAM 因“部分復(fù)制”小于 ReOrder；URAM 用于部分和，與 ReOrder 同量級(jí)，在 pwtk 上最大約 66%。

8. 工程解構(gòu)與實(shí)現(xiàn)要點(diǎn)

I/O 組織：按“向量段 + 批數(shù)據(jù)”順序下發(fā)，DMA 順序讀；批內(nèi)已按 (5) 對(duì)齊，控制簡(jiǎn)化。
矩陣/向量緩沖：矩陣側(cè) 4×FIFO 與 4×PE 匹配，深度較小（裝消速率相近）；向量側(cè)“兩份子緩沖+MUX”提供 4 讀口，端口時(shí)分讀寫(xiě)。
沖突化解：

讀沖突：由“部分復(fù)制”與端口編排根除；
寫(xiě)沖突：加法樹(shù)內(nèi)合并同地址產(chǎn)物，再輸出到 4 路無(wú)沖突寫(xiě)口。

批間切換：R1/R2/R3 三工位“當(dāng)前累計(jì)/下批裝載/上批寫(xiě)回”循環(huán)滾動(dòng)，隱藏 $CpsumC_{text{psum}}$ 。

9. 適用性與局限

適用性：當(dāng)矩陣規(guī)模大、列分塊后向量段能“雙份駐留 BRAM”且批高可覆蓋行段時(shí)，方案能穩(wěn)定提供 ≥4 路無(wú)沖突讀與無(wú)沖突寫(xiě)回；對(duì)列極稀疏且重排失效的矩陣（如 stanford），優(yōu)勢(shì)更明顯。
局限：

受 BRAM/LUT 約束，塊寬/批高的選擇需在 BU 與資源間權(quán)衡；
為隱藏 $CpsumC_{text{psum}}$ 需要補(bǔ)零對(duì)齊，在極端稀疏/分布不均時(shí)可能增加少量無(wú)效傳輸。

10. 結(jié)論與復(fù)現(xiàn)建議

本文重構(gòu)表明，“部分向量復(fù)制 + 寫(xiě)無(wú)沖突加法樹(shù) + 乒乓累加器”可在不引入顯著冗余的情況下，實(shí)現(xiàn)更高的帶寬利用率與更穩(wěn)健的并行度。實(shí)測(cè)（ZCU106，100 MHz，512-bit 外設(shè)）顯示對(duì)比兩類先進(jìn)基線的平均 1.10× 提升。

工程復(fù)現(xiàn) Checklist