如果我有一个MxN矩阵和一个大小为 K 的 L1 缓存，那么最佳矩阵转置的缓存未命中率是多少。显然，我正在寻找与M和N（可能K，尽管这可能太复杂）的函数而不是特定数字的东西。
我之所以问，是因为我有很多矩阵数据必须在两个方向上进行处理，并且我希望根据经验法则知道何时将原始数据和转置都保留在内存中是值得的。
user334911
问问题
1564 次
1 回答
2
你还没有说你拥有的缓存类型，它是直接映射的吗？N路集关联？假设一个 N 路集合关联（是的，您确实需要取决于您的特定 CPU 架构的缓存的所有详细信息）并假设一个特定的矩阵排序，例如列优先，那么您基本上会遇到冷缺失 M*N/C其中 C 是高速缓存行大小（取决于 CPU，但通常是 8 倍 :)）。
然后，您将对目标矩阵进行跨步访问，除非矩阵足够小以完全适合 L1，否则您可以假设 M*N 冷缺失的最坏情况，例如大小为 32kB 的 L1，您可以容纳 4000 个双打，即大小为 ~63*63 的矩阵。
因此，我们将查看转置的最坏情况 (M*N/C + M*N) 总 L1 未命中。
一个想法是做翻转矩阵排序的技巧，例如从列优先到行优先，而不是物理移动它，而是将它作为 transposed 访问。如果您有正确的矩阵实现，您可以在相同数据上翻转矩阵排序，那么这是一个零成本操作。
真正昂贵的预取虽然永远不会在 L1 而是在 LLC（最后一级缓存），即使你得到 L1 未命中它仍然是一个廉价的未命中，因为它将从 L2 加载。总之，除非您拥有目标 CPU 架构的所有微小细节，否则很难计算。
于 2012-12-06T16:23:07.997 回答