Сколько стоит мисс L1 Cache?

Question

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

Я провел некоторое тестирование <long story goes here>, и мне интересно, связано ли различие в производительности с ошибками в кеше памяти. Следующий код демонстрирует проблему и сводит ее к критической части синхронизации. В следующем коде есть несколько циклов, которые посещают память в случайном порядке, а затем в порядке возрастания адресов.

Я запустил его на машине с XP (скомпилированной с VS2005: cl / O2) и на Linux-машине (gcc –Os). Оба произвели одинаковое время. Эти времена в миллисекундах. Я считаю, что все циклы работают и не оптимизированы (в противном случае он будет запущен «мгновенно»).

*** Testing 20000 nodes
Total Ordered Time: 888.822899
Total Random Time: 2155.846268

Имеют ли эти цифры смысл? Разница в основном из-за пропусков кэша L1 или что-то еще происходит? Имеется 20 000 ^ 2 обращений к памяти, и если бы каждый из них был с ошибкой кэша, то это примерно 3,2 наносекунды за промах. Машина с XP (P4), которую я тестировал, имеет частоту 3,2 ГГц, и я подозреваю (но не знаю), что она имеет 32 КБ L1 и 512 КБ L2. Я предполагаю, что с 20 000 записей (80 КБ) не будет значительного количества пропусков L2. Так что это будет (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss. Это кажется высоким для меня. Может быть, нет, или, может быть, моя математика плохая. Я попытался измерить ошибки кэша с помощью VTune, но получил BSOD. И теперь я не могу подключить его к серверу лицензий (grrrr).

typedef struct stItem
{
   long     lData;
   //char     acPad[20];
} LIST_NODE;



#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2, llFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
   *pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn't need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
   // Just use clock(), this test doesn't need higher resolution
   *pt1 = clock();
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2 = clock();
   *pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif



long longrand()
{
   #if defined( WIN32 )
   // Stupid cheesy way to make sure it is not just a 16-bit rand value
   return ( rand() << 16 ) | rand();
   #else
   return rand();
   #endif
}

// get random value in the given range
int randint( int m, int n )
{
   int ret = longrand() % ( n - m + 1 );
   return ret + m;
}

// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
   long *plShuffle,  // (O) return array of "randomly" ordered integers
   long lNumItems    // (I) length of array
)
{
   long i;
   long j;
   long t;

   for ( i = 0; i < lNumItems; i++ )
      plShuffle[i] = i;

   for ( i = 0; i < lNumItems; i++ )
      {
      j = randint( i, lNumItems - 1 );

      t = plShuffle[i];
      plShuffle[i] = plShuffle[j];
      plShuffle[j] = t;
      }
}



int main( int argc, char* argv[] )
{
   long          *plDataValues;
   LIST_NODE     *pstNodes;
   long          lNumItems = 20000;
   long          i, j;
   LONGLONG      t1;  // for timing
   double dms;

   if ( argc > 1 && atoi(argv[1]) > 0 )
      lNumItems = atoi( argv[1] );

   printf( "\n\n*** Testing %u nodes\n", lNumItems );

   srand( (unsigned int)time( 0 ));

   // allocate the nodes as one single chunk of memory
   pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
   assert( pstNodes != NULL );

   // Create an array that gives the access order for the nodes
   plDataValues = (long*)malloc( lNumItems * sizeof( long ));
   assert( plDataValues != NULL );

   // Access the data in order
   for ( i = 0; i < lNumItems; i++ )
      plDataValues[i] = i;

   StartTimer( &t1 );

   // Loop through and access the memory a bunch of times
   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Ordered Time: %f\n", dms );

   // now access the array positions in a "random" order
   ShuffleArray( plDataValues, lNumItems );

   StartTimer( &t1 );

   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Random Time: %f\n", dms );

}

Answer 1

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

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

Кухонный счетчик - это ваш кэш L1, который в 12 раз медленнее регистров. Требуется 12 x 1 = 12 секунд, чтобы подойти к прилавку, взять пакет с грецкими орехами и вылить его в руку .

Холодильник - это ваш кэш L2, в четыре раза медленнее, чем L1. Требуется 4 x 12 = 48 секунд, чтобы подойти к холодильнику, открыть его, убрать остатки прошлой ночи с дороги, вынуть коробку яиц, откройте коробку, положите 3 яйца на прилавок и положите коробку обратно в холодильник.

Шкаф - это ваш кэш L3, в три раза медленнее, чем L2. Требуется 3 x 48 = 2 минуты и 24 секунды, чтобы сделать три шага к шкафу, наклониться, открыть дверь, повернуть вокруг чтобы найти противень для выпечки, извлеките его из шкафа, откройте его, выкопайте, чтобы найти разрыхлитель, положите его на прилавок и смести беспорядок, который вы пролили на пол.

А основная память? Это магазин на углу, в 5 раз медленнее, чем L3. Требуется 5 x 2:24 = 12 минут, чтобы найти свой кошелек, надеть обувь и куртку, броситься вниз по улице, взять литр молока, броситься домой, сними обувь и куртку и возвращайся на кухню.

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

Мораль истории: Организуйте доступ к своей памяти так, чтобы ЦПУ приходилось ходить за продуктами как можно реже.

Числа были взяты из сообщения в блоге Ошибка очистки кэша , в котором указано, что для конкретного процессора Intel 2012 года верно следующее:

• доступ к регистру = 4 инструкции за цикл
• L1 латентность = 3 цикла (12 х регистров)
• L2 латентность = 12 циклов (4 x L1, 48 x регистр)
• задержка L3 = 38 циклов (3 x L2, 12 x L1, 144 x регистр)
• Задержка DRAM = 65 нс = 195 циклов на процессоре 3 ГГц (5 x L3, 15 x L2, 60 x L1, 720 x регистр)

Галерея эффектов кэш-памяти также хорошо читает эту тему.

Answer 2

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

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

Answer 3

3,2 нс для пропуска кэша L1 вполне правдоподобно. Для сравнения, на одном конкретном современном многоядерном процессоре PowerPC промах L1 составляет около 40 циклов - для некоторых ядер немного больше, чем для других, в зависимости от того, как далеко они находятся от кэша L2 (да, действительно). Мисс L2 составляет не менее 600 циклов.

Кэш - это все в производительности; Процессоры теперь намного быстрее, чем память, так что вы фактически оптимизируете шину памяти вместо ядра.

Answer 4

Ну, да, похоже, что в основном это будут пропуски кэша L1.

10 циклов при пропадании кэша L1 звучат довольно разумно, возможно, с низкой стороны.

Чтение из ОЗУ займет порядка 100 с или может быть даже 1000 с (я слишком устал, чтобы пытаться делать математику прямо сейчас;)) циклов, так что это все еще огромная победа над этим.

Answer 5

Если вы планируете использовать cachegrind, обратите внимание, что это только симулятор попадания / пропуска кэша. Это не всегда будет точно. Например: если вы обращаетесь к некоторой ячейке памяти, скажем, 0x1234 в цикле 1000 раз, cachegrind всегда будет показывать вам, что была только одна ошибка кэша (первый доступ), даже если у вас что-то вроде:

clflush 0x1234 в вашем цикле.

На x86 это вызовет все 1000 кеш-пропусков.

Answer 6

Некоторые цифры для P4 с частотой 3,4 ГГц из серии Lavalys Everest:

• L1 кэш-памяти составляет 8 КБ (кэш-линии 64 байта)
• L2 - 512K
• Задержка выборки L1 составляет 2 цикла
• Задержка получения L2 примерно вдвое больше, чем вы видите: 20 циклов

Подробнее здесь: http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

(время ожидания указано в нижней части страницы)

Answer 7

Самое простое, что нужно сделать - это сделать масштабную фотографию целевого процессора и физически измерить расстояние между ядром и кешем уровня 1. Умножьте это расстояние на расстояние, которое электроны могут перемещать в секунду в меди. Затем выясните, сколько тактов вы можете иметь за одно и то же время. Это минимальное количество циклов ЦП, которое вы тратите на промах L1.

Вы также можете определить минимальную стоимость извлечения данных из ОЗУ с точки зрения количества циклов ЦП, потраченных таким же образом. Вы можете быть удивлены.

Обратите внимание, что то, что вы видите здесь, определенно связано с промахами кэша (будь то L1 или оба L1 и L2), потому что обычно кэш извлекает данные в одной строке кэша, как только вы обращаетесь к чему-либо в этом кэше линия, требующая меньше поездок в оперативную память.

Однако то, что вы, вероятно, также видите, это то, что ОЗУ (даже если оно называется оперативной памятью) по-прежнему предпочитает линейный доступ к памяти.

Answer 8

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