algorithm - 是否有用于生成带限锯齿的恒定时间算法？

Question

我正在研究GPU合成音频的可行性，其中每个线程呈现一个样本这对可以使用什么样的算法设置了一些有趣的限制——任何引用以前一组样本的算法都不能以这种方式实现。
过滤就是其中一种算法。带通、低通或高通-所有这些都需要查看最后生成的几个样本，以便计算结果。这无法完成，因为这些样本尚未生成。
这使得合成带限波形变得困难一种方法是利用傅立叶级数对部分进行加法合成。然而，这是在O（n）时间运行的，并且在GPU上特别慢，以至于失去了并行性的增益如果有一个在0（1）时间运行的算法，这将消除分支，并且在处理声音范围时速度将高达1000倍。
我特别要找的是锯齿状的DSF。我一直在试图用手工计算出傅里叶级数的简化，但那真的，真的很难主要是因为它涉及调和数，也就是黎曼-泽塔函数唯一的奇点。
恒定时间算法可以实现吗？如果不是，能证明不是吗？

Answer 1

过滤就是其中一种算法。带通、低通或高通-所有这些都需要查看最后生成的几个样本，以便计算结果。这无法完成，因为这些样本尚未生成。
那是不对的。IIR过滤器确实需要以前的结果，但是FIR过滤器只需要以前的输入；这对于GPU设计的任务来说是非常典型的，所以让每个处理核心访问（比如说64个输入样本来产生一个输出样本）不太可能是个问题——事实上，NVIDIA和AMD使用的缓存架构那。
恒定时间算法可以实现吗如果不是，能证明不是吗？
它是！在两个方面：
如上所述，fir滤波器只需要不可变输入的多个样本，因此它们可以很好地并行化，并且
即使你需要先计算你的输入，并且想把它并行化（我看不出原因——生成锯齿不是CPU受限，而是内存带宽受限），每个核都可以简单地计算最后N个样本——当然，有N-1个冗余操作，但只要你的核数远远大于N，你仍然会更快，每个核心都会有固定的运行时间。
对你的方法的评论：
我正在研究gpu合成音频的可行性，其中每个线程呈现一个样本。
从更高的角度来看，这听起来太细了我的意思是，假设你有3000个流处理器（高端消费者GPU）假设你有44.1kHz的采样率，假设每个处理器只做一个采样，让它们都运行一次只会给你1/14.7秒的音频（mono）。那你就得继续下一部分的音频了。
换句话说：肯定会有比处理器多得多的样本。在这些情况下，让一个处理器处理一系列样本通常会更有效；例如，如果您想要生成30秒的音频，则为1.323ms（amples）。简单地将问题分成3000个块，每个处理器一个，给每个处理器44100*30/3000=441个他们应该处理的样本，再加上64个“历史”样本，在第一个“自己的”样本仍然很容易放入本地内存之前。
还有一个想法：
我来自软件定义的无线电背景，那里通常每秒有数百万个采样，而不是几千赫的采样率，实时（即处理速度>采样率）。尽管如此，在gpu上进行计算只会为cpu更密集的任务付出代价，因为在与gpu交换数据时会有很大的开销，而且现在的cpu速度非常快。因此，对于相对简单的问题，在GPU上做事情可能永远不会比在CPU上优化它们更快；如果必须同时处理大量样本或流，事情当然会看起来不同对于更细粒度的任务，填充缓冲区、将其移动到gpu并将结果缓冲区返回到软件中的问题通常会扼杀优势。
因此，我想向您提出挑战：下载GNU Radio live DVD，将其刻录到DVD或将其写入U盘（您不妨在虚拟机中运行它，但如果您不知道如何优化虚拟机，这当然会降低性能；真的-从实时媒体中尝试），运行

volk_profile

让 VOLK library测试哪些算法在您的特定机器上最有效，然后启动

gnuradio-companion

然后，打开以下两个信号处理流程图：
"classical FIR"： 这个fir滤波器的单线程实现在我的cpu上产生大约50个采样/秒。
FIR Filter implemented with the FFT, running on 4 threads： 此实现达到160MSamples/s（！！）就在我的CPU上。
当然，借助于GPU上的FFT，我可以更快，但这里的问题是：即使使用“简单”的FIR滤波器，我也可以用一个CPU核，从我的机器中获取50兆的样本——也就是说，以44.1kHz的音频采样率，每秒我可以处理大约19分钟的音频不复制主机RAM。没有GPU冷却器启动。这可能真的不值得进一步优化。如果你优化并采用fft滤波方法：160ms/s意味着每秒钟大约一小时的音频处理，包括锯齿波的产生。