比较算法成本的正确方法
Correct way to compare algorithm cost
比较信号处理算法所需的计算资源的正确方法是什么？
我说的是具有误差范围与资源与响应延迟折衷的信号处理算法。
在通过算法实现实现错误边界和响应延迟后，我正在尝试比较其效率。
目前我正在对不同的算法进行基准测试，方法是向它们提供相同的信号并使用 perf 获取 amd64 上使用的 task-clocks / mseg，但那是与架构无关。
业界使用 MFLOPS/Hz 来比较处理器，但我如何为特定实现包含内存（可能还有线程）开销？
什么是正确的学术测量可以说：
Algorithm X is N times better than Y to achieve P with Q bounds.
编辑： 对于上下文，我正在处理的信号处理算法是迭代算法，其阶跃函数可以受 O(1) 的约束。所以BigO在这里似乎没有用。
这个问题有多个正确答案。你至少应该考虑这两个：
- 计算机科学使用 O notation – 通常用于衡量处理要求，但它只是数学，也可以应用于内存。
- 正如您所做的那样，基准测试是测试实施的正确方法。但是您想要进行多变量分析（即在不同的平台、输入大小等上进行测试）。
平台原则上应该只是一个常数因素。但在实践中，常数因子可能是相关的。
准确的性能度量与体系结构或实现无关。不同的 DSP 计算平台不仅会有不同的绝对性能数字（MHz/GHz），而且 MAC 或触发器延迟与调度比率和内存延迟与带宽比率的比率不同，以及许多其他性能危害（缓存替换与流策略等）和效率（SMP 或矢量调度等）
在古代（VAX、FP 系统、56000 或更早版本）原始乘法或 MAC 计数优于所有其他性能限制，因此这成为事实上的成本指标。这不再总是现代流水线短向量 FPU 多处理器的主导因素，现在甚至在玩具中也很常见。
一种可能性是猜测您的算法最有可能针对的平台，并对其进行测量（更可能类似于基于 ARM 的移动 phone 或 Raspberry Pi 系统而不是 AMD恕我直言，甚至可能是 OpenCL GPU）。
另一种可能性是 运行 在学术 CPU 模拟器（RISC V？）上，您可以在其中打开详细的性能计数器（调度的每种类型的操作、内存流量、寄存器重用危险、等）这将比任何 AMD 台式机准确得多，其中 OS 任务切换、TLB/MMU 未命中以及缓存初始化和流量的变化可能导致任何性能测量中的各种未知变化。
比较信号处理算法所需的计算资源的正确方法是什么？
我说的是具有误差范围与资源与响应延迟折衷的信号处理算法。
在通过算法实现实现错误边界和响应延迟后，我正在尝试比较其效率。
目前我正在对不同的算法进行基准测试，方法是向它们提供相同的信号并使用 perf 获取 amd64 上使用的 task-clocks / mseg，但那是与架构无关。
业界使用 MFLOPS/Hz 来比较处理器，但我如何为特定实现包含内存（可能还有线程）开销？
什么是正确的学术测量可以说：
Algorithm X is N times better than Y to achieve P with Q bounds.
编辑： 对于上下文，我正在处理的信号处理算法是迭代算法，其阶跃函数可以受 O(1) 的约束。所以BigO在这里似乎没有用。
这个问题有多个正确答案。你至少应该考虑这两个：
- 计算机科学使用 O notation – 通常用于衡量处理要求，但它只是数学，也可以应用于内存。
- 正如您所做的那样，基准测试是测试实施的正确方法。但是您想要进行多变量分析（即在不同的平台、输入大小等上进行测试）。
平台原则上应该只是一个常数因素。但在实践中，常数因子可能是相关的。
准确的性能度量与体系结构或实现无关。不同的 DSP 计算平台不仅会有不同的绝对性能数字（MHz/GHz），而且 MAC 或触发器延迟与调度比率和内存延迟与带宽比率的比率不同，以及许多其他性能危害（缓存替换与流策略等）和效率（SMP 或矢量调度等）
在古代（VAX、FP 系统、56000 或更早版本）原始乘法或 MAC 计数优于所有其他性能限制，因此这成为事实上的成本指标。这不再总是现代流水线短向量 FPU 多处理器的主导因素，现在甚至在玩具中也很常见。
一种可能性是猜测您的算法最有可能针对的平台，并对其进行测量（更可能类似于基于 ARM 的移动 phone 或 Raspberry Pi 系统而不是 AMD恕我直言，甚至可能是 OpenCL GPU）。
另一种可能性是 运行 在学术 CPU 模拟器（RISC V？）上，您可以在其中打开详细的性能计数器（调度的每种类型的操作、内存流量、寄存器重用危险、等）这将比任何 AMD 台式机准确得多，其中 OS 任务切换、TLB/MMU 未命中以及缓存初始化和流量的变化可能导致任何性能测量中的各种未知变化。