Тест критического шага кэш-памяти CPU, дающий неожиданные результаты на основе типа доступа

Ответ 1

Что касается вашего ожидания 3, вы правы. Это как и следовало ожидать. Подробнее см. "Что каждый программист должен знать о памяти" . Это отличная серия статей, объясняющих иерархию памяти.

Так почему же трудно подтвердить номер 3: Есть две основные причины. Один из них - распределение памяти, а другой - преобразование виртуального физического адреса.

Распределение памяти

Не существует строгой гарантии того, каков фактический физический адрес выделенной области памяти. Когда вы хотите протестировать кэширование CPU, я всегда рекомендую использовать posix_memalign для принудительного распределения выделенной границы. В противном случае вы, вероятно, увидите какое-то странное поведение.

Трансляция адресов

Как работает перевод адресов, хорошо объяснено в упомянутой статье. И чтобы подтвердить ваше предположение, вам нужно попытаться определить ожидаемое поведение. Самый простой способ сделать это:

Эксперимент

Выделите набор областей большой памяти k (примерно 512 МБ) в виде массивов int и выровняйте их все с границей страницы 4096b. Теперь перебираем все элементы в области памяти и постепенно добавляем в ваш эксперимент дополнительные области k. Измерьте время и нормализуйте количество прочитанных элементов.

Код может выглядеть так:

#define N 10000000
for(size_t i=0; i < k; ++i) {

   size_t sum=0;
   clock_t t1= clock();
   for(size_t j=0; j < N; ++j) {
       for(size_t u=0; u<i; ++u) {
           sum += data[u][j];
       }
   }

   clock_t t2= clock();

}

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

Обновление

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

Однако, хотя программист обычно не влияет на то, как данные хранятся в кэшах ЦП, при записи есть небольшая разница. Можно выполнять так называемые потоковые записи, которые не загрязняют кеш, а скорее записываются непосредственно в память. Эти записи также называются non-temporal.

Ответ 2

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

Сказав это, ваше четвертое предположение может быть по-прежнему правильным в некоторых случаях, поскольку операция загрузки действительно потребует, чтобы данные были получены до того, как программа продвинется, в то время как хранилище можно буферизовать для записи позже, когда это возможно. Однако нагрузка будет останавливать программу только в том случае, если она находится на некотором критическом пути (что означает, что какая-то другая операция ожидает его результата), поведение, которое ваша тестовая программа не выполняет. Поскольку большинство современных процессоров предлагают исполнение вне очереди, следующие независимые инструкции могут свободно идти, не дожидаясь завершения загрузки. В вашей программе нет взаимосвязи между циклами, за исключением простого продвижения индекса (который может легко запускаться вперед), поэтому вы в основном не узкополосны по задержке памяти, а скорее по пропускной способности памяти, что совсем другое. Кстати, чтобы добавить такую ​​зависимость, вы можете эмулировать обход связанного списка или даже проще - убедитесь, что массив инициализирован до нуля (и переключает записи только на нули) и добавляет содержимое каждого прочитанного значения в индекс на каждой итерации (в дополнение к приращению) - это создало бы зависимость без изменения самих адресов. В качестве альтернативы, сделайте что-нибудь противное (если предположить, что компилятор недостаточно умен, чтобы отказаться от этого...):

    if (onlyWriteToCache)
    {
        buffer[index] = (char)(index % 255);
    }
    else
    {
        buffer[index] = (char)(buffer[index] % 255);
        index += buffer[index];
        index -= buffer[index];
    }

Теперь, о результатах, кажется, что запись vs read + write ведет себя одинаково, когда вы прыгаете на критический шаг, как и ожидалось (так как чтение не сильно отличается от RFO, которое будет выдано писать все равно). Однако для некритического шага операция чтения + записи выполняется намного медленнее. Теперь трудно сказать, не зная точной системы, но это может произойти из-за того, что нагрузки (чтения) и записи (записи) не выполняются на одном и том же этапе в течение срока действия инструкций - это означает, что между нагрузкой и следующий магазин, вы, возможно, уже вышли из строя, и вам нужно снова отправить его снова во второй раз. Я не слишком уверен в этом, но если вы хотите проверить, возможно, вы могли бы добавить инструкцию сборки sfence между итерациями (хотя это значительно замедлит вас).

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

Ответ 3

Я также попытался сделать шаг на рейке, как только я прочитал о механизме кеша в Optimization С++ от Agner Frog.

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

Моя первая попытка сделать это в пользовательском пространстве не удалась. (У меня есть процессор i5-4200).

Total size 128kb cache set size 8kb => time 18ms; 568000000
Total size 256kb cache set size 16kb => time 13ms; 120000000
Total size 384kb cache set size 24kb => time 12ms; 688000000
Total size 512kb cache set size 32kb => time 14ms; 240000000

$g++ -std = С++ 11 -march = native -O3 hit-stride.cpp -o hit-stride

#include<iostream>
#include<chrono>

using namespace std::chrono;
using namespace std;

int main(int argc, char** argv) {
  unsigned int cacheSetSizes[] = { 8, 16, 24, 32 };
  const int ways = 8;

  for (unsigned int i = 0; i < sizeof(cacheSetSizes) / sizeof(int); ++i) {
    const unsigned int setSize = cacheSetSizes[i] * 1024;
    const unsigned int size = setSize * ways * 2;
    char* buffer = new char[size];
    for (int k = 0; k < size; ++k) {
      buffer[k] = k % 127;
    }
    const auto started = steady_clock::now();
    int sum = 0;
    for (int j = 0; j < 1000000; ++j) {
      for (int k = 0; k < size; k += setSize) {
        sum += buffer[k];
      }
    }
    const auto ended = steady_clock::now();
    cout << "Total size " << (size >> 10) << "kb cache set size " << cacheSetSizes[i]
         << "kb => time " << duration_cast<milliseconds>(ended - started).count()
         << "ms; " << sum << endl;
    delete buffer;
  }
  return 0;
}

"Тот же" код, заключенный в модуль ядра, выглядит как хиты L2: Я понял, что мне нужно физически соединять память. Это можно сделать только в режиме ядра. Мой размер кеша L1 32kb. В тесте я перехожу по диапазону памяти дольше, чем количество способов (8) с шагом, равным размеру кеша. Таким образом, я получаю заметное замедление на 32kb (последняя строка).

Apr 26 11:13:54 diehard kernel: [24992.943076] Memory 512 kb is allocated
Apr 26 11:13:54 diehard kernel: [24992.969814] Duration  23524369 ns for cache set size         8 kb; sum = 568000000
Apr 26 11:13:54 diehard kernel: [24992.990886] Duration  21076036 ns for cache set size        16 kb; sum = 120000000
Apr 26 11:13:54 diehard kernel: [24993.013832] Duration  22950526 ns for cache set size        24 kb; sum = 688000000
Apr 26 11:13:54 diehard kernel: [24993.045584] Duration  31760368 ns for cache set size        32 kb; sum = 240000000

$make && & sudo insmod hello.ko && sleep 1 && tail -n 100/var/log/syslog

#include <linux/module.h>   /* Needed by all modules */
#include <linux/kernel.h>   /* Needed for KERN_INFO */
#include <linux/time.h>    

static unsigned long p = 0;
static struct timespec started, ended;
static unsigned int cacheSetSizes[] = { 8, 16, 24, 32 };
static const u32 ways = 8;
static const u32 m = 2;
static char* buffer;
static unsigned int setSize;
static unsigned int size;
static unsigned int i, j, k;
static int sum;

int init_module(void) {
  s64 st, en, duration;
  u32 max = 1*1024*1024;
  printk(KERN_INFO "Hello world 1.\n");
  p = __get_free_pages(GFP_DMA, get_order(max));
  printk(KERN_INFO "Memory %u kb is allocated\n", ways * m * 32);
  buffer = (char*) p;

  for (k = 0; k < max; ++k) {
    buffer[k] = k % 127;
  }

  for (i = 0; i < sizeof(cacheSetSizes) / sizeof(int); ++i) {
    setSize = cacheSetSizes[i] * 1024;
    size = setSize * ways * m;
    if (size > max) {
      printk(KERN_INFO "size %u is more that %u", size, max);
      return 0;
    }
    getnstimeofday(&started);
    st = timespec_to_ns(&started);

    sum = 0;
    for (j = 0; j < 1000000; ++j) {
      for (k = 0; k < size; k += setSize) {
        sum += buffer[k];
      }
    }

    getnstimeofday(&ended);
    en = timespec_to_ns(&ended);
    duration = en - st;
    printk(KERN_INFO "Duration %9lld ns for cache set size %9u kb; sum = %9d\n",
           duration, cacheSetSizes[i], sum);
  }
  return 0;
}

void cleanup_module(void) {
  printk(KERN_INFO "Goodbye world 1.\n");
  free_pages(p, get_order(1*1024*1024));
  printk(KERN_INFO "Memory is free\n");
}