Я написал простую программу умножения матриц, чтобы продемонстрировать эффект кэширования и измерения производительности с помощью perf. Две функции для сравнения относительной эффективности: sqmat_mult и sqmat_mult_efficient:
void sqmat_mult(int x, const int a[x][x], const int b[x][x], int m[x][x])
{
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
int sum = 0;
for (int k = 0; k < x; k++) {
sum += a[i][k] * b[k][j]; // access of b array is non sequential
}
m[i][j] = sum;
}
}
}
static void sqmat_transpose(int x, int a[x][x])
{
for (int i = 0; i < x; i++) {
for (int j = i+1; j < x; j++) {
int temp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = temp;
}
}
}
void sqmat_mult_efficient(int x, const int a[x][x], int b[x][x], int m[x][x])
{
sqmat_transpose(x, b);
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
int sum = 0;
for (int k = 0; k < x; k++) {
sum += a[i][k] * b[j][k]; // access of b array is sequential
}
m[i][j] = sum;
}
}
sqmat_transpose(x, b);
}
Однако, когда я запускаю perf stat на основе этих двух функций, я запутался в статистике "сбоев страниц". Выход для sqmat_mult:
428374.070363 task-clock (msec) # 1.000 CPUs utilized
128 context-switches # 0.000 K/sec
127 cpu-migrations # 0.000 K/sec
12,334 page-faults # 0.029 K/sec
8,63,12,33,75,858 cycles # 2.015 GHz (83.33%)
2,89,73,31,370 stalled-cycles-frontend # 0.34% frontend cycles idle (83.33%)
7,90,36,10,13,864 stalled-cycles-backend # 91.57% backend cycles idle (33.34%)
2,24,41,64,76,049 instructions # 0.26 insn per cycle
# 3.52 stalled cycles per insn (50.01%)
8,84,30,79,219 branches # 20.643 M/sec (66.67%)
1,04,85,342 branch-misses # 0.12% of all branches (83.34%)
428.396804101 seconds time elapsed
В то время как выход для sqmat_mult_efficient:
8534.611199 task-clock (msec) # 1.000 CPUs utilized
39876.726670 task-clock (msec) # 1.000 CPUs utilized
11 context-switches # 0.000 K/sec
11 cpu-migrations # 0.000 K/sec
12,334 page-faults # 0.309 K/sec
1,19,87,36,75,397 cycles # 3.006 GHz (83.33%)
49,19,07,231 stalled-cycles-frontend # 0.41% frontend cycles idle (83.33%)
50,40,53,90,525 stalled-cycles-backend # 42.05% backend cycles idle (33.35%)
2,24,10,77,52,356 instructions # 1.87 insn per cycle
# 0.22 stalled cycles per insn (50.01%)
8,75,27,87,494 branches # 219.496 M/sec (66.68%)
50,48,390 branch-misses # 0.06% of all branches (83.33%)
39.879816492 seconds time elapsed
При транспонированном умножении количество "незадействованных бэкэнд-циклов" значительно уменьшается, как и ожидалось. Это связано с малым временем ожидания получения когерентной памяти. Что меня смущает, так это то, что количество «сбоев страниц» одинаково. Сначала я подумал, что это может быть проблемой переключения контекста, поэтому я запустил программу с расписанием SCHED_FIFO и приоритетом 1. Количество переключений контекста уменьшилось примерно с 800 до 11, но «сбои страниц» остались такими же, как и раньше.
Размер матрицы, которую я использую, равен 2048 x 2048, поэтому весь массив не поместится на странице 4K. Он также не помещается во весь мой кэш (4MiB в моем случае), поскольку размер трех матриц (3 *2048* 2048 * sizeof (int) == 48MiB) значительно превышает общий кэш avaibale. Предполагая, что «ошибки страницы» здесь относятся к пропаданию TLB или кешу, я не вижу, как эти два алгоритма могут иметь одинаковое число. Я понимаю, что значительное улучшение эффективности, которое я вижу, связано с тем, что происходит попадание в кэш L1, но это не означает, что передача из ОЗУ в кэш не играет никакой роли.
Я также провел еще один эксперимент, чтобы проверить, масштабируются ли «ошибки страницы» в соответствии с размером массива. Как и ожидалось.
Так что мои вопросы -
- Правильно ли я полагаю, что "сбои страниц" означают промах TLB или промах кэша?
- Почему «ошибки страниц» одинаковы для обоих алгоритмов?