我们如何计算这个代码片段中缓存的读取/未命中次数

Question

给出我目前正在学习的这本教科书中的代码片段(全球版，因此本书的练习可能是错误的。(

for (i = 31; i >= 0; i--) {
for (j = 31; j >= 0; j--) {
total_x += grid[i][j].x;
}
}
for (i = 31; i >= 0; i--) {
for (j = 31; j >= 0; j--) {
total_y += grid[i][j].y;
}
}

这是提供的信息

最近热门游戏《模拟水族馆》的核心是一个计算512个藻类的平均位置。您正在评估其在具有2048字节直接映射数据高速缓存的机器，具有32字节块(B＝32(。

struct algae_position {
int x;
int y;
};

struct algae_position grid[32][32];
int total_x = 0, total_y = 0;
int i, j;

您还应该假设以下内容：

• sizeof(int(=4
• 网格从内存地址0开始
• 缓存最初为空
• 唯一的内存访问是对数组网格的条目的访问
• 变量i、j，total_x和total_y存储在寄存器中

这本书给出了以下问题作为练习：

A. What is the total number of reads?    
Answer given : 2048  
B. What is the total number of reads that miss in the cache?
Answer given : 1024    
C. What is the miss rate?  
Answer given: 50%

1. 我猜对于A，答案是从32*32 *2推导出来的？CCD_ 2和2，因为x和y值有2个单独的循环。这是正确的吗？应如何计算读取的总数？

2. 我们如何计算缓存中发生的未命中总数和未命中率？我读到未命中率是(1-命中率(

Answer 1

问题A

您对32 x 32 x 2的读数是正确的。

问题B

循环从31倒计时到0，但这对这个问题来说并不重要。对于从0到31的循环，答案是相同的。由于这更容易解释，我假设循环计数器会增加。

当您读取grid[0][0]时，您将获得缓存未命中。这将使grid[0][0]、grid[0][1]、grid[0][2]和grid[0][3]进入缓存。这是因为每个元素是2x4＝8个字节，块大小是32。换句话说：32/8=4个网格元素在一个块中。

因此，下一个缓存未命中是针对grid[0][4]，它将再次将接下来的4个网格元素带入缓存。等等…比如：

miss
hit
hit
hit
miss
hit
hit
hit
miss
hit
hit
hit
...

所以在第一个循环中，你只需要：

"Number of grid elements" divided by 4.

或

32 * 32 / 4 = 256

通常在第一个循环中：

Misses = NumberOfElements / (BlockSize / ElementSize)

所以这里：

Misses = 32*32 / (32 / 8) = 256

由于缓存大小仅为2048，并且整个网格为32 x 32 x 8=8192，因此在第一个循环中读取到缓存中的任何内容都不会在第二个循环中生成缓存命中。换句话说，两个循环都将有256次未命中。

因此，缓存未命中的总数为2 x 256=512。

还要注意，书中似乎有一个bug。

此处：

The heart of the recent hit game SimAquarium is a tight loop that calculates the
average position of 512 algae.
^^^
Hmmm... 512 elements...

此处：

for (i = 31; i >= 0; i--) {
for (j = 31; j >= 0; j--) {
^^^^^^
hmmm... 32 x 32 is 1024

因此，循环访问1024个元素，但文本显示为512。所以书中出现了问题。

问题C

Miss rate = 512 misses / 2048 reads = 25 %

注意：

由于非常严格，我们不能确定元素大小是整数大小的两倍。C标准允许结构包含填充。因此，原则上，结构中可以有8个字节的填充(即元素大小为16(，这将给出书中所说的结果