Winograd与余数系统融合：数字滤波器性能优化新路径

1. 项目概述：当Winograd遇上余数系统，数字滤波器的性能革命

在数字信号处理的世界里，滤波操作就像流水线上的核心质检员，实时甄别、筛选着海量的数据流。无论是医学影像去噪、雷达信号分析，还是视频流的实时增强，滤波器的性能直接决定了整个系统的“反应速度”和“吞吐量”。传统滤波器架构的核心瓶颈在于其密集的乘法累加运算，每一次卷积操作都伴随着大量的乘法，这在硬件实现上意味着更长的延迟和更高的功耗。

近年来，两个看似独立的领域——算法优化和硬件算术——的交叉融合，为解决这一瓶颈提供了新思路。一方面，Winograd算法通过巧妙的数学变换，用额外的加法操作替代了部分昂贵的乘法，本质上是“用时间换空间”思想在计算复杂度上的精妙实践。另一方面，余数系统作为一种非位置数制，允许将一个大整数的运算分解为多个独立、并行的小模数运算，天生适合硬件并行加速。当我们将Winograd的计算结构与RNS的并行特性相结合，并针对FPGA等可编程逻辑的硬件特性，选用如2^α和2^α-1这类“特殊模数”时，便催生了一种全新的高性能数字滤波器架构。这种架构并非简单的叠加，而是从算法原理到硬件实现层面的深度协同设计，旨在榨干硬件每一份潜力，实现速度的飞跃。本文就将深入拆解这一融合了Winograd方法与余数系统的二维数字滤波器架构，从理论推导、硬件设计到性能对比，为你呈现一次从算法到芯片的完整性能优化之旅。

2. 核心原理深度解析：为何是Winograd与RNS的联姻？

要理解这个架构的威力，我们必须先抛开具体实现，深入其背后的数学与计算原理。这不仅仅是两个技术的简单拼接，而是一次针对乘法密集型计算任务的系统性重构。

2.1 Winograd方法：以加代乘的计算艺术

Winograd算法的核心思想源于多项式环和中国剩余定理。对于一维卷积F(n, k)，它不直接计算输出，而是通过构造变换矩阵G、B、A，将卷积运算转化为“变换-点乘-反变换”的三步过程。其中，最关键的“点乘”步骤的乘法次数，远少于原始卷积所需的n*k次。

以论文中重点研究的F(2, 2)为例，它处理2x2的滤波器核与3x3的输入块，产出2x2的输出。传统直接卷积需要2*2*3*3 = 36次乘加。而Winograd通过公式z = A^T [(GfG^T) ⊙ (B^TdB)] A将其重构。这里，f是2x2的滤波器核（常数），d是3x3的输入数据块。GfG^T和B^TdB是预先计算好的变换结果，⊙是逐元素乘法。精妙之处在于，G和B矩阵的元素仅为0、1、-1，这意味着变换过程完全不涉及乘法，仅需加法和减法。整个F(2,2)的运算量被压缩到仅需4次标量乘法（对应⊙操作），其余全是加法。这种牺牲加法次数来换取乘法次数急剧降低的策略，在乘法器远比加法器昂贵的硬件逻辑中，收益是巨大的。

注意：Winograd的优势大小与滤波器尺寸(n, k)密切相关。对于小的滤波器核（如3x3），加速比非常显著。但随着核尺寸增大，变换矩阵会变得稠密，加法操作的增长可能会抵消乘法减少带来的收益，并且数值精度问题也会更突出。因此，F(2,2)或F(4,3)是实践中非常受欢迎且高效的配置。

2.2 余数系统：化整为零的并行哲学

余数系统是一种非位置数制。它选择一个两两互质的模数集合{p1, p2, ..., pη}，任何一个在动态范围P = ∏pi内的整数X，都可以唯一地表示为一组余数(x1, x2, ..., xη)，其中xi = X mod pi。

RNS的最大魅力在于其算术运算的独立性。加法、减法、乘法都可以在各个模数通道内独立并行进行：(A ± B) mod P等价于(|a1 ± b1|p1, ..., |aη ± bη|pη)(A × B) mod P等价于(|a1 × b1|p1, ..., |aη × bη|pη)

这意味着，一个对大整数的复杂运算，被分解为多个对小整数的、完全无数据依赖的并行运算。在硬件上，这可以对应为多个并行的处理单元，天然适合FPGA的并行架构。最终结果再通过基于中国剩余定理的反变换，从余数表示恢复回标准整数。

2.3 特殊模数2^α与2^α - 1：硬件友好的关键选择

RNS的性能优势能否充分发挥，很大程度上取决于模数选取。论文中选用的{2^α, 2^α-1, ...}这类特殊模数集，是硬件实现上的“神来之笔”。

1. 模2^α运算：在二进制世界中，对2^α取模操作异常简单——直接保留该数的低α位即可，等价于截断操作。加法和乘法后对2^α取模，也只需简单截断低位，无需复杂的除法电路。
2. 模2^α - 1运算：对于2^α - 1取模，虽然不像2^α那样直接截断，但可以利用“端回进位”技术。其原理是：一个α位二进制数A，可以看作A = Q*(2^α - 1) + R，其中R是余数。由于2^α ≡ 1 (mod 2^α-1)，因此A mod (2^α-1)等价于将A的二进制表示按α位分组成若干段，将这些段循环累加，直到结果小于2^α。这在硬件上可以通过带循环进位的加法器高效实现。

选择这类模数，使得RNS中最耗资源的“模约减”操作，被简化为了位移和加法，彻底避免了通用的 Barrett 或 Montgomery 约减算法中所需的试除或预计算乘法，极大降低了硬件开销和延迟。

2.4 强强联合：架构优势的乘数效应

将Winograd与RNS结合，产生了1+1>2的效果：

• Winograd层面：将全局的、数据依赖强的卷积计算，解耦为独立的、可并行处理的逐元素乘法点。这正好契合了RNS的并行处理需求。每个模数通道内的U ⊙ V点乘操作，都是独立的小规模计算。
• RNS层面：为Winograd算法中每个独立的乘法点（尽管数量已减少）提供了进一步的并行加速。原本一个b位宽的乘法，被分解为η个并行的、α位宽（α < b）的乘法。更窄位宽的乘法器在硬件上速度更快、面积更小。
• 特殊模数：确保了每个并行通道内的运算（加法、乘法、模约减）都是硬件友好的，使得整个并行流水线能够以最高时钟频率运行。

这种从算法结构到算术单元的全栈优化，是最终实现数倍性能提升的根本原因。

3. 架构设计与硬件实现拆解

理解了“为什么”之后，我们来看“怎么做”。论文提出的F(2×2, 2×2)_RNS架构是一个精密的硬件引擎，其设计充分体现了对上述原理的工程化实现。

3.1 整体架构与数据流

整个处理流程针对一个3x3的输入数据块d，最终产生一个2x2的输出块z。在RNS域中，输入数据d_RNS是一个向量(|d|_2α1, |d|_2α2-1, ...)，输出z_RNS也是对应的余数向量。

架构核心是多个并行的模通道处理单元。如图7所示，对于模数集合{2^α1, 2^α2-1, ..., 2^αη-1}，架构中包含一个F(2×2, 2×2)_2α1模块（处理模2^α1通道）和η-1个F(2×2, 2×2)_2αi-1模块（处理模2^αi-1通道）。所有模块并行工作，输入数据广播到所有通道，各通道独立计算，最后输出汇聚成结果向量。

每个模通道处理单元（以F(2×2, 2×2)_2α为例，见图5）内部遵循 Winograd 的z = A^T [(GfG^T) ⊙ (B^TdB)] A流程，并划分为三个清晰的硬件阶段：

1. 数据变换单元：计算V = B^T d B。由于B矩阵元素仅为0, ±1，此阶段完全由加法器和减法器构成，无需乘法器。
2. 逐元素乘法单元：计算M = U ⊙ V。其中U = G f G^T是滤波器系数变换后的常数（可预计算并硬编码）。此阶段是唯一需要乘法器的部分，包含9个并行的模乘法器MUL_2α。
3. 最终变换单元：计算z = A^T M A。同样，由于A矩阵元素仅为0, 1，此阶段也仅由加法器构成。

3.2 关键硬件模块详解

3.2.1 模加法器：MOMA

无论是数据变换还是最终变换，其核心都是多操作数的模加法。论文采用了多操作数模加法器（MOMA, Multiply Operand Modulo Adder）。其设计非常经典：

• CSA树：首先使用进位保留加法器（CSA）树将多个输入数压缩为两个数（和向量与进位向量）。CSA的优点在于它避免了进位链的传播延迟，可以快速对数个输入进行压缩。
• 最终加法器：将CSA树输出的两个数，通过一个快速的并行前缀加法器（如Kogge-Stone Adder, KSA）进行合并，得到最终的和。对于模2^α-1的加法器（MOMA_2α-1），需要在KSA中集成端回进位逻辑，即将最高位的进位循环加回到最低位。

一个支持N个输入的MOMA_2α，其面积和延迟随α（位宽）和N（操作数个数）对数增长，这为构建大规模加法网络提供了可预测的性能模型。

3.2.2 模乘法器：MUL

逐元素乘法单元中的MUL_2α和MUL_2α-1是性能关键路径。它们通常基于改进的Booth编码或华莱士树结构，并集成了模约减。

• 部分积生成：利用Booth算法或简单的与门阵列，生成乘数的部分积。对于模2^α，生成的部分积就是标准的二进制部分积。对于模2^α-1，部分积生成需要考虑模运算的特性，可能涉及符号扩展和特殊的补偿逻辑。
• 部分积累加：使用另一套CSA树将所有部分积累加，压缩成两个数。
• 模约减与最终相加：将压缩后的两个数送入一个集成了模约减功能的最终加法器。对于MUL_2α，这只是一个普通的α位加法器（溢出位直接丢弃，即模2^α）。对于MUL_2α-1，则需要使用带EAC的最终加法器。

实操心得：在FPGA实现中，DSP Slice是宝贵的硬核乘法器资源。对于较窄的位宽（如α<=18），可以尝试用DSP Slice实现模乘法，其频率通常比用逻辑（LUT）搭建的乘法器更高。但需要仔细设计包装逻辑，将DSP的输出结果映射到模运算的范围内。对于更宽位宽或需要极致面积优化的情况，用LUT和寄存器构建专用的模乘法单元可能更灵活。

3.2.3 数据通路与常数处理

在DT_2α（模2^α数据变换单元）中，由于涉及减法（对应B矩阵中的-1），需要处理负数。在模2^α系统中，负数通常用二进制补码表示。因此，硬件实现时，对于每个减法操作，实际上是将减数取反加一（补码转换），并与一个校正常数C（等于该式中负数出现的次数）一同送入MOMA。如图3a和公式(22)所示，这个校正操作被整合进了加法树，无需单独的取反加一电路，优化了时序。

而对于DT_2α-1（模2^α-1），负数用反码表示，仅需按位取反，无需加一，因此不需要额外的校正常数，简化了设计。

3.3 FPGA实现策略与优化

在将上述架构映射到FPGA（如Xilinx Artix-7）时，有几个关键策略决定了最终的性能：

1. 流水线深度规划：整个F(2×2, 2×2)_RNS模块可以深度流水化。数据变换、点乘、最终变换这三个主要阶段之间必须插入流水线寄存器。更重要的是，在MOMA的CSA树内部、MUL的部分积累加树内部，也可以插入多级流水。目标是使关键路径（通常是某个乘法器或宽位加法器的内部）的延迟小于目标时钟周期，从而尽可能提高系统时钟频率。
2. 资源权衡：使用更多流水线寄存器可以提高Fmax，但会增加FF（触发器）的消耗。使用DSP Slice实现乘法可以节省LUT并提高速度，但DSP数量有限。设计者需要根据目标器件和性能要求，在LUT、FF、DSP、BRAM之间做出权衡。论文中为了通用性比较，可能主要使用LUT实现。
3. 模数集与位宽选择：动态范围P = ∏ pi必须大于滤波器中间结果和最终结果可能出现的最大值。需要根据输入数据位宽、滤波器系数位宽和精度要求，反推所需的总位宽b，然后选择合适的模数集合{2^α1, 2^α2-1, ...}使其乘积P > 2^b。通常，会选择几个位宽相近的模数来平衡各通道的负载。
4. I/O与数据复用：对于一个256x256的图像，需要滑动3x3窗口进行处理。硬件架构应当设计一个高效的滑动窗口缓冲区（例如行缓冲器），以便在每时钟周期能输出一个2x2的结果块，实现吞吐率为1。

4. 性能分析与对比实验

论文通过理论模型和硬件仿真两个维度，系统地评估了所提架构的性能，并与主流方案进行了对比。

4.1 理论模型：“单位门”模型分析

“单位门”模型是一种简化但有效的VLSI复杂度分析模型。它赋予基本逻辑门（AND, OR, XOR等）标准的延迟和面积成本，然后基于此估算复杂电路的成本。

基于此模型，论文推导出了关键模块（MOMA,MUL,DT,EWM,FT）以及整个F(2×2, 2×2)_RNS滤波器的延迟和面积公式（如公式(37)-(39)）。这些公式是α（模数位宽）和η（模数个数）的函数。

对比方案包括：

• 传统MAC滤波器：基于标准乘累加单元的有限冲激响应滤波器。
• 截断MAC滤波器：对MAC单元内部进行优化，牺牲极少精度换取面积和速度提升。
• 基于RNS的TMAC滤波器：将截断MAC与RNS结合。
• 纯Winograd滤波器（PNS）：在传统二进制系统（PNS）中实现Winograd算法。

理论分析的核心结论（对应表2）非常振奋人心：与纯Winograd（PNS）实现相比，Winograd+RNS架构在延迟上降低了24.79% – 66.77%，面积减少了17.59% – 53.67%。这直观地证明了RNS并行化带来的巨大收益。与传统的MAC滤波器相比，新架构在延迟上也有13.47% – 42.04%的优势。最关键的指标——处理一幅256x256图像的时间，新架构比其他已知架构快1.33 到 6.90 倍。

4.2 硬件仿真与FPGA实测

理论需要实践验证。论文在Xilinx Artix-7 FPGA平台上进行了综合与实现，使用Vivado 2018.3工具，策略为性能优先（Flow_PerfOptimized_high）。

评测指标：

• 最大时钟频率：电路能稳定运行的最高时钟速度，直接决定吞吐率。
• 查找表占用：消耗的LUT数量，代表逻辑资源开销。
• 功耗：动态和静态功耗的总和。
• 性能：每秒能处理的256x256信号块数量。

硬件结果分析（对应表3）：

1. 性能：实测性能提升为1.31 – 4.12 倍，与理论预测趋势一致，证实了架构的有效性。提升倍数因对比基线不同而异，相对于最基础的MAC滤波器提升最大。
2. 频率与面积：新架构的最大时钟频率比纯Winograd（PNS）实现高31.03% – 38.46%，这得益于RNS将宽位运算拆分为多个窄位并行运算，缩短了关键路径。但付出的代价是LUT占用大幅增加（是TMAC架构的3.83 – 7.74 倍），这是并行化带来的典型“面积换速度”权衡。
3. 功耗：功耗增加了2.57% – 42.46%。更多的并行活动电路单元必然导致更高的动态功耗。这在许多高性能计算场景中是可接受的交换。
4. 与理论模型的偏差：硬件结果与“单位门”模型预测存在小幅偏差，这主要是由于模型未考虑线延迟、扇出负载、FPGA布线资源竞争等实际物理因素。

注意事项：选择此架构时，必须明确应用场景的优先级。如果追求极致的处理速度和吞吐率，且功耗和面积预算相对宽松（如高性能实时图像处理），那么Winograd+RNS架构是绝佳选择。反之，如果对功耗和芯片面积极其敏感（如边缘IoT设备），则基于TMAC的RNS滤波器或甚至优化后的传统MAC架构可能更合适。

5. 应用场景、局限性与未来展望

5.1 典型应用场景

1. 实时视频处理与计算机视觉：高清视频流中的2D卷积滤波（如边缘检测、高斯模糊、图像锐化）对吞吐率要求极高。本架构的高并行性非常适合用于FPGA加速的实时视频处理管线。
2. 卷积神经网络加速器：Winograd算法最初就是在CNN加速中焕发第二春的。将本架构作为CNN卷积层的硬件核心，可以高效处理3x3卷积核。结合更大的F(n,k)变换（如F(4x4, 3x3)），可以进一步提升CNN推理性能。
3. 数字通信与雷达信号处理：在通信系统的匹配滤波、雷达脉冲压缩等场景中，需要执行大量固定系数的卷积运算。本架构的滤波器系数f是常数，U=GfG^T可以预计算并硬编码，进一步优化性能。
4. 医学影像处理：CT、MRI等影像的重建和后处理算法中包含大量滤波步骤，对计算精度和速度都有要求。可通过调整RNS动态范围来满足精度需求。

5.2 当前架构的局限性

1. 面积开销大：并行化带来了显著的LUT资源消耗，这在资源受限的低端FPGA或ASIC设计中可能成为瓶颈。
2. 模数转换开销：架构假设输入输出已在RNS域。在实际系统中，前端需要二进制到RNS的转换器，后端需要RNS到二进制的反向转换器。这些转换器本身也有延迟和面积成本，在评估端到端系统性能时必须计入。论文专注于核心滤波计算，未包含这部分。
3. 适用于固定小核：F(2,2)针对2x2核优化。虽然可通过重叠分块处理更大图像，但算法本身对更大尺寸卷积核（如5x5,7x7）的加速效益会变化，需要重新推导变换矩阵并评估复杂度。
4. 数值范围限制：RNS的动态范围是固定的。如果中间计算结果超出范围P，会发生溢出且无法恢复。设计时必须谨慎确定数据位宽和模数集，确保整个计算链都在动态范围内。

5.3 未来优化方向

1. 异构计算与高级综合：利用HLS工具，可以更快速地探索不同流水线深度、模数位宽、模数个数下的性能-面积-功耗帕累托前沿。
2. 可重构架构：设计一个支持多种F(n, k)模式（如F(2,2),F(4,3)）和可配置模数集的硬件架构，通过部分重配置来适应不同的算法需求。
3. 精度可调与近似计算：结合截断MAC的思想，在RNS的某些低位宽通道中引入可控的计算近似，以换取更大的面积和功耗节省，适用于对误差有一定容忍度的应用（如机器学习推理）。
4. 系统级集成：将RNS转换器、Winograd滤波核心、存储器控制器等集成到一个完整的IP核中，并提供标准的AXI-Stream或AXI-MM接口，便于在SoC系统中调用。
5. 探索其他特殊模数集：除了{2^α, 2^α-1}，还可以研究其他形式的特殊模数（如2^α+1），或平衡的模数集，以在动态范围、通道均衡性和硬件效率之间取得更好折衷。

这次从算法创新到硬件落地的探索表明，在追求极致性能的道路上，跨层次的协同优化——从数值表示（RNS）到计算算法（Winograd），再到硬件微架构（特殊模数运算单元）——往往能带来突破性的收益。Winograd+RNS架构为高性能数字滤波提供了一条被验证有效的路径，其设计思想对于面临类似计算瓶颈的其他信号处理任务，也具有深刻的启发意义。