Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

想象一下，你正在尝试清理一段充满噪音的录音，或者是在制造一个需要对环境做出即时反应的机器人。在两种情况下，你都需要一个数字“滤波器”来将好的声音与坏的声音分离。完成这项工作的最强大工具被称为递归滤波器（recursive filters）。把它们想象成一个神奇的回声室：为了确定下一个声音应该是怎样的，滤波器不仅会观察当前的声音，还会观察它在前一瞬间所产生的声音。这种“向后看”的做法使得它们极其高效，只需极少的计算能力就能完成复杂的任务。然而，这其中有一个陷阱：因为每一个新声音都依赖于前一个声音，滤波器必须一步一个脚印地工作，就像一个人走在长长的走廊里。这造成了一个瓶颈，当需要处理海量数据（如高清视频或实时广播）时，会拖慢整体速度。

几十年来，科学家们一直试图通过让更多计算机参与协作来解决这个问题。挑战在于，如果你将工作分配给多台计算机，它们会变得混乱，因为它们都在等待前一个人完成他的步骤，然后才能开始自己的步骤。这就像一场接力赛，即使跑者们站在不同的赛道上，他们也会因为等待接力棒而停滞不前。这篇论文正是在解决这个精确的问题。它采用了一种已经在单台超快计算机芯片上被证明有效的巧妙数学技巧，并将其扩展到现代多核计算机和强大的图形处理器（GPU）上。作者发现，他们可以让这些计算机协同工作而无需等待，将原本缓慢的单列队变成了高速的多车道公路，实现了这种数学运算此前被认为无法达到的速度。

接力赛问题与神奇技巧

为了理解这一突破，让我们看看这些滤波器通常是如何工作的。想象一排人正在传递一条信息。每个人都必须等待前面的人低声说完信息，然后才能加入自己的部分并传递下去。这就是“递归”的部分。如果你有一条很长的链条，信息传到终点就需要很长时间。

本文的作者已经找到了一种方法，可以将一条长链拆分为更小的块（blocks），从而实现更快处理。但当他们尝试同时将这些块交给多个计算机（比如一个团队）时，一个新的问题出现了：前一个块的结尾是下一个块的起点。如果你把块 A 交给工人 1，把块 B 交给工人 2，那么工人 2 就必须等待工人 1 完成块 A 之后才能开始处理块 B。结果，整个团队实际上还是在逐个进行，这让组建团队失去了意义。

该论文的主要发现是一种被称为**叠加（superposition）**的数学“魔法技巧”。与其等待前一个块的答案，工人会先猜测如果从零开始，答案“将会”是什么（一个“零状态”猜测）。他们立即进行这项计算。然后，他们会等待来自前一个工人的“实际”起始数值到达。一旦数值到达，他们只需在他们的猜测基础上加上一个微小的“修正值”即可。这就像一位厨师根据食谱开始煮汤，即便假设现在还没有食材一样。当送菜卡车终于把真正的蔬菜送到时，厨师只需把它们加进去并搅拌即可。汤几乎是瞬间就准备好了，因为最繁重的烹饪过程已经在并行状态下完成了。

两种不同的运行方式

论文展示了这种魔法技巧可以根据你的需求以两种完全不同的方式运行。

1. 实时流处理（流水线模式）
如果你正在处理实时数据，比如广播，你不能等到整批数据处理完后再播放下一秒的音频。你需要数据按照进入的顺序依次输出（先进先出）。

• 解决方案： 作者为多核 CPU 构建了一个“波前流水线（wavefront pipeline）”。想象一条装配线，不同的工人同时处理同一首歌的不同阶段。工人 1 负责清理低音，工人 2 负责修复人声，工人 3 负责添加回声。一旦工人 1 完成了一块内容，他们就会将其传递给工人 2，工人 2 再传递给工人 3。
• 结果： 在一台拥有六个强大核心的现代计算机上，这种方法对于一个复杂的 16 阶滤波器实现了 2.4 Gigasamples 每秒 的处理速度。这几乎比使用单个核心快了 4 倍。有趣的是，他们发现将较慢的“效率核心”混入其中反而会拖慢流水线的速度，这证明了对于这项特定任务，少数几个快速的工人比许多缓慢的工人更好。

2. 批处理（工厂模式）
如果你正在处理一个巨大的记录文件（如电影或数据库），你并不那么在意顺序，你在意的是原始速度。你可以一次性处理整个文件。

• 解决方案： 他们使用了强大的图形处理器（GPU），这类设备拥有数以千计的小型工作单元。他们使用了一种**解耦回溯（decoupled lookback）**技术。想象一个工厂，每个工人立即计算他们负责的部分。如果一个工人需要来自前一站的零件，他们不会停下来等待；他们只是查看一个“状态板”来看看前一站是否已经完成。如果完成了，他们就取走零件；如果没有，他们会继续处理其他事情，直到零件准备就绪。
• 结果： 这种方法极其迅速。在 NVIDIA RTX 3060 显卡上，系统对于单个滤波器部分的处理速度达到了 38.2 Gigasamples 每秒。这达到了硬件理论最大速度（“内存带宽上限”）的 85%。

为什么这很重要以及它超越了什么

作者不仅提高了速度，还证明了他们的方法比旧方法更可靠。

• “直接形式（Direct Form）”的失败： 有一种旧方法叫做“直接形式”，它试图通过一个巨大的步骤来完成数学运算。论文指出，对于复杂的滤波器（如 16 阶滤波器），这种旧方法会失效。数值会变得极其混乱，导致计算机产生错误的结果甚至崩溃。本文使用的这种新的“级联（cascaded）”方法即使在如此高水平的情况下也能保持准确。
• 击败竞争对手： 他们将新的 GPU 代码与现有的最强并行滤波引擎进行了对比。在测试的所有滤波器阶数中，他们的方法都更快。
• 速度的代价： 论文还仔细测量了这种速度带来的“代价”。他们发现，在较新的、更快的芯片（如 RTX 3060）上，“屏障（barriers）”（即工人检查自己是否可以继续进行的检查过程）是非常廉价的，因此可以使用更复杂、更快速的方法。而在较旧的芯片上，这些检查非常昂贵，因此必须使用更简单的方法。这有助于工程师了解如何针对不同硬件来调优他们的软件。

总结

这篇论文将一个困难的、顺序性的数学问题变成了一场并行的盛宴。通过使用一种巧妙的“猜测并修正”策略，他们让计算机能够协同工作而不会互相等待。

• 对于实时流处理，他们构建了一个在标准计算机上运行速度快了 3.95 倍 的流水线。
• 对于批处理，他们构建了一个处理速度达 38.2 Gigasamples 每秒 的 GPU 引擎，这是一个巨大的飞跃。
• 至关重要的是，他们证明了这种方法不仅更快，而且效果更好，在旧方法失效的地方依然能保持准确。

作者已将他们的代码作为开源库发布，这意味着任何人现在都可以使用这些超快速滤波器来构建更好的音频工具、更清晰的视频和更智能的机器人。他们有效地将一个“顺序”瓶颈转变为了一条“并行”超级公路，证明了即使是最顽固的数学问题，也可以通过让计算机团队同步协作来解决。