Измерение эффектов TLB на Cortex-A9

Прочитав следующую статью https://people.freebsd.org/~lstewart/articles/cpumemory.pdf ( "Что каждый программист должен знать о памяти" ), я хотел попробовать один из авторов тест, то есть измерение влияния TLB на окончательное время выполнения.

Я работаю над Samsung Galaxy S3, который встраивает Cortex-A9.

Согласно документации:

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

typedef struct {
     int elmt; // sizeof(int) == 4 bytes
     char padding[28]; // 4 + 28 = 32B == cache line size
}entry;


volatile entry ** entries = NULL;

//Allocate memory and init to 0
entries = calloc(NB_ENTRIES, sizeof(entry *));
if(entries == NULL) perror("calloc failed"); exit(1);

for(i = 0; i < NB_ENTRIES; i++)
{
      entries[i] = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
      if(entries[i] == MAP_FAILED) perror("mmap failed"); exit(1);
}

entries[LAST_ELEMENT]->elmt = -1

//Randomly access and init with random values
n = -1;
i = 0;
while(++n < NB_ENTRIES -1)
{
      //init with random value
      entries[i]->elmt = rand() % NB_ENTRIES;

      //loop till we reach the last element
      while(entries[entries[i]->elmt]->elmt != -1)
      {
            entries[i]->elmt++;
            if(entries[i]->elmt == NB_ENTRIES)
                     entries[i]->elmt = 0;
      }

       i = entries[i]->elmt;
}


gettimeofday(&tStart, NULL);
for(i = 0; i < NB_LOOPS; i++)
{
     j = 0;
     while(j != -1)
     {
          j = entries[j]->elmt
     }
}
gettimeofday(&tEnd, NULL);

time = (tEnd.tv_sec - tStart.tv_sec);
time *= 1000000;
time += tEnd.tv_usec - tStart.tv_usec;
time *= 100000
time /= (NB_ENTRIES * NBLOOPS);

fprintf(stdout, "%d %3lld.%02lld\n", NB_ENTRIES, time / 100, time % 100);

У меня есть внешний цикл, который делает NB_ENTRIES меняющимся от 4 до 1024.

Как видно на рисунке ниже, в то время как NB_ENTRIES == 256 записей, время выполнения больше.

Когда NB_ENTRIES == 404, я получаю "лишний объем памяти" (почему превышено превышение? TLB превышено? превышены ли TLB? Таблицы превышены? Виртуальная память для процесса превышена?)

Может кто-нибудь объяснить мне, пожалуйста, что действительно происходит от 4 до 256 записей, а затем от 257 до 404 записей?

Effects of TLB on execution time

РЕДАКТИРОВАТЬ 1

Как было предложено, я запустил membench (src code) и ниже результатов:

membench results

РЕДАКТИРОВАТЬ 2

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

enter image description here

Прямо сейчас, в соответствии с их результатами и объяснениями, я могу только выделить несколько вещей.

  • Графики
  • подтверждают, что размер строки кеша L1 составляет 32 байта, поскольку, как они сказали

"после того, как размер массива превышает размер кэша данных (32 КБ), чтения начинают генерировать промахи [...], точка перегиба возникает, когда каждое чтение генерирует ложь".

В моем случае самая первая точка перегиба появляется при шаге == 32 байта.  - График показывает, что у нас есть кеш второго уровня (L2). Я думаю, что это изображено желтой линией (размер 1 МБ == L2)  - Поэтому два последних графика над последним, вероятно, отражают задержку при доступе к основной памяти (+ TLB?).

Однако из этого теста я не могу определить:

  • ассоциативность кэша. Обычно D-Cache и I-Cache являются 4-сторонними ассоциативными (Cortex-A9 TRM).
  • Эффекты TLB. Как они сказали,

в большинстве систем вторичное увеличение латентности указывает на TLB, который кэширует ограниченное число виртуальных и физических переводов. [...] Отсутствие увеличения латентности, относящегося к TLB, указывает на то, что [...] "

вероятно, были использованы/реализованы большие размеры страниц.

РЕДАКТИРОВАТЬ 3

Эта ссылка объясняет эффекты TLB с другого графика membench. На самом деле можно получить одни и те же эффекты на моем графике.

В системе страниц размером 4 КБ, по мере роста ваших шагов, пока они все еще остаются, 4K, вы будете наслаждаться все меньше и меньше использования каждой страницы [...] вам нужно будет получить доступ к TLB второго уровня при каждом доступе [...]

Cortex-A9 поддерживает режим 4KB страниц. Действительно, как видно на моем графике до шага == 4K, задержки возрастают, тогда, когда он достигает 4K

вы вдруг начинаете получать прибыль снова, так как вы фактически пропускаете целые страницы.

Ответы

Ответ 1

tl; dr → Предоставить правильный MVCE.

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

  • Мне пришлось исправить кучу синтаксических ошибок (отсутствующие точки с запятой) и объявить переменные undefined.

  • После устранения всех этих проблем код НЕ НИЧЕГО (программа завершена еще до запуска первого mmap. Я даю чаевые использовать фигурные скобки все время, вот ваш первый и ваш вторая ошибка, вызванная НЕ:

.

// after calloc:
if(entries == NULL) perror("calloc failed"); exit(1);
// after mmap
if(entries[i] == MAP_FAILED) perror("mmap failed"); exit(1);

обе строки просто завершают вашу программу независимо от состояния.

  1. Здесь вы получите бесконечный цикл (переформатированные, добавленные фигурные скобки, но никаких других изменений):

.

//Randomly access and init with random values
n = -1;
i = 0;
while (++n < NB_ENTRIES -1) {
    //init with random value
    entries[i]->elmt = rand() % NB_ENTRIES;

    //loop till we reach the last element
    while (entries[entries[i]->elmt]->elmt != -1) {
        entries[i]->elmt++;
        if (entries[i]->elmt == NB_ENTRIES) {
            entries[i]->elmt = 0;
        }
    }

    i = entries[i]->elmt;
}

Первая итерация начинается с установки entries[0]->elmt на некоторое случайное значение, затем внутренний цикл увеличивается до тех пор, пока не достигнет LAST_ELEMENT. Тогда i устанавливается на это значение (т.е. LAST_ELEMENT), а второй цикл перезаписывает конечный маркер -1 на другое случайное значение. Затем он постоянно увеличивал mod NB_ENTRIES во внутреннем цикле до тех пор, пока вы не нажмете CTRL + C.

Заключение

Если вам нужна помощь, отправьте Минимальный, полный и проверенный пример, а не что-то еще.