algorithm - 最佳矩阵转置的缓存未命中率是多少？

Question

如果我有一个 M x N 矩阵和一个大小为 K 的 L1 缓存，则最佳矩阵转置的缓存未命中率是多少。显然，我正在寻找的是 M 和 N(可能还有 K，尽管这可能太复杂)的函数，而不是一个具体数量。

我问是因为我有很多矩阵数据必须在两个方向上进行处理，我希望根据经验法则知道什么时候在内存中保留原始数据和转置是值得的。

Answer 1

你没有说你有什么缓存类型，它是直接映射的吗？ N路集合关联？假设一个 N 路集合关联(是的，你确实需要缓存的所有细节，这取决于你的特定 CPU 架构)并假设一个特定的矩阵排序，例如column-major 那么你基本上会有冷未命中 M*N/C，其中 C 是缓存行大小(这取决于 CPU，但通常是 8 个双倍 :))。

然后您将对目标矩阵进行跨步访问，除非矩阵足够小以完全适合 L1，否则您可以假设 M*N 冷未命中的最坏情况，例如大小为 32kB 的 L1 可以容纳 4000 个 double ，即大小为 ~63*63 的矩阵。

因此，我们会考虑转置的最坏情况 (M*N/C + M*N) L1 总失误。

一个想法是做翻转矩阵排序的技巧，例如从列优先到行优先，而不是物理移动它，按转置方式访问它。如果您有正确的矩阵实现，您可以在相同数据上翻转矩阵排序，那么这是零成本操作。

虽然真正昂贵的预取永远不会在 L1 中，但在 LLC(最后一级缓存)中，即使你得到 L1 未命中，它仍然是一个便宜的未命中，因为它将从 L2 加载。总之，除非您拥有 objective-c PU 架构的所有微小细节，否则很难进行计算。