C ++ Как заставить данные предварительной выборки кешировать? (цикл массива)

Question

C ++ Как заставить данные предварительной выборки кешировать? (цикл массива)

У меня такая петля

start = __rdtsc();
unsigned long long count = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
count += tab[i][j];
stop = __rdtsc();
time = (stop - start) * 1/3;

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

6

c++cpu-cache prefetch

Решение

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

Только для GCC:

__builtin_prefetch((const void*)(prefetch_address),0,0);

prefetch_address может быть недействительным, не будет segfault. Если есть слишком маленькая разница между prefetch_address и текущее местоположение, там не может быть никакого эффекта или даже замедления. Попробуйте установить его как минимум на 1 Кб.

7

Самый простой / самый переносимый метод — это просто читать некоторые данные через каждые байты кэширования. Предполагая, что tab является правильным двумерным массивом, вы можете:

char *tptr = (char *)&tab[0][0];
tptr += 64;
char temp;
volatile char keep_temp_alive;
for(int i = 0; i < N; i++)
{
temp += *tptr;
tptr += 64;
for(j = 0; j < M; j++)
count += tab[i][j];
}
keep_temp_alive = temp;

Что-то вроде того. Тем не менее, это зависит от:
1. Вы не заканчиваете чтение вне выделенной памяти [слишком много].
2. Цикл J не намного больше, чем 64 байта. Если это так, вы можете добавить больше шагов temp += *tptr; tptr += 64; в начале цикла.

keep_temp_alive после цикла важно, чтобы компилятор полностью не удалял temp как ненужные загрузки.

К сожалению, я слишком медленно пишу универсальный код, чтобы предлагать встроенные инструкции, пункты за которые идут Леониду.

3

Источник

Accepted Answer

Во-первых, я полагаю, что tab большой двумерный массив, такой как статический массив (например, int tab[1024*1024][1024*1024]) или динамически распределяемый массив (например, int** tab и после mallocс). Здесь вы хотите предварительно получить некоторые данные из tab в кэш, чтобы сократить время выполнения.

Просто я не думаю, что вам нужно вручную вставлять какую-либо предварительную выборку в ваш код, где выполняется простое сокращение для двумерного массива. Современные процессоры будут делать автоматическую предварительную выборку, если это необходимо и выгодно.

Два факта, которые вы должны знать для этой проблемы:

(1) Вы уже используете пространственную местность tab внутри самой внутренней петли. однажды tab[i][0] считывается (после пропуска кэша или сбоя страницы) данные из tab[i][0] в tab[i][15] будет в вашем кэше процессора, при условии, что размер строки кэша составляет 64 байта.

(2) Однако, когда код пересекается в строке, т.е. tab[i][M-1] в tab[i+1][0], очень вероятно, что произойдет промах холодного кэша, особенно когда tab является динамически распределенным массивом, где каждая строка может быть распределена фрагментарно. Однако, если массив размещен статически, каждая строка будет находиться в памяти непрерывно.

Таким образом, предварительная выборка имеет смысл только тогда, когда вы читаете (1) первый элемент следующей строки и (2) j + CACHE_LINE_SIZE/sizeof(tab[0][0]) досрочно.

Вы можете сделать это, вставив операцию предварительной выборки (например, __builtin_prefetch) в верхней петле. Однако современные компиляторы не всегда могут выдавать такие инструкции предварительной выборки. Если вы действительно хотите это сделать, вы должны проверить сгенерированный двоичный код.

Однако, как я уже сказал, я делаю не Рекомендую вам сделать это, потому что современные процессоры в основном будут выполнять автоматическую предварительную выборку, и эта автоматическая предварительная выборка будет в основном превосходить ваш ручной код. Например, в процессорах Intel, таких как процессоры Ivy Bridge, есть несколько средств предварительной выборки данных, таких как предварительная выборка в кэш L1, L2 или L3. (Я не думаю, что мобильные процессоры имеют причудливый предварительный сборщик данных, хотя). Некоторые prefetchers будут загружать смежные строки кэша.

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

3