1. Strassen多脉动阵列架构解析：当算法优化遇上硬件设计
矩阵乘法作为计算机科学中最基础的运算之一，其性能直接影响着机器学习、图像处理等众多领域的计算效率。传统矩阵乘法的时间复杂度为O(n³)，而Strassen算法通过分治策略将这个复杂度降低到了O(n²·⁸⁰⁷)。但在实际应用中，特别是在硬件实现层面，如何将这种理论上的复杂度优势转化为实际的性能提升或资源节省，一直是个极具挑战性的问题。
脉动阵列（Systolic Array）因其规则的数据流和高度并行的计算特性，成为加速矩阵乘法的理想硬件架构。然而，传统的单脉动阵列设计在面对Strassen算法时，往往难以充分发挥其理论优势。这正是我们提出的多脉动阵列（Multisystolic Array）架构要解决的核心问题——通过创新的硬件设计，将Strassen算法的复杂度优势直接转化为硬件资源的节省和计算效率的提升。
关键突破点：我们的设计实现了Strassen算法中数据移动和加法操作的完全并行化，消除了CPU/GPU实现中常见的额外开销，使得理论复杂度降低能够直接对应到硬件资源的节省上。
2. Strassen算法与脉动阵列的协同设计原理
2.1 Strassen算法的计算重构
传统矩阵乘法将两个n×n矩阵相乘需要n³次乘法和n²(n-1)次加法。而Strassen算法通过将矩阵分块并重新组织计算，将8次子矩阵乘法减少为7次，代价是增加了18次子矩阵加法。对于r级递归，计算复杂度从O(n³)降低到O(n^(log₂7))≈O(n²·⁸⁰⁷)。
算法核心在于以下计算步骤：
T1 = A11 + A22 T2 = A21 + A22 ... Q1 = T1 · S1 ... C11 = Q1 + Q4 - Q5 + Q7 ...这种计算重构虽然减少了乘法次数，但在通用处理器上实现时，额外的数据重组和临时存储操作往往会抵消计算量减少带来的优势。
2.2 脉动阵列的硬件优势
脉动阵列由规则排列的处理单元(PE)构成，数据像"心跳"一样在阵列中有节奏地流动。每个PE独立完成乘累加(MAC)操作，具有以下特点：
- 高度并行：所有PE同时工作
- 数据复用：每个数据元素被多个PE使用
- 规则互联：简化布线，提高时钟频率
传统脉动阵列设计面临两个主要限制：
- 阵列利用率：当矩阵尺寸小于阵列规模时，PE利用率下降
- 资源占用：大规模阵列需要大量乘法器和寄存器
2.3 多脉动阵列的创新设计
我们的SMMr(Strassen Multisystolic Array)架构通过以下创新解决了上述问题：
- 分层递归结构：将大阵列分解为7^r个小阵列，每个小阵列处理Strassen算法的一级递归
- 并行数据通路：专用加法器网络实时计算T/S矩阵，避免中间结果存储
- 内存布局优化：特殊的矩阵存储格式支持同时访问所有子块的行/列
这种设计使得：
- 对于r级递归，DSP资源需求减少(8/7)^r倍
- 最小支持矩阵尺寸降低2^r倍
- 计算吞吐量保持不变
3. 硬件架构的详细实现
3.1 整体架构设计
SMMr架构的核心是一个由7^r个小型脉动阵列组成的网络，如图2所示。每个小型阵列处理Strassen算法的一个递归级别，最低级别使用传统脉动阵列完成基础乘法。
关键组件包括：
- 输入重组单元：将输入矩阵A/B划分为4^r个子块，并按特殊格式存储
- 加法器网络：并行计算所有T/S矩阵(图3)
- 子阵列集群：7个独立的小型脉动阵列，可递归实现
- 输出组合单元：将Q矩阵结果重组为最终输出
3.2 内存访问优化
为实现高效的数据供给，我们设计了特殊的内存布局(图1)：
- 矩阵A：按行交错存储，地址i包含所有从第i行开始每隔m行的数据
- 矩阵B：按列交错存储，类似A但转置
- 每个内存位置包含来自所有子块的对应行/列
这种布局使得：
- 单次内存访问可获取所有子块的对应行/列
- 加法操作可在数据流入阵列时并行完成
- 无需额外存储中间结果
3.3 脉动阵列微架构
基础脉动阵列(图4)采用标准设计，但针对Strassen算法优化：
- 处理单元(PE)结构(图6)包含：
- 乘法器：支持动态位宽调整
- 累加器：带溢出保护
- 双缓冲：隐藏B矩阵加载延迟
- 数据流采用二维脉动模式：
- A矩阵元素沿垂直方向流动
- B矩阵元素沿水平方向流动
- 结果C从对角线输出
3.4 递归实现策略
SMMr架构支持多级递归实现：
- 顶层SMMr分解为7个SMM(r-1)子阵列
- 每个子阵列可继续分解，直到SMM0(基础阵列)
- 每级递归：
- 子阵列规模减小2倍
- 加法器数量减半
- 支持矩阵尺寸减半
这种递归结构使得：
- 资源节省随递归深度指数增长
- 仍保持传统脉动阵列的规则性和可扩展性
4. 关键性能指标与优化效果
4.1 资源利用率分析
在FPGA实现中，我们重点关注两类资源：
- DSP单元：实现乘法运算，通常为设计瓶颈
- 逻辑资源(LUT/FF)：用于控制逻辑和加法器
对于r级递归的SMMr架构：
- DSP需求：减少(8/7)^r倍
- 例如r=2时，DSP节省约1.3倍
- 逻辑资源：与常规设计相当
- 额外加法器消耗被更小规模阵列节省的资源抵消
4.2 乘法器计算效率(MCE)
我们定义乘法器计算效率：
MCE = (理论乘法次数/实际乘法次数) × (实际吞吐量/峰值吞吐量)对于不同架构：
- 传统设计(MMr)：MCE上限为1
- SMMr设计：MCE上限为(8/7)^r
实测数据显示，我们的实现接近理论上限，证明设计有效性。
4.3 实际工作负载表现
在机器学习加速场景下的测试表明：
- 对于24×24矩阵(2级递归)：
- DSP使用减少30%
- 吞吐量保持不变
- 对于32×32矩阵(1级递归)：
- DSP使用减少14%
- 逻辑资源相当
与CPU/GPU实现相比，我们的设计：
- 有效矩阵尺寸下限从1000+降低到24
- 实际加速比更接近理论预期
5. 实现考量与优化技巧
5.1 FPGA实现细节
在实际FPGA部署时，我们采用以下优化策略：
数据位宽管理：
- 基础位宽：8/16位整数量化
- 递归扩展：每级递归增加1位保护位
- 累加器位宽：⌈log₂X⌉额外位(X为阵列宽度)
时钟域交叉：
- 采用异步FIFO连接不同时钟域
- 关键路径流水线化
资源复用：
- 加法器时分复用
- 存储器块分区共享
5.2 常见问题与解决方案
在实际部署中遇到的典型问题及解决方法：
数据依赖问题：
- 现象：计算结果偶尔不正确
- 原因：加法器网络延迟不匹配
- 解决：插入平衡寄存器，统一所有路径延迟
时序违例：
- 现象：高频下功能异常
- 原因：关键路径过长
- 解决：将大型加法器拆分为多级流水线
资源溢出：
- 现象：布局布线失败
- 原因：局部资源紧张
- 解决：手动布局约束，关键模块锁定到特定区域
5.3 设计权衡与选择
在架构设计中需要考虑的关键权衡：
递归深度选择：
- 更深递归：更大资源节省
- 但会增加控制复杂度，限制最小矩阵尺寸
- 推荐：1-2级递归适用于大多数场景
子阵列规模：
- 更小阵列：更高利用率
- 但会增加通信开销
- 推荐：8×8或16×16为平衡点
定点精度：
- 更低精度：更高能效
- 但可能影响计算结果质量
- 推荐：机器学习应用可使用8-16位
6. 应用场景与扩展方向
6.1 机器学习加速
该架构特别适合作为神经网络加速器的矩阵乘法单元：
- 匹配典型神经网络层尺寸(24×24到128×128)
- 可配置递归深度适应不同层
- 实测在ResNet-18上实现1.2×能效提升
6.2 其他适用场景
图像处理：
- 卷积运算转换为矩阵乘法
- 支持小核尺寸高效处理
科学计算：
- 稠密矩阵运算
- 可扩展支持批处理模式
密码学：
- 有限域矩阵运算
- 可定制PE计算单元
6.3 未来扩展方向
混合精度支持：
- 动态可配置位宽
- 自适应精度调整
三维集成：
- 利用硅中介层连接多个阵列
- 进一步提高并行度
近似计算：
- 在加法器网络引入可控误差
- 换取额外能效提升
在实际部署中，我们发现将阵列规模与目标工作负载的常用矩阵尺寸匹配至关重要。例如，针对边缘推理场景，选择24×24基础阵列配合2级递归可获得最佳性价比。而对于云端训练，32×32阵列配合1级递归可能更合适。这种设计已经在我们开源的深度学习加速器框架中得到验证，结果显示在保持精度的前提下，典型卷积层的计算能效提升了1.14-1.3倍。
