2

我试图弄清楚如何计算数组的未命中率。我有答案，但我不明白答案是如何得出的。我有以下代码：

int C[N1][N2];
int A[N1][N3];
int B[N3][N2];

initialize_arrays(A, B, C, N1, N2, N3);

for(i=0; i<N1; ++i)
   for(j=0; j<N2; ++j)
      for(k=0; k<N3, ++k)
         C[i][j] += A[i][k] * B[k][j];

我还有以下信息：（N1=N2=N3=2048这是什么意思？？）。该处理器具有 32kB 的 L1 数据高速缓存，行大小为 64B（无 L2 高速缓存）。（什么是线条尺寸？）

我知道数组 C 的未命中率是(N^2/16)/N^3. 我知道公式是(total misses)/(total accesses)。我看到有N^3总访问，但他们是如何获得总未命中的？

(N^3)/(N^3)我也知道数组 B:和 A:的未命中率(N^2/16)/N^3。有人可以向我解释他们是如何在这里得到全部未命中的吗？

4

1 回答 1

2

始终以行的粒度访问/管理缓存。这里的行大小是64B。这意味着在一个高速缓存行中，一个高速缓存行中将有 16 个元素（64B / 4B = 16）。接下来重要的是每 17 个元素都在一个新行中，一旦将一行放入缓存，它可能会产生 15 次命中。

解决了这个问题，让我们看看访问模式。A[0][0]、B[0][0]、C[0][0]、A[0][1]、B[1][0]、C[0][0]、A[ 0][2]、B[2][0]、C[0][0]、...... A[0][16]、B[16][0]、C[0][0 ]、A[0][17]、B[17][0]、C[0][0]、……等等

现在由于一行有 16 个元素，并且可以安全地假设内存中元素的行主要放置 A[0][0] - A[0][15] 将属于第一个缓存行（让我们调用这个 AL1) 并且类似地让 B[0][0] - B[0][15] 属于 BL1 行。根据这些信息，我们可以根据缓存行编写访问模式。AL1，BL1，CL1，AL1，BL129，CL1，AL1，BL257，CL1，...... AL1，BL2049，CL1，AL2，BL2176，CL1，......等等。

现在缓存大小为 32kB，这意味着缓存可以容纳 512 行。由于这是 L1，我们假设它是双向关联缓存。因此有 256 套。这意味着在数组的每 256 行之后，第 257 行映射到与第 1 行相同的集合。

访问映射到集合 1 的行时的缓存内容如下所示

第一次迭代 - 内部

Access to - AL1 - Miss
 AL1 
Access to - BL1 - Miss
 AL1
 BL1
Access to - CL1 - Miss
 CL1
 BL1

第二次迭代 - 内部

Access to - AL1 - Miss
 CL1
 AL1
Access to - CL1 - Hit
 CL1
 AL1

第三次迭代 - 内部

Access to - AL1 - Hit
 CL1
 AL1
Access to - BL257 - Miss
 BL257
 AL1
Access to - CL1 - Miss
 BL257
 CL1

第 4 次迭代 - 内部

Access to - AL1 - Miss
 AL1
 CL1
Access to - CL1 - Hit
 AL1
 CL1

第 5 次迭代 - 内部

Access to - AL1 - Hit
 CL1
 AL1
Access to - BL513 - Miss
 BL513
 AL1
Access to - CL1 - Miss
 BL513
 CL1

. . .

第 16 次迭代 - 内部

Access to - AL1 - Miss
 AL1
 CL1
Access to - CL1 - Hit
 AL1
 CL1

第 17 次迭代 - 内部

Access to - BL2049 - Miss
 BL2049
 CL1
Access to - CL1 - Hit
 BL2049
 CL1

第 18 次迭代 - 内部

Access to - CL1 - Hit
 BL2049
 CL1

对于中间循环的第一次迭代。我们有第 1 组，

A -> M, M, H, M, H, M, H, M, H, M, H, M, H , M, H, M, ~ , ~ , ~ , ~ , ....... 
=> after 2048 iterations - 7 hits 9 misses, 16 accesses

B -> M, ~ , M, ~ ,  M, ~ , ........
=> after 2048 iterations - 0 Hits, 1024 misses, 1024 accesses

C -> M, H, M, H, M, H, M, H, M, H, M, H, M, H, M, H, H , H, H , H, ......
=> after 2048 iterations - 2040 hits, 8 misses, 2048 accesses

对于中间循环的第 2-16 次迭代，

Exact hit / miss / access pattern as before.

对于中间循环的第 17 - 2048 次迭代，

A -> same as before
B -> No accesses
C -> No accesses

总结一下 - 对于外循环的 1 次迭代，我们有集合 1，

A -> N*9 misses , N * 16 accesses
B -> N/2 * 16 Misses , N/2 * 16 accesses
C -> 8 * 16 Misses , N * 16 accesses

在外循环中，我们可以看到，对于数组 C 和 A，每次交替迭代都将具有与第一次迭代（如上总结）相同的命中/未命中/访问模式。外循环的每次迭代都将具有相同的命中/未命中/访问模式。访问模式 a 数组 B 的第一次迭代。

因此，（终于！）

对于 Set 1，在程序结束时，我们有

A -> N^2 * 9 / 2 misses, N^2 * 8 accesses
B -> N^2 * 8 misses, N^2 * 8 accesses
C -> N * 64 misses, N^2 * 8 accesses

访问模式在所有集合中都是相似的。因此，在程序结束时，我们拥有所有集合

A -> N^2 * 1152 misses, N^3 accesses
B -> N^3 misses, N^3 accesses
C -> N^2 * 8 misses, N^3 accesses

我知道这与问题中指出的不同。我不知道怎么做。我会很高兴听到其他答复。

于 2013-05-04T07:45:35.020 回答