Как придумать пример с высокой частотой промахов кэша?

Question

Как придумать пример с высокой частотой промахов кэша?

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

#include <stdlib.h>

int main(void)
{
int i, j, k;

int w = 1000;
int h = 1000;

int **block = malloc(w * sizeof(int*));
for (i = 0; i < w; i++) {
block[i] = malloc(h * sizeof(int));
}

for (k = 0; k < 10; k++) {
for (i = 0; i < w; i++) {
for (j = 0; j < h; j++) {
block[j][i] = 0;
}
}
}

return 0;
}

когда я собираю это с -O0 пометить и запустить с помощью perf stat -r 5 -B -e cache-references,cache-misses ./a.out это дает мне:

 Performance counter stats for './a.out' (5 runs):

715,463 cache-references                                      ( +-  0.42% )
527,634 cache-misses          #   73.747 % of all cache refs  ( +-  2.53% )

0.112001160 seconds time elapsed                                  ( +-  1.58% )

что достаточно для моих целей. Однако, если я пойду дальше и изменю размер матрицы на 2000x2000 это дает:

 Performance counter stats for './a.out' (5 runs):

6,364,995 cache-references                                      ( +-  2.32% )
2,534,989 cache-misses          #   39.827 % of all cache refs  ( +-  0.02% )

0.461104903 seconds time elapsed                                  ( +-  0.92% )

и если я увеличу его еще дальше 3000x3000 Я получил:

 Performance counter stats for './a.out' (5 runs):

59,204,028 cache-references                                      ( +-  1.36% )
5,662,629 cache-misses          #    9.565 % of all cache refs  ( +-  0.11% )

1.116573625 seconds time elapsed                                  ( +-  0.32% )

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

Заметки

Я сказал, что мне нужно что-то относительно независимое от платформы, но все же это мои характеристики:

Intel® Core ™ i5-2467M
4 ГиБ оперативной памяти
64-битная Ubuntu 12.04

10

c++caching perf

Решение

Другие решения

Я не совсем уверен, что вы можете сравнить эти программы или действительно что-то гарантировать, потому что это зависит от того, как ОС распределяет отдельные фрагменты памяти.

Вы должны по крайней мере выделить ВСЕ память как один блок, а затем индексировать в этот блок, чтобы получить все массивы (int* а также int). Таким образом, у вас есть последовательная отправная точка. Вы можете передать размер массива в качестве аргумента, а не перекомпилировать каждый раз.

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

Обратите внимание, что вы должны действительно free ваша память перед выходом.

Как уже указывалось другими, рандомизация вашего шаблона доступа — это хорошая идея.

2

Источник

Accepted Answer

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

int main(void)
{
int i;

int n = 1000 * 1000;

int *block = malloc(n * sizeof(int));

for (i = 0; i < n / 10; i++) {
int ri = rand() % n;
block[ri] = 0;
}

return 0;
}

9