Откуда берется отсутствующий кэш данных L1 в заблокированной матричной матрице?
Я пытаюсь оптимизировать кратность целочисленной матрицы, разделив их на меньший матричный блок, чтобы получить лучшую частоту обращений в кэш на RasPberry Pi 3b+ (это ядро Cortex-A53, со строкой кэша 64 байта, 4-сторонней ассоциативностью. Это 32 Кбайт),
Вот код:
#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
И я поставил А как 1024x512 и Б как 512x1024 в моем тесте. И есть 262144 звонки в mat_mul функция и MxN является 16x8 на последнем звонке mat_mul,
И мой подсчет отсутствия кеша намного меньше результата перфорации, вот так:
Поскольку матрица A имеет размер 16x8, а B - 8x16, то каждая строка B (16* sizeof(int) = 64 Byte) помещается в одну строку кэша L1. И теперь A и B должны вписаться в кэш L1 (16*8*2*sizeof(int) = 1024 Byte, Я предполагаю, что есть кэш-память L1D 32 КБ и с учетом 4-х сторонней связи, 1024 Byte также должен уметь вписываться в него). Так что расчет в mat_mul с А (16x8) и B (8x16) должен содержать 16 + 8 = 24 Отсутствие кэша L1. Так что есть 262,144 * 24 = 6,291,456 пропуски кэша в целом вычислении.
Но результаты перфа показывают, что есть 192,979,016 отсутствие кэша. это 30 раз больше, чем я ожидал.
Итак, мой вопрос, что не так с моим расчетом здесь? Или откуда берется лишний кеш?
И я также использую 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
Спасибо!