我们如何计算此代码段中缓存的 reads/misses 个数？

Question

鉴于我目前正在学习的这本教科书的这段代码片段。 Randal E. Bryant、David R. O'Hallaron - 计算机系统。 A Programmer's Perspective [第 3 版]（2016 年，Pearson）（全球版，因此本书的练习可能有误。）

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;
    }
}

这是给出的信息

The heart of the recent hit game SimAquarium is a tight loop that calculates the average position of 512 algae. You are evaluating its cache performance on a machine with a 2,048-byte direct-mapped data cache with 32-byte blocks (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;
You should also assume the following:

sizeof(int) = 4.

grid begins at memory address 0.

The cache is initially empty.

The only memory accesses are to the entries of the array grid.

Variables i, j, total_x, and total_y are stored in registers

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

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%

我猜A，答案是从32*32 *2推导出来的？ 32*32 用于矩阵的维度和 2 因为 x 和 y vals 有 2 个独立的循环。这个对吗？阅读总数应该如何统计？
我们如何计算缓存中发生的未命中总数和未命中率？我读到未命中率为 (1- hit-rate)

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。

另请注意，本书中似乎存在错误。

这里：

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），这将给出书中所说的结果。

我们如何计算此代码段中缓存的 reads/misses 个数？

how do we calculate the number of reads/misses of the cache in this code snippet?

computer-science

caching

cpu-architecture

cpu-cache