cpumemory.pdf - кэш оптимизировано умножения матриц

Question

Я читаю cpumemory.pdf от Ульриха Drepper и я не в состоянии понять следующие части об оптимизации доступа кэша в матричном умножении из главы 6.2.1 (стр 49-50):

Первый наивным метод матричного умножения показано:

for (i = 0; i < N; ++i) 
    for (j = 0; j < N; ++j) 
     for (k = 0; k < N; ++k) 
      res[i][j] += mul1[i][k] * mul2[k][j]; 

mul2 доступ по столбцам так что для каждого столбца одна строка кэша впустую. Ульрих говорит:

С SizeOf (двойным) является 8 это означает, что в полной мере использовать строку кэша, мы должны размотать средний цикл 8 раз.

Для краткости я развернул среднюю петлю только 2 раза.

for (i = 0; i < N; ++i) 
    for (j = 0; j < N; j += 2) 
     for (k = 0; k < N; ++k) { 
      res[i][j+0] += mul1[i][k] * mul2[k][j+0]; 
      res[i][j+1] += mul1[i][k] * mul2[k][j+1]; 
     } 

Теперь очевидно, что если кэш линия 2 двойных значения ширины он будет полностью использоваться. Но тогда Ульрих продолжает:

Продолжая эту мысль, чтобы эффективно использовать матрицу Реза, а также, то есть к запись 8 результатов в то же время, мы должны разворачивать внешний контур 8 раз хорошо.

Для краткости я развернул внешнюю петлю только 2 раза снова.

for (i = 0; i < N; i += 2) 
    for (j = 0; j < N; j+=2) 
     for (k = 0; k < N; ++k) { 
      res[i+0][j+0] += mul1[i+0][k] * mul2[k][j+0]; 
      res[i+0][j+0] += mul1[i+0][k] * mul2[k][j+0]; 
      res[i+1][j+0] += mul1[i+1][k] * mul2[k][j+0]; 
      res[i+1][j+1] += mul1[i+1][k] * mul2[k][j+1]; 
     } 

Мне кажется, что еще хуже, чем предыдущая версия, потому что теперь mul1 получает доступ колонн. Пожалуйста, объясните, что имел в виду Ульрих.

Answer 1

Внутри кеша есть три матрицы: левый вход, правый вход и результат.

Доступ к левому входу осуществляется только по оригинальному коду, потому что он является строковым, а самый внутренний цикл увеличивает k, поэтому он идет по линии кэша. Вторая матрица получает доступ к одной развертке, потому что теперь все столбцы в строке кэша используются до выключения линии кэша.

Вопрос - это матрица результатов .. она также имеет ряд строк, но строка кэша индексируется j, а не k .. и вы правы .. j уже развернут, поэтому он использует все элементы в строке кэша в матрице результатов .. так что, похоже, ничего не получается при втором разворачивании .. все, что он делает, это добавить два дополнительные строки кэша .. дополнительная для левой матрицы и дополнительная для матрицы результатов! Он не улучшает охват элементов любых строк кеша!

Однако бывает, что повторное использование строки кэша правой матрицы дважды, что уменьшает общее количество раз, когда строки правой матрицы должны быть введены .. и она не увеличивает количество раз влево и строки правого матричного кэша будут введены .. поэтому, возможно, повторное использование всей строки - это то преимущество, из которого получается преимущество. Я предполагаю, что вопрос заключается в том, правильно ли он заблокирован до размера кеша и что заданная ассоциативность кеша .. если все строки всех трех матриц остаются в кеше, то это не имеет никакого преимущества. (но это не делает ничего хуже!)