Da4ml 一个针对 FPGA 上超低延迟神经网络的快速、可扩展且精确的 CMVM 优化框架。

  • 基于图的分解和成本感知的 CSE
  • da4ml 框架实现为一个开源库，集成到 hls4ml 工具中，da4ml 也可以直接生成可综合的 RTL，以启用 CMS 进行 AXOL1TL 异常检测出发的生产部署

背景

常数矩阵算法

分布式算术是一种无乘法器方法，通过用移位加（或减）操作替代乘积累加操作在硬件中实现乘法，这些操作通常映射到 FPGA 上的 LUT。

在无精度损失的情况下使用加法器树实现 CMVM 操作的最先进算法仍是提出的 H_cmvm 算法

  • 该算法寻找将 CMVM 问题转换为潜在更简单子问题的可能变换，并使用类似于启发式的方法来评估每个变换的成本
  • 该算法还支持通过限制搜索相空间来制定生成加法器树的最大允许加法器深度
    计算成本高昂

超低延迟神经网络

设计中资源消耗最多的部分通常是全连接层或卷积层中的矩阵向量乘法。

Da4ml 算法

Hls4ml

Hls4ml 为用户提供了一个高层接口，用于连接流行的机器学习框架和 how 后端，是用户能够以最小努力在 FPGA 上部署神经网络

概述

Da4ml 是一种基于 CSE 的混合算法。与其他基于 CSE 的算法类似，该算法在常数矩阵的离散表示上运行。

在这项工作中，我们采用规范带符号数字表示，CSD 是一种数字的带符号数字表示，永远没有两个连续的非零数字，并且非零数字的数量保证是最少的。因此，对于一个有 x 位数字的数，CSD 表示最多有 [x/2+1] 个非零数字，平均占总数字数的 1/3

  • 首先，用于 M 仅包含定点整数，通过跨行和列应用位移位来对其进行归一化，使得除了零之外没有行/列的所有项都是偶数。记录得到的缩放因子，并将应用于输入/输出向量
  • 基于一种图的方式将常数矩阵 M 分解为两个子矩阵 M1, M2，该方法捕获了跨行的高级公共模式。然后，它对两个子矩阵应用 CSE 以最小化冗余计算，最终优化的加法器树显著减少了 LUT 使用并改善了延迟。

理解与实现

对于 FPGA 这样的硬件来说，乘法器（Multiplier）很贵（占资源多），但移位（Shift）几乎是免费的（只是连线变一下），加法（Add）则介于两者之间。

因此，da4ml 的目标就是：把所有的乘法都变成“移位 + 加法”，然后想办法把重复的加法合并掉。

第一步：理解“移位代替乘法”与 CSD 表示法

在二进制里，乘以 2 的幂次方就是移位。比如 $$x \times 8$$ 就是把x 向左移 3 位。但是，乘以 7 怎么办？

  • 普通二进制方法：$$7=4+2+1$$ (二进制 111)。 这里需要 2 次加法。
  • CSD (Canonical Signed Digit) 方法（论文重点）：$$7=8-1$$ 这里只需要 1 次减法（加法和减法在硬件上代价一样）。

CSD 的核心原则： 允许使用负数（-1），尽量减少非零位的数量，绝不让两个非零位相邻。

第二步：将矩阵乘法拆碎（第一阶段的简化理解）

假设我们有以下矩阵乘法 
$$
y_0=3x_0+3x_1
$$
$$
y_1=5x_0+7x_1
$$
我们先把常数 3, 5, 7 转换成 CSD：

  • $$3 \rightarrow 4-1 \rightarrow (1 \ll 2)-(1\ll 0)$$
  • $$5 \rightarrow 4+1 \rightarrow (1 \ll 2)+(1\ll 0)$$
  • $$7 \rightarrow 8-1 \rightarrow (1 \ll 3)-(1\ll 0)$$
    现在把 y 的计算全部展开成最基础的项（Term）：
  • 对于 y_0:
    • $$x_0 部分：0 \ll 2, -x_0 \ll 0$$
    • $$x_1 部分：x_1 \ll 2, -x_1 \ll 0$$
  • 对于 y_1
    • $$x_0 部分：0 \ll 2, x_0 \ll 0$$
    • $$x_1 部分：0 \ll 3, -x_1 \ll 0$$

在这一步之前，它先看整列。比如，x_0 这一列在 y_0 是3，在 y_1 是5。如果很多列都是“3”和“5”的组合，它就把 (3, 5) 打包成一个图的节点。
该内容不包括 prim 算法

第三步：公共子表达式消除 (CSE) —— 核心中的核心

这是 da4ml 能够省资源的关键。找出重复出现的加法组合。

  1. $$y_0 需要：x 0 \ll2, -x 0\ll0, x 1\ll2, -x 1\ll0$$
  2. $$y_1 需要：x0\ll2, x0\ll0, x1\ll3, -x1\ll0$$

x_0 << 2在 y_0 和 y_1 中都出现了。但这只是单项复用。更高级的是两项组合复用。

假设发现 $$A=x_0 \ll 2$$ 和$$B=-x_1 \ll 0$$在计算中经常一起出现（需要相加）。
如果不优化：

  • $$y_0=…+A+B+…（做一次加法）$$
  • $$y_1=…+A+B+…（又做一次加法）$$
    优化后 (CSE)：
  • $$T_1=A+B（做一次加法）$$
  • $$Y_0=…+T_1+…$$
  • $$Y_1=…+T_1+…$$
    这样就节省了一次加法运算。

da4ml 的 CSE 算法逻辑

  1. 统计频率： 遍历所有还未计算的式子，找出所有可能的“两项相加”组合 
  2. 计算代价： 论文提出了一个代价函数。不仅仅看频率，还要看位宽。
    • 简单理解：两个数位宽越接近、重叠越多，把它们加起来就越“贵”（消耗 LUT 多）。
    • 策略： 我们优先消除那些出现频率高且重叠多（消除后省得多）的组合。
  3. 替换： 选定最优组合（例如 $$T_{new}=x_a \ll s_1 + x_b \ll s_2$$），把它变成一个新的“基础项”，放入池子。
  4. 循环： 重复上述步骤，直到没有可以合并的项j

第四步：da4ml 相比传统算法的改进点

  1. 不只看频率，看“对齐”：
    在选择合并哪两个项时，da4ml 倾向于选择移位量相近的项。
    • A<<10 和 B<<0 相加：这两个数在二进制上几乎不重叠，加法器很简单，甚至不需要进位链，只是简单的拼接。消除它的收益很低。
    • A<<2 和 B<<2 相加：完全重叠，每一位都要算进位，这是最贵的。
    • da4ml 策略： 优先消除那些“贵”的加法（重叠多的）。
  2. 两阶段优化：
    在第一阶段，它把常数矩阵 M 分解成了 $$M=M_1 \times M_2$$
    • M_1: 基础构件块。
    • M_2: 稀疏的组合系数。
      这相当于先在宏观上找了一次规律（比如很多列都是由“基础列 A”和“基础列 B”加减得来的），然后再在微观上做 CSE。这大大加快了处理大规模矩阵的速度。