我们如何计算这段代码片段中缓存的读取/未命中次数？
鉴于我目前正在学习的这本教科书中的这段代码片段。Randal E. Bryant, David R. O'Hallaron - 计算机系统。A Programmer's Perspective [3rd ed.] (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;
}
}
这是给出的信息
最近热门游戏 SimAquarium 的核心是一个计算 512 藻类平均位置的紧密循环。您正在一台具有 2,048 字节直接映射数据缓存和 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;您还应该假设以下几点：
- 大小（整数）= 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%
-
我猜是 A，答案是从
32*32 *2?32*32对于矩阵和 2 的维度，因为 x 和 y vals 有 2 个单独的循环。这样对吗？应该如何计算reads的总数？ -
我们如何计算缓存中发生的未命中总数和未命中率？我读到未命中率为（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），这将给出书中所说的结果。