在 L1、L2 和 L3 缓存方面的缓存命中和缓存未命中数

Question

以下代码将运行放在具有以下缓存结构的 CPU 上：

一级缓存：1KB
二级缓存：8KB
三级缓存：64KB

块大小：16B

 unsigned int A[65536];
 int i,j;
 for (i=0 ; i<65536-256 ; i++)
 for (j=1 ; j<128; j++)
 A[i]=A[i]+A[i+j];

我正在准备期中考试，有一道题。修改此代码以尽量减少惩罚次数。根据 L1、L2 和 L3 缓存计算缓存命中数和缓存未命中数。

我尝试通过 Loop Interchange 解决它。如果我更改为如下代码，那么将进行顺序访问，而不是每 16,364 个字跨过内存。

     unsigned int A[65536];
     int i,j;
     for (j=1 ; j<128; j++)
     for (i=0 ; i<65536-256 ; i++)
     A[i]=A[i]+A[i+j];

但我坚持缓存命中和未命中。有人可以向我解释吗？

Answer 1

假设unsigned int是4个字节，你的数组大小是4 * 65536 = 256KB。您的 L3 缓存最多只能容纳 64KB。

为了尽量减少惩罚，你应该做的第一件事是将循环分成 4 个子组，这样一旦你将一个条目加载到 L3，你应该在被逐出之前完全使用它。

unsigned int A[65536];
int i,j,k;
for (k=0 ; k<65536-256; k+=16384)
    for (j=1 ; j<128; j++)
        for (i=k ; i<MIN(k+16384,65536-256) ; i++) //define a MIN function to return minimum
            A[i]=A[i]+A[i+j];

现在计算缓存命中和未命中，一个缓存行可以容纳数组的 4 个条目。当你第一次访问 A[0] 时，它会在 L1、L2 和 L3 中丢失。从内存中获取时，您不仅获取 A[0]，还将获取 A[1]、A[2] 和 A[3]，因为缓存行可以容纳所有 4 个。

在同一条指令中，您还访问了 A[i+j]，在这种情况下将是 A[1]，这将是命中。就这样，

First iteration
    A[i]   - A[0] - Miss
    A[i+j] - A[1] - Hit
Second Iteration
    A[i]   - A[1] - Hit
    A[i+j] - A[2] - Hit
Third Iteration
    A[i]   - A[2] - Hit
    A[i+j] - A[3] - Hit
Forth Iteration
    A[i]   - A[3] - Hit
    A[i+j] - A[4] - Miss // This will cause to fetch A[4], A[5], A[6], A[7]

该模式一直持续到 L1 被填满。

在 L1、L2 和 L3 缓存方面的缓存命中和缓存未命中数

The number of cache hits and cache misses in terms of L1, L2 and L3 caches

caching

cpu-architecture

cpu-cache