我认为（一阶）正确的做法是查看算法中所需的触发器与字节的比率，我称之为$\beta$. 让$F_{\mathrm{max}}$是处理器的最大翻转率，并且$B_{\mathrm{max}}$最大带宽。如果$\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$，那么算法将受到带宽限制。如果$B_{\mathrm{max}}\beta > F_{\mathrm{max}}$, 该算法是有限的。

我认为计算内存访问是强制性的，但我们也应该考虑：

• 需要多少本地内存

• 我们有多少可能的并发

然后你就可以开始分析现代硬件的算法了。

我不明白为什么必须成为“赢家”；这不是一个零和游戏，翻牌数和内存访问必须淹没另一个。你可以教他们两个，我认为他们都有自己的用途。毕竟，很难说你的$O(N^4)$算法与$O(N)$内存访问一定会比你的更快$O(N \log N)$算法与$O(N^2)$访问。这完全取决于不同部分的相对成本（我们在这些分析中总是忽略的讨厌的先决条件！）。

从更广泛的角度来看，我认为对算法性能的分析应该是“包罗万象”的。如果我们教人们成为真正的 HPC 开发人员和用户，那么他们需要了解在现实世界中编程的成本是多少。我们的抽象分析模型没有考虑程序员的时间。我们应该考虑“解决问题的总时间”，而不仅仅是失败次数和算法效率。除非你计划运行几百万次计算，否则花三到四个程序员的时间来重写一个例程，从而为每个作业节省一秒钟的计算机时间是没有意义的。同样，为节省一两个小时的计算时间而进行的几天投资很快就会得到回报。那个新颖的算法可能是惊人的，

正如其他人指出的那样，答案当然取决于瓶颈是 CPU 还是内存带宽。对于在一些任意大小的数据集上工作的许多算法，瓶颈通常是内存带宽，因为数据集不适合 CPU 缓存。

此外，Knuth 提到内存访问分析更有可能经受住时间的考验，大概是因为与现代 CPU 管道和分支预测的复杂性相比，它相对简单（即使考虑到缓存友好性）。

在分析 BDD 时， Knuth 在 TAOCP 第 4A 卷中使用了术语gigamems。我不确定他是否在以前的卷中使用它。他在 2010 年的年度圣诞树讲座中就经受住了时间的考验发表了上述评论。

有趣的是，You're Doing It Wrong表明，即使基于内存操作分析性能也并不总是那么简单，因为如果数据不能一次全部放入物理 RAM，就会出现诸如 VM 压力之类的因素。

您如何确定算法的成本取决于您工作的科学计算“级别”以及您考虑的（狭义或广义）问题类别。

如果您考虑缓存优化，这显然与诸如 BLAS 和类似库之类的数值线性代数包的实现更相关。所以这属于低级优化，如果你有一个针对特定问题的固定算法并且对​​输入有足够的约束就可以了。例如，如果矩阵被保证足够稀疏，缓存优化可能与快速实现共轭梯度迭代有关。

另一方面，问题的类别越广泛，您对实际计算的预测就越少（例如，您不知道您的 CG 实现的输入矩阵到底有多稀疏）。您的程序应该运行的机器类别越广泛，您对缓存架构的预测就越少。

此外，在更高层次的科学计算上，改变问题结构可能更相关。例如，如果您花时间为线性方程组寻找一个好的预条件子，这种优化通常优于任何低级优化，因为迭代次数大大减少。

总而言之，缓存优化只有在没有任何东西可以通过并行性和渐近 FLOP 数减少来优化的情况下才有用。

我认为调整理论计算机科学的立场是明智的：最终，提高算法的渐近复杂度比对一些现有代码行的微优化有更多的回报。因此，FLOPs 计数仍然是首选。