Откуда берется отсутствующий кэш данных L1 в заблокированной матричной матрице?

Question

Я пытаюсь оптимизировать целочисленное матричное кратное, разделяя их на меньший матричный блок, чтобы получить лучшую частоту обращений в кэш на Raspberry Pi 3b + (это ядро ​​Cortex-A53, со строкой кэша 64 байта, 4-сторонней ассоциативностью. это 32K байт ).

Вот код:

#define L1_D_CACHE_SZ 32 * 1024
size_t cache_tune_g = 32;

void mat_mul(int *A, int *B, int *C, size_t M, size_t N, size_t strideA, size_t strideB, size_t strideC) {

  for(int i = 0; i < M; i++) {
    int *Ai = A + (N + strideA) * i;
    for(int j = 0; j < M; j++) {
        int sum = 0;
        int *Bj = B + j;

        for (int k = 0; k < N; k++) {
            int *Aik = Ai + k;
            int *Bjk = Bj + (M + strideB) * k;
            sum += (*Aik) * (*Bjk);
        }

        int *Cij = C + (M + strideC) * i + j;
        *Cij = (*Cij) + sum;
    }
  }
}

// if B 'fits' into L1 data cache, then do the multiplication, 
// else divide A and B into 4 sub-matrixes and then call itself recursively.
void mat_mul_opt(int *A, int *B, int *C, size_t M, size_t N, size_t strideA, size_t strideB, size_t strideC) {
  int B_size = sizeof(int) * M * N;
  if (B_size < L1_D_CACHE_SZ/cache_tune_g) {
    mat_mul(A, B, C, M, N, strideA, strideB, strideC);
  } else {
    size_t M_sub = M / 2;
    size_t N_sub = N / 2;
    size_t strideA_sub = N_sub + strideA;
    size_t strideB_sub = M_sub + strideB;
    size_t strideC_sub = M_sub + strideC;

    int *A1 = A;
    int *A2 = A + N_sub;
    int *A3 = A + (N + strideA) * M_sub;
    int *A4 = A3 + N_sub;

    int *B1 = B;
    int *B2 = B + M_sub;
    int *B3 = B + (M + strideB) * N_sub;
    int *B4 = B3 + M_sub;

    int *C1 = C;
    int *C2 = C + M_sub;
    int *C3 = C + (M + strideC) * M_sub;
    int *C4 = C3 + M_sub;

    // due to the result in C is accumulated, order here matters.
    mat_mul_opt(A1, B1, C1, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);
    mat_mul_opt(A2, B3, C1, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);

    mat_mul_opt(A1, B2, C2, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);
    mat_mul_opt(A2, B4, C2, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);

    mat_mul_opt(A3, B1, C3, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);
    mat_mul_opt(A4, B3, C3, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);

    mat_mul_opt(A3, B2, C4, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);
    mat_mul_opt(A4, B4, C4, M_sub, N_sub, strideA_sub, strideB_sub, strideC_sub);
  }
}

А вот и результат перфекта:

 1,244,238,488      cache-references:u                                            (87.41%)
   193,808,545      cache-misses:u            #   15.576 % of all cache refs      (87.42%)
   192,979,016      L1-dcache-load-misses:u                                       (75.14%)
 6,651,396,875      cycles:u                                                      (87.59%)
 3,499,761,427      instructions:u            #    0.53  insn per cycle           (87.62%)
   539,801,098      branches:u                                                    (87.62%)                                            
     1,632,374      armv7_cortex_a7/l2d_cache_refill/:u                                     (87.48%)

   4.847838433 seconds time elapsed

И я установил Aкак 1024x512 и B как 512x1024 в моем тесте.И получите 262144 вызовы функции mat_mul, а MxN - это 16x8 при последнем вызове mat_mul.

И мой расчет отсутствия кэша на намного меньше , чем результат perf, здесь:

Поскольку матрица A равна 16x8, а B - 8x16, то каждая строкаB (16* sizeof(int) = 64 Byte) помещается в одну строку кэша L1.И A, и B теперь должны помещаться в кэш-память L1 (16*8*2*sizeof(int) = 1024 Byte, я предполагаю, что кэш-память L1D составляет 32 КБ, и с учетом упомянутой четырехсторонней связи 1024 Byte также должна быть в состоянии в нее поместиться).Таким образом, расчет в mat_mul с A (16x8) и B (8x16) должен содержать 16 + 8 = 24 L1 пропущенных кеша.Таким образом, во всех вычислениях 262,144 * 24 = 6,291,456 отсутствует кэш.

Но результаты perf показывают, что 192,979,016 пропускают кэш.Это в 1035 раз больше, чем я ожидал.

Итак, мой вопрос: что не так с моими вычислениями здесь?Или откуда берется лишний кеш?

И я также использую perf для записи, откуда отсутствует кеш L1 D, результат как ниже.Эти 99% пропущены, если из mat_mul, а 80% пропущены в mat_mul, из строки самого внутреннего цикла: sum += (*Aik) * (*Bjk);.

  1.21 │ 9c:┌─→ldr    r0, [r3], #4                                                                                                                                           
  2.84 │    │  ldr    ip, [r1], fp                                                                                                                                           
       │    │  cmp    lr, r3                                                                                                                                                 
 80.42 │    │  mla    r2, ip, r0, r2                                                                                                                                         
       │    └──bne    9c               

Спасибо!