非确定有限状态机（NFA）在网络入侵检测、正则表达式匹配、字符串搜索等场景中应用广泛。传统基于 CPU 或 GPU 的 NFA 评估面临严重的数据搬移瓶颈 —— 每次状态转移都需要从内存读取转移函数并将结果写回，功耗随状态规模线性增长。GLVLSI 2025 发表的论文提出了一种全数字存算一体（Compute-in-Memory，CIM）架构，将 NFA 转移函数直接映射到存算阵列中，在源端完成状态转移计算，从而将能耗降低至 1.27 fJ/B/transition，较传统方案提升一个数量级。

存算一体微架构设计

该架构的核心创新在于将 NFA 的每个转移（input symbol, current state, next state）映射为存算阵列中的一列。假设 NFA 的转移函数是稀疏的 —— 即实际使用的转移数量远低于理论最大值 —— 这种稀疏特性恰好契合存算阵列的并行处理能力。初始化阶段将所有转移写入 CIM 硬件，每个列单元存储一个完整的转移三元组。

评估过程采用广播式数据流：输入符号与当前状态位图同时广播至所有列单元。各列独立判断自身存储的转移是否应当激活 —— 即当前状态位图中对应位是否为 1，且输入符号是否匹配该转移的触发条件。激活的转移经多周期迭代后生成下一轮状态位图。这种设计将状态转移的计算嵌入到存储阵列内部，大幅削减了数据搬移次数。

多符号编码与布隆过滤器优化

原始架构每个输入符号需要至少一个处理周期，当激活转移数量较多时延迟进一步增加。论文提出多符号编码技术将多个原始符号合并为 “宏符号”，使单周期可处理多个输入。例如将字符 a 和 b 合并为 ab 后，NFA 的吞吐率可翻倍。该技巧的适用条件是 NFA 实现对符号位宽不敏感，且合并后的符号集规模仍在硬件可表示范围内。

针对网络流量监控场景，论文观察到大多数输入包并不产生匹配 ——NFA 大部分时间停留在初始状态。基于此观察，作者引入布隆过滤器进行预处理过滤。当 NFA 处于初始状态时，输入符号先经过布隆过滤器快速判断是否会触发任何从初始状态出发的转移。布隆过滤器在 NFA 转移函数变更时构建：遍历所有当前状态等于初始状态的转移，对每个转移的输入符号计算哈希值并映射到 N 个 bit 位进行置位。检测时若任意对应位未置位，则该符号必然不触发转移，可直接跳过后续 CIM 评估。实验表明该优化可过滤掉绝大多数无效输入，显著降低平均能耗。

工程落地关键参数

将此类 CIM NFA 加速器集成到实际系统时，需关注以下工程参数。首先是转移存储密度 —— 该架构假设转移函数稀疏，若实际 NFA 状态数接近饱和（如数万个状态、全连接转移），列宽将急剧增长，需评估片上 SRAM 是否足以容纳完整转移表。建议在部署前统计目标 NFA 的稀疏度，确保实际转移数与存储容量匹配。

其次是时序收敛边界。输入符号广播路径与列内比较逻辑的延迟决定了最高工作频率。论文原型在标准单元库下可达成 800MHz 左右的工作频率，但实际芯片需根据工艺角（corner）进行时序 sign-off。建议在系统级验证阶段构建时序裕量模型，覆盖从最佳到最差工艺角的完整场景。

功耗监控应聚焦于两个关键指标：每字节转移能耗（fJ/B/transition）和有效吞吐量（symbols/s）。前者反映硬件能效基线，后者受布隆过滤器命中率和激活转移分布影响。生产环境建议采集每秒处理符号数与平均能耗的比率，当该比率下降超过 20% 时触发告警，排查是否存在 NFA 转移函数复杂度上升或布隆过滤器失配。

与现有方案对比

从能耗角度审视，1.27 fJ/B/transition 的数字 CIM 方案显著优于基于内容寻址存储器（CAM）的 automata 加速器 CAMA，后者在类似工艺节点下的能耗约为 5 至 10 fJ/B/transition。优势来源于全数字实现避免了模拟存算单元的静态功耗，同时 SRAM 单元的密度更高，单位面积可容纳更多并行比较电路。但需注意数字 CIM 的转移存储需要额外的编解码逻辑，而 CAM 方案则直接利用 CAM 的并行匹配能力，两者在不同 NFA 规模下的适用性各有取舍。

对于网络入侵检测系统（IDS）类应用，如 Snort 规则集的加速，该架构的布隆过滤器优化尤为契合 —— 实际网络流量中匹配事件本身是小概率事件，过滤机制可将大部分无效包直接丢弃，仅对可能触发转移的包进行完整 CIM 评估。建议在系统集成时将布隆过滤器实现为可配置模块，允许根据当前 NFA 的初始状态转移分布动态调整过滤器参数。

总结

数字存算一体架构为 NFA 评估提供了一条从算法到硬件的协同优化路径。通过将转移函数嵌入存储阵列内部消除数据搬移，结合多符号编码提升吞吐、利用布隆过滤器过滤无效输入，该架构在保持全数字可编程性的同时实现了超低能耗。工程落地时需重点评估 NFA 稀疏度是否满足存储约束、时序收敛边界是否满足性能需求，并建立功耗与吞吐的联合监控体系。

资料来源：Dangling Pointers，《A 1.27 fJ/B/transition Digital Compute-in-Memory Architecture for Non-Deterministic Finite Automata Evaluation》, GLVLSI 2025