在L1，L2和L3缓存方面，缓存命中率和缓存的数量都错过了

Question

以下代码将在CPU上运行以下缓存结构：

• l1缓存：1KB

• l2缓存：8KB

• L3缓存：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缓存计算缓存命中的数量和缓存错过的数量。

我尝试通过循环互换来解决它。如果我更改下面的代码，因此将有一个顺序访问，而不是每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]; 

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

在同一指令中，您还访问[i j]，在这种情况下，将是[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]

an模式一直持续到填充L1为止。