基于“部分向量复制”的高带宽利用率 SpMV FPGA 加速器：架构、公式与实验复现-电子产品世界手机版

基于“部分向量复制”的高带宽利用率 SpMV FPGA 加速器：架构、公式与实验复现

嵌入式系统时间：2025-11-06来源：

摘要

稀疏矩阵-向量乘（SpMV）在图计算、机器学习和工程仿真等场景中广泛使用，并常常主导整体运行时间。针对 FPGA 的高外存带宽与可定制数据通路，本文重构并评述 ASP-DAC’23 提出的“通过部分向量复制实现高带宽利用率的 SpMV”方案。该方案以读无冲突的向量缓冲区、写无冲突的加法树以及乒乓寄存器为核心，目标是在不显著增加数据冗余的前提下，提升归一化带宽利用率（BU）。作者在真实平台上报告相较最新方案的**平均 1.10×**性能提升。

1. 问题与动机

1.1 SpMV 的瓶颈本质

SpMV 只对非零元进行乘加，导致输入向量访问按列索引呈不规则跳转，CPU/GPU 端常出现缓存未命中与带宽受限，难以发挥算力；而 FPGA 具备更高效的外存带宽使用潜力与可编程流水线，更契合存储受限应用。因此，如何在 FPGA 上提高 BU（Bandwidth Utilization） 成为关键。

1.2 既有路线的不足

三类典型做法：

列流式执行（CSC/列优先）：容易产生部分和的写后读冲突，拖慢流水；
用向量值替代列索引（ReDESK）：假设极稀疏，且以宽数据替代窄索引，会引入显著数据冗余；
整向量上片+重排（ReOrder）：用大 BRAM/URAM 存全向量，再做元素级重排以缓解端口冲突；但效果强依赖非零分布，难以消除全部冲突，复杂度与延迟上升。

结论：核心矛盾是向量不规则访问引发的端口冲突与失衡，这是 BU 下降的根源。

2. 方案总览：部分向量复制 + 两类“无冲突”单元

基本思想：把大矩阵按列切成块（block），每块对应的向量片段足够小时，在片上做双份复制，为多 PE 并行提供足够读端口；同时在写回端用写无冲突加法树提前合并同一行的部分和，避免写地址冲突；批（batch）间用乒乓寄存器隐藏部分和装/存的访存开销。

作者标注的三点贡献如下：

读无冲突向量缓冲区：在多于 2 次并发访问时仍不阻塞流水；
写无冲突加法树：消除对同一累加器地址的并发写入冲突，最小化批内写延迟；
乒乓寄存器：批切换时并行完成“上批存/下批装”，隐藏访存开销。

3. 数学刻画与复杂度

3.1 BU 定义与性能分解

论文采用归一化 BU：

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

其中 $N_{text{nonzero}}$ 来自每非零元一次乘法一次加法。流水执行下的总周期：

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

分别为向量装载、所有批执行与流水起始的开销（ $CpipeC_{text{pipe}}$ 为常数）。

3.2 向量装载与批执行模型

若向量长度为 $N_v$ ，单元素字节数 $B_v$ ，外设接口字宽 $Datawidthbytetext{Datawidth}_{text{byte}}$ ：

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

。

批执行周期取计算与部分和访存二者的较大者。设第 $i$ 批含非零元 $N_i$ ，PE 数为 $N$ ，部分和访存开销为 $CpsumC_{text{psum}}$ ，则

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

。

注：后续数据预处理会补零对齐，以满足批内整除与隐藏 $CpsumC_{text{psum}}$ 的需要，从而简化控制并稳定流水。

4. 数据预处理与矩阵分块

4.1 双向分块：列向块 + 行成批

列向块（block width 由 BRAM 约束）：保证每块对应的向量片段能在 BRAM 中一份变两份；
行向批（batch height 由 LUT/累加器资源约束）：控制加法树/累加器资源规模。
示例中把 $12 \times 12$ 矩阵切为 2 个块、每块 3 个批，对应地向量切为 2 个长度为 6 的片段，块内批-批执行、块间顺序推进，最终把各块的部分和合并成输出。

4.2 预处理算法（要点）

为每批统计非零元 $N_p$ ，按 PE 数补零，使 $N_p/Nrceil$ 对齐；
比较 $N_p/Nrceil$ 与 $CpsumC_{text{psum}}$ ，若前者更小，再额外补零以隐藏部分和访问开销；
输出数据顺序：向量段 + 若干批（含对齐零），利于顺序 DMA 装载与简单控制。
算法总体复杂度 $O(N_bN_p)$ ，在实际分块/分批下远小于矩阵规模，具备良好扩展性。

5. 关键硬件模块

5.1 系统数据通路

数据自 DRAM 进入解码器，根据类型送至向量缓冲区、矩阵缓冲区与累加器；4×PE 取数相乘，产物进入写无冲突加法树，再由累加器累计到片上部分和缓冲（PSB, URAM），块完成后回写 DRAM。

5.2 读无冲突向量缓冲区（核心：部分复制）

外设 512-bit 带宽每拍可装 8 个 64-bit 向量元素；BRAM 每拍仅 2 写口，故将每个向量段复制两份组成两个子缓冲，并在每份内用 4 片 BRAM + 4:1 MUX 组织读路，由两份合计提供4 个独立读端口对接 4×PE；
BRAM 端口时分复用：装载阶段用作写口、计算阶段用作读口，保持资源可控。

5.3 写无冲突加法树（核心：地址冲突提前合并）

当多个 PE 产物指向同一行时，通过MUX 选择 + 多级流水加法把冲突项先加在树内，再输出到不同“无冲突”端口写累加器，典型两路冲突 $P_{0,0}$ 与 $P_{2,0}$ 的处理流程被给出（含寄存级数与交叉开关选择）。

5.4 乒乓寄存器（批间装/存隐藏）

每个累加器从单寄存器拓展为 R1/R2/R3：当前批累计、下批装载、上批存储三者并行，按“R1→R2→R3”轮转，完全隐藏批切换过程中的部分和装/存开销。

6. 动机示例复盘：为何它更快？

以 $6 \times 6$ 的玩具矩阵（8 个非零）为例：

ReOrder：受 BRAM 2 读口限制与部分和写冲突影响，需要5 拍完成；
本文方案：向量复制提供 4 读口，同周期释放 4 个非零；加法树消除写冲突，2 组（4+4）在3 拍完成。
该例还说明：我们无需依赖重排即可获得稳定并行度——但为避免“整向量复制”超出 BRAM，必须先分块再复制向量片段。

7. 实验设置与对比

平台与频率：Xilinx Zynq UltraScale ZCU106（XCZU7EV，外设 512-bit），设计运行在 100 MHz。
关键参数：列块宽度设置为 $2^{14}$ （由 BRAM 约束），批高 64（由 LUT/累加器约束）。
基线：对比 ReDESK 与 ReOrder（同平台）。
数据集：UF Sparse 集合 12 个矩阵（如 pwtk, stanford, rma10 等），规模与稀疏度见表。

7.1 理论峰值 BU

在 64 B 数据宽下，每拍处理 4 个非零（值+索引在本设计的 512-bit 通道组织下达成），理论最少周期 $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 个矩阵上，本文方案的平均 BU 高于 ReDESK（1.26×）与 ReOrder（1.10×），且对 stanford 等列极稀疏矩阵，重排法难以避免向量端口冲突，我们仍保持优势。

7.3 资源占用与批高权衡

批高增大可提升平均 BU，但会显著增加累加器 LUT 消耗，实践中选 64 折中；
与 ReOrder 同平台对比：我们用手写 Verilog 管线乘法器，DSP 占用仅 ~2%；乒乓寄存器虽增 FF，但总体 FF 仍更少；LUT 因累加器侧更高；BRAM 因“部分复制”小于 ReOrder；URAM 用于部分和，与 ReOrder 同量级，在 pwtk 上最大约 66%。

8. 工程解构与实现要点

I/O 组织：按“向量段 + 批数据”顺序下发，DMA 顺序读；批内已按 (5) 对齐，控制简化。
矩阵/向量缓冲：矩阵侧 4×FIFO 与 4×PE 匹配，深度较小（装消速率相近）；向量侧“两份子缓冲+MUX”提供 4 读口，端口时分读写。
冲突化解：

读冲突：由“部分复制”与端口编排根除；
写冲突：加法树内合并同地址产物，再输出到 4 路无冲突写口。

批间切换：R1/R2/R3 三工位“当前累计/下批装载/上批写回”循环滚动，隐藏 $CpsumC_{text{psum}}$ 。

9. 适用性与局限

适用性：当矩阵规模大、列分块后向量段能“双份驻留 BRAM”且批高可覆盖行段时，方案能稳定提供 ≥4 路无冲突读与无冲突写回；对列极稀疏且重排失效的矩阵（如 stanford），优势更明显。
局限：

受 BRAM/LUT 约束，块宽/批高的选择需在 BU 与资源间权衡；
为隐藏 $CpsumC_{text{psum}}$ 需要补零对齐，在极端稀疏/分布不均时可能增加少量无效传输。

10. 结论与复现建议

本文重构表明，“部分向量复制 + 写无冲突加法树 + 乒乓累加器”可在不引入显著冗余的情况下，实现更高的带宽利用率与更稳健的并行度。实测（ZCU106，100 MHz，512-bit 外设）显示对比两类先进基线的平均 1.10× 提升。

工程复现 Checklist

评估 BRAM 容量，选定块宽使每向量段可双份驻留；
依据 LUT/CARRY 可用量选批高，与加法树/累加器规模匹配；
落地预处理：对齐 $N_p/Nrceil$ ，必要时按 $CpsumC_{text{psum}}$ 再补零；
实作“2×子缓冲 + 4:1 MUX”的读无冲突向量缓冲；
实作多级流水写无冲突加法树，保证同地址合并；
部分和 PSB 置于 URAM，并实现R1/R2/R3 乒乓协议。

公式与符号速览

SpMV 基式

$yi=∑j=0colsAi,j⋅xj,Ai,j≠0y_i=sum_{j=0}^{text{cols}}A_{i,j}cdot x_j,quad A_{i,j}neq 0$

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

总周期分解

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

向量装载周期

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

批执行周期

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

关键词：

加入微信
获取电子行业最新资讯
搜索微信公众号：EEPW
或用微信扫描左侧二维码