matrix - 理论上如何计算内存中超过缓存大小的矩阵的缓存未命中数？

Question

我目前正在考虑以行优先顺序存储在主存储器中的 64 位整数元素的nxn 矩阵 M。我有一个16KB 的L1数据缓存，分为 64B 块（无 L2 或 L3）。我的代码旨在通过以行优先顺序或列优先顺序遍历矩阵，一次打印出数组的每个元素。

在n = 16（即 16 x 16 矩阵）的情况下，我使用行优先顺序和列优先顺序计算了 0 个缓存未命中，因为矩阵 M 完全适合 16KB 缓存（它永远不需要跳转到主内存来获取元素）。我将如何处理例如n = 256（256 x 256 64 位整数矩阵）的情况；即当 M 不完全适合缓存时？我是否将所有不适合的整数都算作未命中，还是可以以某种方式利用空间局部性？假设缓存最初是空的。

Answer 1

“0 缓存未命中”似乎假设您开始时 M 已经在缓存中。这已经有点可疑了，但没关系。

对于 256x256 的情况，您需要模拟缓存的行为方式。您必须有缓存未命中才能引入丢失的条目。每个缓存未命中不仅会带来请求的 int，还会带来 7 个相邻的 int。