9

我需要实时绘制音频峰值表。每秒最少 44100 个样本乘以最少 40 个流。每个缓冲区介于 64 到 1024 个样本之间。我需要从每个缓冲区中获取最大绝对值。（然后将它们通过一种低通滤波器馈入并以大约 20 毫秒的间隔绘制。）

for(int i = 0; i < numSamples; i++)
{ 
      absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}

我现在就是这样做的。我想做得更快。缓冲区的浮点数在 -1 到 1 范围内，因此是 fabs。

问题，是否有一些棘手的 comp-sci quicksort-esque 方法可以更快地做到这一点？

如果做不到这一点，浮点数的无分支 ABS 和 MAX 函数，它们存在吗？

编辑：主要平台是 Linux/gcc，但计划了一个 windows 端口（可能与 mingw）。

编辑，第二个：
我接受了一个人，因为关于实际算法结构的一点是问题的核心。
我将尝试将循环展开到四个，将符号位归零，然后使用 SSE（maxps 指令）获得最大值，看看是否不会剥皮。感谢您的建议，我投票赞成你们中的一些人，作为亚军。:)

4

7 回答 7

5

对于 IEEE 浮点数，fabs 和比较都非常快（例如，原则上单整数运算快）。

如果编译器没有内联这两个操作，那么要么戳它直到它完成，或者找到你的架构的实现并自己内联它。

您可能会从正IEEE 浮点数与具有相同位模式的整数的顺序相同的事实中得到一些信息。那是，

f > g   iff   *(int*)&f > *(int*)&g

因此，一旦您完成了制造，我认为 int 的无分支最大值也适用于 float（当然假设它们的大小相同）。有一个解释为什么在这里工作：http ://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm 。但是你的编译器已经知道这一切，你的 CPU 也知道，所以它可能没有任何区别。

没有比复杂性更快的方法。您的算法已经是 O(n)，您无法击败它并仍然查看每个样本。

我猜您的处理器的 SIMD（即 Intel 上的 SSE2）中可能有一些东西可以通过每个时钟周期处理比您的代码更多的数据来提供帮助。但我不知道是什么。如果有，那么它很可能会快几倍。

您可能可以在多核 CPU 上进行并行化，尤其是因为您要处理 40 个独立的流。这将是最好的几个因素更快。“只需”启动适当数量的额外线程，将它们之间的工作分开，并使用最轻的原语来指示它们何时全部完成（可能是线程屏障）。我不太清楚您是在绘制所有 40 个流的最大值，还是分别绘制每个流的最大值，所以除了确保将结果传递到下一阶段之外，您实际上可能不需要同步工作线程没有数据损坏。

可能值得看一下反汇编，看看编译器展开了多少循环。尝试再展开它，看看是否有什么不同。

另一件要考虑的事情是你得到了多少缓存未命中，以及是否可以通过给缓存一些线索来减少这个数字，以便它可以提前加载正确的页面。但是我没有这方面的经验，我不会抱太大希望。__builtin_prefetch 是 gcc 上的魔法咒语，我猜第一个实验类似于“在进入该块的循环之前预取下一个块的开头”。

您目前处于所需速度的百分之几？还是“尽可能快”的情况？

于 2009-05-03T18:30:59.300 回答
2

要尝试的事情：

  • fabs() 可能不是内联函数。
  • 特殊的组装说明可能会有所帮助。在 Intel 上，SSE 有一条指令可以一次计算最多四个浮点数。
  • 如果做不到这一点，IEEE 754 规范是这样的，如果 a 和 b是非负浮点数，则 a < b 等效于 *(int *)&a < *(int *)&b。此外，对于任何 a，您都可以通过翻转 MSB 从 a 计算 -a。总之，这些属性可能会启用一些小技巧。
  • 你真的需要每个样本的最大值吗？也许最大值可能不止一次出现，从而打开了不检查每个输入的可能性。
  • 你能以流方式计算最大值吗？
于 2009-05-03T18:34:13.537 回答
2

http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms上记录了一个无分支晶圆厂

另请注意，最新版本的 GCC 将fabs使用 MMX 指令为您内联无分支。还有fminand fmax，但 GCC 不会内联那些（你会得到一个call fmin）。

于 2009-05-03T18:35:43.767 回答
1

你可能想看看Eigen。

它是一个 C++ 模板库，它使用SSE（2 和更高版本）和 AltiVec 指令集，并优雅地回退到非矢量化代码。

快速地。（见基准）。
表达式模板允许在适当的时候智能地删除临时变量并启用惰性求值——Eigen 会自动处理这一点并在大多数情况下也处理别名。
对 SSE（2 和更高版本）和 AltiVec 指令集执行显式矢量化，并优雅地回退到非矢量化代码。表达式模板允许对整个表达式全局执行这些优化。
使用固定大小的对象，可以避免动态内存分配，并且在有意义时展开循环。
对于大型矩阵，需要特别注意缓存友好性。

于 2009-05-04T03:54:23.627 回答
0

Easy optimizations I see:

  • translate the loop to a pointer arithmetic version (assuming that your compiler don't see this)
  • the IEEE 754 standard defines its representation as sign-magnitude. So, setting the most-significant bit to 0 will be the same as calling fabs(). Maybe this function already uses this trick.
于 2009-05-03T18:47:16.297 回答
0

出于您的目的，您可以将其平方而不是取绝对值；正如数学上的 |a| < |b| 如果 a^2 < b^2 反之亦然。在某些机器上乘法可能比 fabs() 更快（？），我不知道。

于 2009-05-04T06:29:27.157 回答
0

用另一个问题回答一个问题并不完全是回答，但是嘿......我也不是 C++ 开发人员。

既然你是在 C++ 中开发这个并且你正在做 dsp，你不能连接到 matlab 或 octave（它是开源的）到你的数学并得到结果吗？

在这些软件中已经实现了一些功能（如 conv、fft、ifft、fir 和绘图实用程序功能，如 freqz、stem、graph、plot、mesh 等）。我在 Photoshop 中查看了一个名为 MATLAB 的大文件夹……其中包含一些从应用程序获取调用的 .m 文件，将其发送到动态 matlab，然后将结果返回给应用程序。

希望能帮助到你。

于 2009-05-03T18:30:31.923 回答