通过增加数组的大小来减少缓存未命中 - 为什么这样做有效？
reduce the cache misses by increasing size of array - why does this work?
给出教科书中的这段代码 Randal E. Bryant、David R. O'Hallaron - Computer Systems。程序员的视角 [第 3 版]（2016 年，Pearson）:
float dotprod(float x[8], float y[8])
{
float sum = 0.0;
int i;
for (i = 0; i < 8; i++)
sum += x[i] * y[i];
return sum;
}
这是缓存信息：
sizeof(float) = 4.
Array x begins at memory address 0x0 and is stored in row-major order. y follows x.
In each case below, the cache is initially empty.
The only memory accesses are to the entries of the array x and y. All other variables are stored in registers.
Cache size 32 bytes and cache block size is 16 bytes. The cache is direct mapped cache.
We're given the explanation that the miss rate is 100%, due to constant thrashing. Then they go on to say this:
我想知道为什么 float x[12] 会是他们的选择，而不是这些选项之一，例如：
x[9]x[10]x[11]x[16]
为什么这 4 个选项中的 none 会起作用（我被告知它不会起作用？但我不确定为什么，因为那个人没有给出解释）并且只有 x[12] 可以替代 x[8] 数组。或者他们是否对代码中存在的缓存未命中百分比进行了不同的更改？
在具有 16 字节块的 32 字节直接映射缓存中，您将有 2 个块。这意味着对于给定的地址，您将有 1 位来标识块索引，4 位用于块偏移量，用于标识块内的特定字节（2 位用于字偏移量，2 位用于字节偏移量），其余的将是标签。
缓存看起来像这样：
Valid? | Tag | Index | Data
-------+-----+-------+-----
| | 0 | (16 bytes)
-------+-----+-------+-----
| | 1 | (16 bytes)
-------+-----+-------+-----
为简单起见，我们假设 8 位地址（地址越长，您只会得到越长的标签，其他没有任何变化）。在 8 位地址的情况下，您将有 3 位用于标记，1 位用于块索引，4 位用于块偏移。因此，给定一个地址，例如0x34，你可以这样分解：
block offset
tag |
001|1|0100
|
block index
现在假设这两个数组一个接一个地在内存中，像这样：
x[0] | x[1] | ... | x[7] | y[0] | y[1] | ... | y[7]
如果x从地址0x0开始，我们会遇到以下情况：
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|0000 (32)
x[1] 000|0|0100 (4) y[1] 001|0|0100 (36)
x[2] 000|0|1000 (8) y[2] 001|0|1000 (40)
x[3] 000|0|1100 (12) y[3] 001|0|1100 (44)
x[4] 000|1|0000 (16) y[4] 001|1|0000 (48)
x[5] 000|1|0100 (20) y[5] 001|1|0100 (52)
x[6] 000|1|1000 (24) y[6] 001|1|1000 (56)
x[7] 000|1|1100 (28) y[7] 001|1|1100 (60)
| |
block index block index
如您所见，这里的问题是具有相同数组索引的x和y的任意两个元素之间的块索引始终相同.
现在假设您在 x:
结束后添加适当的填充
x[0] | x[1] | ... | x[7] | ...PADDING... | y[0] | y[1] | ... | y[7]
你现在的情况好多了：
element addr element addr
x[0] 000|0|0000 (0) y[0] 01|1|0000 (48)
x[1] 000|0|0100 (4) y[1] 01|1|0100 (52)
x[2] 000|0|1000 (8) y[2] 01|1|1000 (56)
x[3] 000|0|1100 (12) y[3] 01|1|1100 (60)
x[4] 000|1|0000 (16) y[4] 10|0|0000 (64)
x[5] 000|1|0100 (20) y[5] 10|0|0100 (68)
x[6] 000|1|1000 (24) y[6] 10|0|1000 (72)
x[7] 000|1|1100 (28) y[7] 10|0|1100 (76)
| |
block index block index
确实，这种情况是最优的，您将只有 4 次缓存未命中 (x[0]、y[0]、x[4]、y[4])。
为什么其他选项不起作用？好吧，让我们看看。
=== WITH x[9] =======================================
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|0100 (36)
x[1] 000|0|0100 (4) y[1] 001|0|1000 (40)
x[2] 000|0|1000 (8) y[2] 001|0|1100 (44)
x[3] 000|0|1100 (12) y[3] 001|1|0000 (48)
x[4] 000|1|0000 (16) y[4] 001|1|0100 (52)
x[5] 000|1|0100 (20) y[5] 001|1|1000 (56)
x[6] 000|1|1000 (24) y[6] 001|1|1100 (60)
x[7] 000|1|1100 (28) y[7] 010|0|0000 (64)
=== WITH x[10] ======================================
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|1000 (40)
x[1] 000|0|0100 (4) y[1] 001|0|1100 (44)
x[2] 000|0|1000 (8) y[2] 001|1|0000 (48)
x[3] 000|0|1100 (12) y[3] 001|1|0100 (52)
x[4] 000|1|0000 (16) y[4] 001|1|1000 (56)
x[5] 000|1|0100 (20) y[5] 001|1|1100 (60)
x[6] 000|1|1000 (24) y[6] 010|0|0000 (64)
x[7] 000|1|1100 (28) y[7] 010|0|0100 (68)
=== WITH x[11] =====================================
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|1100 (44)
x[1] 000|0|0100 (4) y[1] 001|1|0000 (48)
x[2] 000|0|1000 (8) y[2] 001|1|0100 (52)
x[3] 000|0|1100 (12) y[3] 001|1|1000 (56)
x[4] 000|1|0000 (16) y[4] 001|1|1100 (60)
x[5] 000|1|0100 (20) y[5] 010|0|0000 (64)
x[6] 000|1|1000 (24) y[6] 010|0|0100 (68)
x[7] 000|1|1100 (28) y[7] 010|0|1000 (72)
=== WITH x[16] =====================================
element address element address
x[0] 000|0|0000 (0) y[0] 010|0|0000 (64)
x[1] 000|0|0100 (4) y[1] 010|0|0100 (68)
x[2] 000|0|1000 (8) y[2] 010|0|1000 (72)
x[3] 000|0|1100 (12) y[3] 010|0|1100 (76)
x[4] 000|1|0000 (16) y[4] 010|1|0000 (80)
x[5] 000|1|0100 (20) y[5] 010|1|0100 (84)
x[6] 000|1|1000 (24) y[6] 010|1|1000 (88)
x[7] 000|1|1100 (28) y[7] 010|1|1100 (92)
从上面可以很容易地看出，这些填充选择中的 none 是最优的。 x[16] 基本上与最坏的情况相同，你的填充太多了。 x[9]只解决了1/4的元素问题，x[10]解决了2/4的元素问题，x[11]解决了3/4的元素问题。
因此，正如您所说，这些选项对代码中存在的缓存未命中百分比进行了不同的更改，但其中 none 是最佳的（即可能的最低未命中率）。
唯一最好的配置是你有任何填充，使得 x 以块索引 0 开头，y 以块索引 1 开头，然后 x[4] 位于块索引 1 处， y[4] 位于块索引 0 处。要么这样，要么完全相反。对于任何 N >= 1，数组 x 大小的良好值是 8 * N + 4，最小的是 12.
给出教科书中的这段代码 Randal E. Bryant、David R. O'Hallaron - Computer Systems。程序员的视角 [第 3 版]（2016 年，Pearson）:
float dotprod(float x[8], float y[8])
{
float sum = 0.0;
int i;
for (i = 0; i < 8; i++)
sum += x[i] * y[i];
return sum;
}
这是缓存信息：
sizeof(float) = 4.Array x begins at memory address 0x0 and is stored in row-major order. y follows x.
In each case below, the cache is initially empty.
The only memory accesses are to the entries of the array x and y. All other variables are stored in registers.
Cache size 32 bytes and cache block size is 16 bytes. The cache is direct mapped cache.
We're given the explanation that the miss rate is 100%, due to constant thrashing. Then they go on to say this:
我想知道为什么 float x[12] 会是他们的选择，而不是这些选项之一，例如：
x[9]x[10]x[11]x[16]
为什么这 4 个选项中的 none 会起作用（我被告知它不会起作用？但我不确定为什么，因为那个人没有给出解释）并且只有 x[12] 可以替代 x[8] 数组。或者他们是否对代码中存在的缓存未命中百分比进行了不同的更改？
在具有 16 字节块的 32 字节直接映射缓存中，您将有 2 个块。这意味着对于给定的地址，您将有 1 位来标识块索引，4 位用于块偏移量，用于标识块内的特定字节（2 位用于字偏移量，2 位用于字节偏移量），其余的将是标签。
缓存看起来像这样：
Valid? | Tag | Index | Data
-------+-----+-------+-----
| | 0 | (16 bytes)
-------+-----+-------+-----
| | 1 | (16 bytes)
-------+-----+-------+-----
为简单起见，我们假设 8 位地址（地址越长，您只会得到越长的标签，其他没有任何变化）。在 8 位地址的情况下，您将有 3 位用于标记，1 位用于块索引，4 位用于块偏移。因此，给定一个地址，例如0x34，你可以这样分解：
block offset
tag |
001|1|0100
|
block index
现在假设这两个数组一个接一个地在内存中，像这样：
x[0] | x[1] | ... | x[7] | y[0] | y[1] | ... | y[7]
如果x从地址0x0开始，我们会遇到以下情况：
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|0000 (32)
x[1] 000|0|0100 (4) y[1] 001|0|0100 (36)
x[2] 000|0|1000 (8) y[2] 001|0|1000 (40)
x[3] 000|0|1100 (12) y[3] 001|0|1100 (44)
x[4] 000|1|0000 (16) y[4] 001|1|0000 (48)
x[5] 000|1|0100 (20) y[5] 001|1|0100 (52)
x[6] 000|1|1000 (24) y[6] 001|1|1000 (56)
x[7] 000|1|1100 (28) y[7] 001|1|1100 (60)
| |
block index block index
如您所见，这里的问题是具有相同数组索引的x和y的任意两个元素之间的块索引始终相同.
现在假设您在 x:
x[0] | x[1] | ... | x[7] | ...PADDING... | y[0] | y[1] | ... | y[7]
你现在的情况好多了：
element addr element addr
x[0] 000|0|0000 (0) y[0] 01|1|0000 (48)
x[1] 000|0|0100 (4) y[1] 01|1|0100 (52)
x[2] 000|0|1000 (8) y[2] 01|1|1000 (56)
x[3] 000|0|1100 (12) y[3] 01|1|1100 (60)
x[4] 000|1|0000 (16) y[4] 10|0|0000 (64)
x[5] 000|1|0100 (20) y[5] 10|0|0100 (68)
x[6] 000|1|1000 (24) y[6] 10|0|1000 (72)
x[7] 000|1|1100 (28) y[7] 10|0|1100 (76)
| |
block index block index
确实，这种情况是最优的，您将只有 4 次缓存未命中 (x[0]、y[0]、x[4]、y[4])。
为什么其他选项不起作用？好吧，让我们看看。
=== WITH x[9] =======================================
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|0100 (36)
x[1] 000|0|0100 (4) y[1] 001|0|1000 (40)
x[2] 000|0|1000 (8) y[2] 001|0|1100 (44)
x[3] 000|0|1100 (12) y[3] 001|1|0000 (48)
x[4] 000|1|0000 (16) y[4] 001|1|0100 (52)
x[5] 000|1|0100 (20) y[5] 001|1|1000 (56)
x[6] 000|1|1000 (24) y[6] 001|1|1100 (60)
x[7] 000|1|1100 (28) y[7] 010|0|0000 (64)
=== WITH x[10] ======================================
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|1000 (40)
x[1] 000|0|0100 (4) y[1] 001|0|1100 (44)
x[2] 000|0|1000 (8) y[2] 001|1|0000 (48)
x[3] 000|0|1100 (12) y[3] 001|1|0100 (52)
x[4] 000|1|0000 (16) y[4] 001|1|1000 (56)
x[5] 000|1|0100 (20) y[5] 001|1|1100 (60)
x[6] 000|1|1000 (24) y[6] 010|0|0000 (64)
x[7] 000|1|1100 (28) y[7] 010|0|0100 (68)
=== WITH x[11] =====================================
element address element address
x[0] 000|0|0000 (0) y[0] 001|0|1100 (44)
x[1] 000|0|0100 (4) y[1] 001|1|0000 (48)
x[2] 000|0|1000 (8) y[2] 001|1|0100 (52)
x[3] 000|0|1100 (12) y[3] 001|1|1000 (56)
x[4] 000|1|0000 (16) y[4] 001|1|1100 (60)
x[5] 000|1|0100 (20) y[5] 010|0|0000 (64)
x[6] 000|1|1000 (24) y[6] 010|0|0100 (68)
x[7] 000|1|1100 (28) y[7] 010|0|1000 (72)
=== WITH x[16] =====================================
element address element address
x[0] 000|0|0000 (0) y[0] 010|0|0000 (64)
x[1] 000|0|0100 (4) y[1] 010|0|0100 (68)
x[2] 000|0|1000 (8) y[2] 010|0|1000 (72)
x[3] 000|0|1100 (12) y[3] 010|0|1100 (76)
x[4] 000|1|0000 (16) y[4] 010|1|0000 (80)
x[5] 000|1|0100 (20) y[5] 010|1|0100 (84)
x[6] 000|1|1000 (24) y[6] 010|1|1000 (88)
x[7] 000|1|1100 (28) y[7] 010|1|1100 (92)
从上面可以很容易地看出，这些填充选择中的 none 是最优的。 x[16] 基本上与最坏的情况相同，你的填充太多了。 x[9]只解决了1/4的元素问题，x[10]解决了2/4的元素问题，x[11]解决了3/4的元素问题。
因此，正如您所说，这些选项对代码中存在的缓存未命中百分比进行了不同的更改，但其中 none 是最佳的（即可能的最低未命中率）。
唯一最好的配置是你有任何填充，使得 x 以块索引 0 开头，y 以块索引 1 开头，然后 x[4] 位于块索引 1 处， y[4] 位于块索引 0 处。要么这样，要么完全相反。对于任何 N >= 1，数组 x 大小的良好值是 8 * N + 4，最小的是 12.