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

Question

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

• 一级缓存:1KB

• 二级缓存:8KB

• 三级缓存:64KB

• 区 block 大小: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 被填满。