缓存内存优化数组转置 : C

Question

typedef int array[2][2];

void transpose(array dst, array src) {
    int i, j;
    for (j = 0; j < 2; j++) {
        for (i = 0; i < 2; i++) {
            dst[i][j] = src[j][i];
        }
    }
}

src 数组从地址 0 开始，dst 数组从地址 0x10 开始。

L1 数据缓存，直接映射，写入分配，8 字节 block 大小。

缓存总大小为 16 个数据字节。

src 和 dst 数组的每个条目的命中或未命中是什么？

答案是:

src: 
[0][0] -> miss,
[0][1] -> miss,
[1][0] -> miss,
[1][1] -> hit

dst:
[0][0] -> miss,
[0][1] -> miss,
[1][0] -> miss,
[1][1] -> miss

如果缓存总大小为 32 个数据字节，则答案为:

src: 
[0][0] -> miss,
[0][1] -> hit,
[1][0] -> miss,
[1][1] -> hit

dst:
[0][0] -> miss,
[0][1] -> hit,
[1][0] -> miss,
[1][1] -> hit

我不确定这两种结果。我不太了解数组和缓存的概念。

Answer 1

因此，在第一个实例中，您有两个缓存行，每个缓存行 8 个字节，总共 16 个字节。我假设 int 数据大小为 4 个字节。鉴于数组在 C 中的位置和您提供的偏移量，这些是可以缓存的内存行:

Cacheable lines:
#A: &src[0][0] = 0x00, &src[0][1] = 0x04
#B: &src[1][0] = 0x08, &src[1][1] = 0x0C
#C: &dst[0][0] = 0x10, &dst[0][1] = 0x14
#D: &dst[1][0] = 0x18, &dst[1][1] = 0x1C

然后我们需要知道程序访问每个内存地址的访问顺序。我假设没有可能导致编译器重新排序的优化。

Access order and cache behavior (assuming initially empty):
#1: load src[0][0] --> Miss line A = cache slot 1
#2: save dst[0][0] --> Miss line C = cache slot 2
#3: load src[0][1] --> Hit  line A = cache slot 1
#4: save dst[0][1] --> Hit  line C = cache slot 2
#5: load src[1][0] --> Miss line B = cache slot 1 (LRU, replaces line A)
#6: save dst[1][0] --> Miss line D = cache slot 2 (LRU, replaces line C)
#7: load src[1][1] --> Hit  line B = cache slot 1
#8: save dst[1][1] --> Hit  line D = cache slot 2

我认为这与您的第二个答案相符。然后缓存大小为 32 字节(4 行)，假设所有其他因素不变:

Access order and cache behavior (assuming initially empty):
#1: load src[0][0] --> Miss line A = cache slot 1
#2: save dst[0][0] --> Miss line C = cache slot 2
#3: load src[0][1] --> Hit  line A = cache slot 1
#4: save dst[0][1] --> Hit  line C = cache slot 2
#5: load src[1][0] --> Miss line B = cache slot 3
#6: save dst[1][0] --> Miss line D = cache slot 4
#7: load src[1][1] --> Hit  line B = cache slot 3
#8: save dst[1][1] --> Hit  line D = cache slot 4

它们是相同的。唯一的区别是您是否再次重新运行移调。在情况 1 中，您会得到完全相同的行为(好吧，您会从缓存中充满所有错误的东西开始，所以它也可能是空的)。但是，在更大的缓存情况下，第二次调用所需的一切都已缓存，因此不会有缓存未命中。

我的答案和你的答案之间的差异很可能是由于我们对循环计数寄存器(i 和 j)的编译器行为的假设。我假设它们都存储在寄存器中(因此不会影响数据缓存)。您可能需要假设它们在内存中的某个地方(因此与缓存交互)以获得预期的结果。