Счет попаданий / промахов при кешировании массива

Question

Я читаю книгу «Компьютерные системы» от Bryant & O'Hallaron, есть упражнения, решение которых кажется неправильным.Поэтому я хотел бы убедиться, что

учитывая

struct point {
  int x; 
  int y;  };


struct array[32][32];

for(i = 31; i >= 0; i--) {
   for(j = 31; j >= 0; j--) {
      sum_x += array[j][i].x;
      sum_y += array[j][i].y; }}

sizeof(int) = 4;

у нас есть 4096 байтов кеша с размером блока (строки) 32 байта.Процент попаданий спрашивается.

Мое рассуждение состояло в том, что у нас есть блоки 4096/32 = 128, каждый блок может хранить 4 точки (2*4*4 = 32), поэтому кэш может хранить 1/2 массива, то есть 512 точек (всего 32 * 32 =1024).Поскольку код обращается к массиву в главном порядке столбцов, доступ к каждой точке пропущен.Так что у нас array[j][i].x всегда отсутствует, а array[j][i].y находится под ударом.Наконец шанс промаха = шанс попадания = 1/2 .

Проблема: Решение говорит, что частота попаданий равна 3/4, потому что кэш может хранить весь массив.

Но, по моим рассуждениям, кеш может хранить только половину очков

Я что-то пропустил?

Answer 1

Если вы расшифровали программу правильно, то вы правы, ответ 3/4 неправильный.

Ответ 3/4 будет правильным , если индексы всамые внутренние sum += ... операторы были расположены так, чтобы самый правый индекс изменялся наиболее быстро, то есть как:

    sum_x += array[i][j].x;
    sum_y += array[i][j].y;

В этом случае 1-я, 5-я, 9-я ... итерации цикла были бы пропущены, нострока, загруженная в кэш при каждом из этих пропусков, приведет к попаданию следующих трех итераций.

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

В качестве примера (при условиидля простоты, когда адрес первого члена array[0][0] выровнен с началом кэша), ссылка на array[31][31] в первом проходе цикла является пропуском, который вызывает загрузку строки 127 кэша.Строка 127 теперь содержит данные для [31][28], [31][29], [31][30] и [31][31].Однако выборка array[15][31] приводит к перезаписи строки 127 до ссылки на array[31][30], поэтому, когда в итоге наступает ход [31][30], это тоже промах.А затем промах в [15][30] заменяет строку до ссылки [31][29].

IMO ваш коэффициент попадания 1/2 является чрезмерным, поскольку он учитывает доступ к координате .y как удар.Однако, это не то, что делает оригинальный ответ 3/4.Если бы выборка .y координаты была посчитана как попадание, то исходный ответ был бы 7/8.Вместо этого он считает каждую полную точку или, возможно, каждую итерацию цикла как попадание или промах.По этому показателю показатель успешности программы, как написано в вашем вопросе, составляет хороший раунд 0.

Answer 2

Верхние четыре строки массива занимают часть кэша:

|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|...

Выше приведена схема массива, как прикладной математик записал бы массив на бумаге.Каждый элемент состоит из пары (x, y), точки .

Четыре строки, помеченные o на диаграмме, содержат 128 точек, достаточно для заполнения1024 байта, что составляет только одну четверть кэша, но смотрите: в вашем коде переменная i равна

• счетчик основных циклов, а также
• индекс массива строка (как написано на бумаге).

Итак, давайте снова посмотрим на диаграмму.Как ваши вложенные циклы шагают по массиву, как показано на схеме?

Ответ: очевидно, ваши циклы шагают вправо по верхнему ряду, как показано на схеме, с j (столбец) в качестве вспомогательного счетчика цикла.Однако, как вы заметили, массив хранится по столбцам.Поэтому, когда элемент [j][i] == [0][0] загружен, с ним загружается вся строка кэша.И что включает в себя эту строку кэша?Это четыре элемента, помеченные на диаграмме *.

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

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

При данной вложенности цикла коэффициент попадания действительно равен 3 / 4.

ДАЛЬНЕЙШАЯ ОБСУЖДЕНИЕ

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

Можете ли вы написать элемент (например, array[3][14].x), который ударил бы?

Могу.array[j][i] == array[10][5] ударил бы.(Оба .x и .y будут попадать.)

Я объясню.array[j][i] == array[10][4] будет отсутствовать, тогда как array[10][5], array[10][6] и array[10][7] в конечном итоге попадут.Почему в конце концов? Это важно.Хотя все четыре элемента, которые я назвал, загружаются аппаратным обеспечением кеша одновременно, array[10][5] не доступен для вашего кода (то есть для процессора) при обращении к array[10][4].Скорее всего, после доступа к array[10][4] программа и ЦП получат доступ к array[11][4] в следующий раз .

Программа и ЦП получат доступ к array[10][5] только позже.

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

ПРИЛОЖЕНИЕ: ЗАКАЗ МАТРИЦ FORTRAN / BLAS / LAPACK

Стандартно в числовых вычислениях хранение матриц по столбцама не рядом.Это называется хранилище столбца .К сожалению, в отличие от более раннего языка программирования на Фортране, язык программирования C изначально не был предназначен для численных вычислений, поэтому в C для хранения массивов по столбцам нужно писать array[column][row] == array[j][i], что, конечно, означает, что нотация прикладного математика обращает вспятьего или ее карандаш написал бы это.

Это артефакт языка программирования C.Артефакт не имеет математического значения, но при программировании на C вы должны не забывать набирать [j][i].[Если бы вы программировали на ныне в основном устаревшем языке программирования Fortran, вы бы набрали (i, j), но это не Fortran.]

Причина, по которой хранилище на основе столбцов является стандартным, связана с последовательностью, в которойЦП выполняет скалярное умножение, умножение и сложение с плавающей запятой, когда в математической / карандашной терминологии матрица [A] действует слева на вектор столбца x.Стандартная библиотека подпрограмм линейной алгебры (BLAS), используемая LAPACK и другими, работает таким образом.Вы и я должны работать таким же образом, не только потому, что нам, скорее всего, понадобится взаимодействовать с BLAS и / или LAPACK, но и потому, что в численном отношении это более плавно.