Поведение кэша функции, суммирующей 2d массив - PullRequest
Новая
       9

Поведение кэша функции, суммирующей 2d массив

3 голосов
/ 15 января 2020

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

int A[2][4]

int sum()
{
    int sum = 0;

    for (int j=0; j<4; j++) {
        for (int i=0; i<2; i++) {
            sum += A[i][j];
        }
    }
    return sum;
}

Допустим следующее:

  • Система памяти состоит из регистров, одного кеша L1 и основной памяти
  • Кеш холодный, когда вызывается функция, и массив был инициализирован в другом месте
  • Переменные i, j и sum все хранятся в регистрах
  • Массив A выравнивается в памяти так, что первые два элемента массива отображаются на тот же блок кеша.
  • sizeof (int) == 4
  • Кэш напрямую отображается с размером блока 8 байтов

a) Предположим, что кеш состоит из 2 комплектов. Заполните таблицу, чтобы указать, будет ли соответствующий доступ к памяти в A ударом (h) или промахом (m). Решение: 

|-------|-------|-------|-------|-------|
|   A   | Col 0 | Col 1 | Col 2 | Col 3 |
|-------|-------|-------|-------|-------|
| Row 0 |   m   |   m   |   m   |   m   |
|-------|-------|-------|-------|-------|
| Row 1 |   m   |   m   |   m   |   m   |
|-------|-------|-------|-------|-------|

б) Каков порядок попаданий и пропусков, если кэш состоит из 4 наборов вместо 2 наборов? Решение: 

|-------|-------|-------|-------|-------|
|   A   | Col 0 | Col 1 | Col 2 | Col 3 |
|-------|-------|-------|-------|-------|
| Row 0 |   m   |   h   |   m   |   h   |
|-------|-------|-------|-------|-------|
| Row 1 |   m   |   h   |   m   |   h   |
|-------|-------|-------|-------|-------|

Я сейчас пытаюсь понять, что происходит. Я думаю, что первое, на что следует обратить внимание, это то, что c хранит массивы, используя мажор строки, а l oop читает его в мажоре столбца. Теперь мое понимание кеша еще не очень хорошее, но позвольте мне попробовать.

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

Итак, вот мой мыслительный процесс:

Массив сохраняется как строка-майор: 

A[0][0] A[0][1] A[0][2] A[0][3] A[1][0] A[1][1] A[1][2] A[1][3]

j=0:
    i=0: Read A[0][0] => miss => Set 1: A[0][0] & A[0][1]
    i=1: Read A[1][0] => miss => Set 2: A[1][0] & A[1][1]

j=1:
    i=0: Read A[0][1] => hit since A[0][1] was read into cache at j=0, i=0. Set stays the same.
    i=1: Read A[1][1] => hit since A[1][1] was read into cache at j=0, i=0. Set stays the same.
j=2:
    i=0: Read A[0][2] => miss => Set 1: A[0][2] & A[0][1]
    i=1: Read A[1][2] => miss => Set 2: A[1][2] & A[1][1]

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

Где я точно терплю неудачу?

1 Ответ

1 голос
/ 15 января 2020

Следующая строка вашего объяснения неверна: 

    i=1: Read A[1][0] => miss => Set 2: A[1][0] & A[1][1]

Поскольку кэш имеет прямое сопоставление , он будет сохранен в наборе 1, а не в наборе 2, перезаписывая предыдущий запись в кеше.

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

Что на самом деле происходит следующее:

Сначала я отмечу границы строк кэша знаком "|" и укажите, к какому набору кеша они привязаны: 

A[0][0] A[0][1] | A[0][2] A[0][3] | A[1][0] A[1][1] | A[1][2] A[1][3]
     Set 1      |      Set 2      |      Set 1      |      Set 2

Теперь вот что происходит: 

j=0:
    i=0: Read A[0][0]
        => miss (Set 1 is cold)
        => Set 1: A[0][0] & A[0][1]
    i=1: Read A[1][0]
        => miss (since A[1][0] was never loaded into Set 1 yet)
        => Set 1: A[1][0] & A[1][1]

j=1:
    i=0: Read A[0][1]
        => miss (since A[0][1] was evicted from Set 1)
        => Set 1: A[0][0] & A[0][1]
    i=1: Read A[1][1]
        => miss (since A[1][1] was evicted from Set 1)
        => Set 1: A[1][0] & A[1][1]

j=2:
    i=0: Read A[0][2]
        => miss (Set 2 is cold)
        => Set 2: A[0][2] & A[0][3]
    i=1: Read A[1][2]
        => miss (since A[1][2] was never loaded into Set 2 yet)
        => Set 2: A[1][2] & A[1][3]

j=3:
    i=0: Read A[0][3]
        => miss (since A[0][3] was evicted from Set 2)
        => Set 2: A[0][2] & A[0][3]
    i=1: Read A[1][3]
        => miss (since A[1][3] was evicted from Set 2)
        => Set 2: A[1][2] & A[1][3]

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

...