Оптимизация кэша C для прямого сопоставления кеша

Имея некоторые проблемы с выяснением ставок хита и пропусков следующих двух фрагментов кода.

Данная информация: у нас есть 1024-байтовый прямой кеш с размером блока 16 байт. Таким образом, тогда получается 64 строки (в этом случае). Предположим, что кеш пуст. Рассмотрим следующий код:

struct pos {
    int x;
    int y;
};

struct pos grid[16][16];
int total_x = 0; int total_y = 0;

void function1() {
    int i, j;
    for (i = 0; i < 16; i++) {
         for (j = 0; j < 16; j++) {
             total_x += grid[j][i].x;
             total_y += grid[j][i].y;
         }
    }
}

void function2() {
    int i, j;
    for (i = 0; i < 16; i++) {
         for (j = 0; j < 16; j++) {
             total_x += grid[i][j].x;
             total_y += grid[i][j].y;
         }
    }
}

Я могу сказать по некоторым основным правилам (т.е. массивы C - порядок строк), что функция2 должна быть лучше. Но я не понимаю, как рассчитать процент попадания/промаха. По-видимому, функция1() пропускает 50% времени, а функция2() пропускает только 25% времени.

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

Спасибо.

Ответ 1

Как хранятся данные в памяти
Каждая структура pos имеет размер 8 байтов, поэтому общий размер pos[16][16] составляет 2048 байтов. И порядок массива выглядит следующим образом:
pos[0][0] pos[0][1] pos[0][2]...... pos[0][15] pos[1]0[]...... pos[1][15]....... pos[15][0]...... pos[15][15] < бр /" >

Организация кэширования по сравнению с данными
Для кеша каждый блок равен 16 байтам, который имеет тот же размер, что и два элемента массива. Весь кеш составляет 1024 байта, что вдвое меньше всего массива. Поскольку кеш напрямую отображается, это означает, что если мы будем отмечать блок кеша от 0 до 63, мы можем с уверенностью предположить, что сопоставление должно выглядеть так:
------------ память ---------------------------- cache
pos[0][0] pos[0][1] ----------- > block 0
pos[0][2] pos[0][3] ----------- > block 1
pos[0][4] pos[0][5] ----------- > block 2
pos[0][14] pos[0][15] -------- > block 7
.......
pos[1][0] pos[1][1] ----------- > block 8
pos[1][2] pos[1][3] ----------- > block 9
.......
pos[7][14] pos[7][15] -------- > block 63
pos[8][0] pos[8][1] ----------- > block 0
.......
pos[15][14] pos[15][15] ----- > block 63

Как function1 манипулирует памятью
Цикл следует за внутренним циклом по столбцу, что означает, что первая итерация загружает pos[0][0] и pos[0][1] в кеш block 0, вторая итерация загружает pos[1][0] и pos[1][1] в кеш block 8. Кэши холод, поэтому первый столбец x всегда пропустите, а y всегда попадает. Предполагается, что во втором столбце доступ ко всем данным столбцов загружен в кеш, но это НЕ случай. Поскольку pos[8][0] доступ уже вытеснил бывшую страницу pos[0][0] (они оба отображаются на block 0!). Итак, скорость промаха составляет 50%.

Как function2 управляет памятью
Вторая функция имеет хороший шаблон доступа stride-1. Это означает, что при доступе к pos[0][0].x pos[0][0].y pos[0][1].x pos[0][1].y только первый из них является пропуском из-за холодного кеша. Следующие шаблоны одинаковы. Таким образом, пропускная способность составляет всего 25%.

К-образный ассоциативный кеш следует тому же анализу, хотя это может быть более утомительным. Чтобы получить максимальную отдачу от системы кэширования, попробуйте инициировать хороший шаблон доступа, скажем stride-1, и использовать данные как можно больше во время каждой загрузки из памяти. Микроархитектура cpu реального мира использует другой интеллектуальный дизайн и алгоритм для повышения эффективности. Лучший метод - всегда измерять время в реальном мире, выгружать основной код и проводить тщательный анализ.

Ответ 2

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

Ваша структура имеет длину 8 байтов (2 х 4). Поскольку ваши блоки кэша составляют 16 байт, доступ к памяти grid[i][j] будет извлекать ровно две записи структуры (grid[i][j] и grid[i][j+1]). Поэтому, если вы прокручиваете второй индекс, каждый четвертый доступ приведет к чтению памяти. Если вы зацикливаете первый индекс, вы, вероятно, выбросите вторую введенную запись, которая зависит от количества выборок во внутреннем цикле и общего размера кеша.

Теперь мы также должны подумать о размере кеша: вы говорите, что у вас есть 64 строки, которые непосредственно сопоставлены. В функции 1 внутренний цикл равен 16 выборкам. Это означает, что 17-го вы получите сетку [j] [i + 1]. Это должно быть хитом, так как он должен храниться в кеше с момента последнего внутреннего цикла. Поэтому каждый второй внутренний цикл должен состоять только из хитов.

Хорошо, если мои рассуждения верны, ответ, который вам дал, должен быть ошибочным. Обе функции должны выполнять с 25% промахов. Может быть, кто-то найдет лучший ответ, но если вы поймете мои рассуждения, я бы спросил об этом TA.

Изменить: Думая об этом еще раз, мы должны сначала определить, что на самом деле квалифицируется как промах/удар. Когда вы смотрите

total_x += grid[j][i].x;
total_y += grid[j][i].y;

определены ли они как два обращения к памяти или один? Хороший компилятор с настройками оптимизации должен оптимизировать это для

pos temp = grid[j][i];
total_x += temp.x;
total_y += temp.y;

который можно было бы считать одним доступом к памяти. Поэтому я предлагаю универсальный ответ на все вопросы CS: "Это зависит".