GPU Gems 3 · Chapter 35. Fast Virus Signature Matching on the GPU

先问：为什么要先做一个很快的筛子

网络设备面对的不是一份整齐的文件，而是一条持续流入、大小不一、可能跨越多个对象的字节流。每一段数据都可能包含恶意模式；如果每次都让最慢的完整检查从头读到尾，吞吐很快就会被拖垮。

本章把工作拆成两层：先用大量轻量线程找出“看起来像”的位置，再把少量候选交给更擅长复杂判断的处理器。这样没有候选时可以快速通过，有候选时也仍然保留完整检查的准确性。

1. 把完整签名匹配拆成候选过滤和最终验证

原始库以固定字符签名为第一步：GPU 负责规则短、访存规律的候选筛选，CPU 负责完整签名验证和对象归属。正则表达式、解压、文件类型判断和最终报告并不自动变成 GPU 工作；它们仍属于应用或 CPU 侧的可变逻辑。

GPU 与网络处理器有相似之处：都需要快速内存、用很多线程隐藏 DRAM 延迟，并持续搬运大批量数据。但相似不意味着所有阶段都适合并行；“候选过滤”才是本章刻意挑出的规则核心。

2. 选择并行方向：一个包内，还是多个包之间

intrapacket 让一个长对象内部的相邻窗口并行；interpacket 则让多个对象同时前进。实际库把数据先填满 buffer，再由 GPU 忽略对象边界地扫描连续字节，最后由 CPU 使用对象描述把候选归回文件。这个设计避免 GPU 在线程中维护复杂的文件状态。

两种布局的共同要求是：线程必须能独立读固定数量的字节，输出也必须能写到确定位置。于是下一步不是把完整签名复制给每个线程，而是为每个窗口准备一个很小的索引和比较值。

3. 用 2-byte key 把签名数据库压成一次查表

对每个固定字符签名，数据库取一对连续字节作为 key，并把它前面的四个字节存成 tag。GPU 线程读取输入中的一个 2-byte window，用这个 key 索引表，再把表里的 tag 与输入窗口之前的四个字节比较。两个比较都匹配时，只说明这里值得 CPU 进一步检查。

可以把线程的主循环压缩成下面的伪代码；关键不是语言，而是每个线程读取固定窗口、做一次索引和一次短比较：

for each adjacent pair at offset i:
  key = input[i : i + 2]
  tag = table[key]
  if input[i - 4 : i] matches tag:
    output[2 * i] = signatureId

这个表故意把“快”放在第一位：每个 entry 原始设计至多对应一个签名，避免 GPU 为每个窗口追逐复杂链表。代价是签名集合、key 唯一性和内存容量都成为明确的可扩展性边界。

4. 重叠窗口与结果缓冲区决定正确性成本

线程 A 读取 [i, i + 1]，线程 B 读取 [i + 1, i + 2]，这种重叠让每个连续 2-byte pair 都有机会成为 key。若签名的关键字节跨越输入 buffer 末尾，应用必须复制足够的前置数据到下一个 buffer；复制量至少要覆盖最长签名所需的上下文。

命中时 GPU 不写入整条签名，而是在输出 buffer 的相对偏移 2i 写入两字节 identifier。没有命中的位置保持空值，CPU 之后扫描这些稀疏结果，再根据对象描述把 offset 转成文件或数据包中的位置。

动手走一遍：一个 buffer 如何完成过滤并回到对象结果

5. 用多 buffer 把两个处理器变成一条流水线

如果 CPU 填一块 buffer、等待 GPU、再读回结果，GPU 工作时 CPU 可能闲着，CPU 验证时 GPU 也可能闲着。轮转多个 buffer 后，CPU 可以填充下一块，GPU 扫描当前块，CPU 同时验证上一块；只有结果 buffer 的回读在原始实现中仍然是串行点。

轮流使用多块输入/输出 buffer，让 CPU 填充、GPU 过滤和 CPU 验证在不同 buffer 上重叠执行，可以隐藏传输与执行延迟。

这种管线的收益依赖输入分布。没有 tag 命中时，GPU 可以连续处理大块数据，原文测量中最高获得 27 倍于 CPU 参考路径的加速；命中率升高后，结果回读与 CPU 验证会吞掉收益。这里的数字属于特定旧硬件和测试条件，不应当当成今天所有 GPU 的固定承诺。

6. 用 GPU Virus Filter Lab 观察吞吐如何被候选拖慢

先保持 30,000 signatures、8 MB buffer 和 rotating buffers，把命中率从 0% 拉到 50%；再切换 full verification、block threshold 和 object threshold。你应该看到：过滤阶段仍然规则，但 candidate ids、结果搬运和 CPU checks 会随着命中密度上升。

当数据库切到 120,000 时，Lab 会显式显示 table overflow。这个状态不是“GPU 变慢一点”这么简单，而是告诉你原始单 key 表的表示能力已被超过：必须引入多候选结构、分层查表或让 CPU 承担更多消歧工作。

小结

• GPU 适合做规则、短路径的候选过滤，CPU 仍负责完整签名验证和对象报告。
• intrapacket 与 interpacket 是两种数据并行布局，连续 buffer 让 GPU 可以暂时忽略对象边界。
• 2-byte key 索引约 64,000-entry 表，tag comparison 用四个前置字节快速排除多数窗口。
• 重叠窗口和跨 buffer 前缀复制防止签名在边界处漏检；命中结果写入 2i 的稀疏输出位置。
• 多 buffer 轮转能隐藏延迟，但 false positive 密集时回读和 CPU 验证仍会成为瓶颈。

练习