总结二维数组的函数的缓存行为

Question

我正在尝试了解缓存的概念并遇到了这个练习，但我并不完全理解它。考虑：

int A[2][4]

int sum()
{
    int sum = 0;

    for (int j=0; j<4; j++) {
        for (int i=0; i<2; i++) {
            sum += A[i][j];
        }
    }
    return sum;
}

假设如下：

内存系统由寄存器、单个 L1 高速缓存和主内存组成
当函数被调用并且数组已经在别处初始化时缓存是冷的
变量i,j和sum都存储在寄存器中
数组 A 在内存中对齐，前两个数组元素映射到同一个缓存块。
大小（整数）== 4
缓存直接映射，块大小为8字节

a) 假设缓存由2组组成。填写 table 以指示 A 中相应的内存访问是命中 (h) 还是未命中 (m)。解决方案：

|-------|-------|-------|-------|-------|
|   A   | Col 0 | Col 1 | Col 2 | Col 3 |
|-------|-------|-------|-------|-------|
| Row 0 |   m   |   m   |   m   |   m   |
|-------|-------|-------|-------|-------|
| Row 1 |   m   |   m   |   m   |   m   |
|-------|-------|-------|-------|-------|

b) 如果缓存由 4 组而不是 2 组组成，命中和未命中的模式是什么？解决方案：

|-------|-------|-------|-------|-------|
|   A   | Col 0 | Col 1 | Col 2 | Col 3 |
|-------|-------|-------|-------|-------|
| Row 0 |   m   |   h   |   m   |   h   |
|-------|-------|-------|-------|-------|
| Row 1 |   m   |   h   |   m   |   h   |
|-------|-------|-------|-------|-------|

我现在正试图了解发生了什么。我认为首先要注意的重要事情是 c 使用主行存储数组，但循环在主列中读取它。现在我对缓存的理解还不是很好，但让我试试。

所以假设我们有 2 组缓存，每组缓存 8 个字节。如果我们访问 A[i][j]，我们会读取一个 int，即 4 个字节。但是缓存是 8bytes，它也会读取下一个整数。（这就是原因，在这里切换循环会提高性能，但无论如何。）

所以这是我的思考过程：

数组保存为行优先：

A[0][0] A[0][1] A[0][2] A[0][3] A[1][0] A[1][1] A[1][2] A[1][3]

j=0:
    i=0: Read A[0][0] => miss => Set 1: A[0][0] & A[0][1]
    i=1: Read A[1][0] => miss => Set 2: A[1][0] & A[1][1]

j=1:
    i=0: Read A[0][1] => hit since A[0][1] was read into cache at j=0, i=0. Set stays the same.
    i=1: Read A[1][1] => hit since A[1][1] was read into cache at j=0, i=0. Set stays the same.
j=2:
    i=0: Read A[0][2] => miss => Set 1: A[0][2] & A[0][1]
    i=1: Read A[1][2] => miss => Set 2: A[1][2] & A[1][1]

我们基本上可以到此为止，因为我离解决方案还很远，因此这表明，我不明白它是如何工作的。

我到底哪里失败了？

Answer 1

你解释的下面一行是错误的：

    i=1: Read A[1][0] => miss => Set 2: A[1][0] & A[1][1]

由于缓存是direct-mapped，所以会存储到集合1，而不是集合2，覆盖之前的缓存条目。

你的解释对于完全关联的缓存是正确的，但练习指出缓存是直接映射的，这意味着它是单向集关联的。

实际情况如下：

首先，我将用“|”标记缓存行边界并指定它们映射到哪个缓存集：

A[0][0] A[0][1] | A[0][2] A[0][3] | A[1][0] A[1][1] | A[1][2] A[1][3]
     Set 1      |      Set 2      |      Set 1      |      Set 2

现在，情况是这样的：

j=0:
    i=0: Read A[0][0]
        => miss (Set 1 is cold)
        => Set 1: A[0][0] & A[0][1]
    i=1: Read A[1][0]
        => miss (since A[1][0] was never loaded into Set 1 yet)
        => Set 1: A[1][0] & A[1][1]

j=1:
    i=0: Read A[0][1]
        => miss (since A[0][1] was evicted from Set 1)
        => Set 1: A[0][0] & A[0][1]
    i=1: Read A[1][1]
        => miss (since A[1][1] was evicted from Set 1)
        => Set 1: A[1][0] & A[1][1]

j=2:
    i=0: Read A[0][2]
        => miss (Set 2 is cold)
        => Set 2: A[0][2] & A[0][3]
    i=1: Read A[1][2]
        => miss (since A[1][2] was never loaded into Set 2 yet)
        => Set 2: A[1][2] & A[1][3]

j=3:
    i=0: Read A[0][3]
        => miss (since A[0][3] was evicted from Set 2)
        => Set 2: A[0][2] & A[0][3]
    i=1: Read A[1][3]
        => miss (since A[1][3] was evicted from Set 2)
        => Set 2: A[1][2] & A[1][3]

主要问题是您需要的缓存行总是在您有机会再次访问它之前从缓存中逐出。这是由于用于访问数组的访问模式不佳（column major 而不是主要行）。一次只使用一组缓存，而不是整个缓存（两组）。这是低效的，会导致不必要的缓存逐出。

总结二维数组的函数的缓存行为

Cache behaviour of a function summing up a 2d array

c

caching

virtual-memory