-1

我知道命中率是缓存中找到的数据的百分比。但我不知道如何找到算法的命中。我在想，对于代码 1，我将有 11 个块，每个块有 4 个元素，对于代码 2，我将有 4 个块，每个块有 11 个元素，每次我看到 4 个元素丢失。不确定这是否有意义。欢迎任何建议

假设一个 11 行 4 列的二维数组 A，像这样存储在内存中[0][0], [0][1], [0][2], [0][3], [1][0], [1][1], …[10][2], [10][3]

还假设有 10 个内存块的完全关联的单级缓存，每个内存块保存 4 个字节，以及一个 FIFO 替换策略。

每一行都完全适合一个缓存块，不幸的是，整个阵列无法放入缓存中。缓存行太小了...

现在给出以下 2 个代码，1-我如何计算命中率 2-假设缓存访问时间为 5ns，内存访问时间为 70ns，并且假设对内存和缓存的访问重叠，我如何计算每个代码的 EAT ?

代码 1：

for (int row = 0; row < 11; row ++)
{
   for (int column = 0; column < 4; column ++)
   {
      myByte = A [ row, column ];
   }
}

代码 2：

for (int column = 0; column < 4; column ++)
   {
   for (int row = 0; row < 11; row ++)
   {
      myByte = A [ row, column ];
   }
}

任何帮助表示赞赏。谢谢

4

1 回答 1

0

好吧，我们不计算算法的命中率。我们以利用缓存概念的方式编写算法，即获得最大命中率。您的问题实际上属于计算机组织和体系结构。

无论如何，您的 2D - 数组以行主要顺序存储在内存中。因此，对于代码 1，第一个内部 for 循环将从包含四个元素的内存中获取一个块，因为在缓存中没有找到任何内容（因为它是未命中）（即内存访问时间 70ns）。现在后续三个元素即 [0 ][1],[0][2],[0][3] 将从 cahce 获取（即 3*5 = 15ns），即访问前四个元素的总时间 = 70+3*5 = 85ns。

上面的过程将在你的 10 个缓存块中重复你的数组的 10 行。但是对于使用 FIFO 概念的最后一个块，会发生块交换，但时间将保持不变。所以总时间 = 85*11 = 935ns

对于代码 2，

对于内部 for 循环的每次迭代，都会获取一个块。因此，每次访问内存时，您都没有使用缓存的概念，即它是一段糟糕的代码。如果您的数组以列主要顺序存储在内存中，则代码 2 效果最佳。

于 2013-03-26T06:55:40.543 回答