Какова стоимость прошивки L1 Cache?
Изменить. Для справочных целей (если кто-то наткнулся на этот вопрос), Игорь Островский написал отличный пост промахи кэша. В нем обсуждаются несколько различных проблем и показаны номера примеров. Редактировать конец
Я провел некоторое тестирование <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 ГГц, и я подозреваю (но не знаю) имеет кэш L1 32 Кбайт и 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 );
}
Ответы
Ответ 1
Пока я не могу ответить на вопрос о том, имеют ли значения номера (я не очень хорошо разбираюсь в задержках кэша, но для записи ~ 10 циклов L1 кэш-пропусков звучит правильно), я могу предложить вам Cachegrind как инструмент, который поможет вам увидеть различия в производительности кеша между вашими 2 тестами.
Cachegrind - это инструмент Valgrind (фреймворк, который поддерживает всегда прекрасную memcheck), которая просматривает кеширование и ветвление/промахи. Это даст вам представление о том, сколько кеш-хитов/пропусков вы фактически получаете в своей программе.
Ответ 2
Вот попытка дать представление об относительной стоимости пропусков кэш-памяти по аналогии с печеньем для выпечки шоколадных печей...
Ваши руки - ваши регистры. Вам нужно 1 секунда, чтобы выпустить шоколадные чипсы в тесто.
Кухонный счетчик - это ваш кеш L1, в двенадцать раз медленнее, чем регистры. Требуется 12 х 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), но различия между ними могут иметь огромное влияние на производительность. Оптимизация исключительно для сложностей с большим объемом - это решение решить, добавлять ли шоколадные чипсы в тесто 1 за раз или 10 за раз, но не забудьте положить их в свой список продуктов.
Мораль истории: Организуйте доступ к вашей памяти, поэтому процессор должен идти на продукты как можно реже.
Числа были взяты из сообщения Cache Flushing Fallacy, что указывает на то, что для конкретного процессора Intel на 2012 год верно следующее:
- доступ к регистру = 4 инструкции за цикл
- L1 latency = 3 цикла (регистр 12 x)
- L2 latency = 12 циклов (4 x L1, 48 x регистр)
- L3 latency = 38 циклов (3 x L2, 12 x L1, 144 x регистр)
- Задержка DRAM = 65 нс = 195 циклов на CPU 3 ГГц (регистр 5 x L3, 15 x L2, 60 x L1, 720 x)
Галерея Галерея эффектов кэша процессора также хорошо читает эту тему.
![Mmmm, cookies ...]()
Ответ 3
3.2ns для пропусков кеша L1 вполне правдоподобно. Для сравнения, на одном конкретном современном многоядерном процессоре PowerPC промах L1 составляет около 40 циклов - немного больше для некоторых ядер, чем другие, в зависимости от того, насколько они далеко от кэша L2 (да действительно), Пропуск L2 не менее 600.
Кэш - это все в производительности; Процессоры намного быстрее, чем память, теперь вы почти оптимизируете для шины памяти вместо ядра.
Ответ 4
Ну да, похоже, что это будет главным образом пропуски кэша L1.
10 циклов для пропусков кеша L1 звучат примерно разумно, возможно, немного на нижней стороне.
Чтение из ОЗУ займет порядка 100 секунд или может быть даже 1000 (слишком устало, чтобы делать математику прямо сейчас;)) циклов, так что все еще огромная победа над этим.
Ответ 5
Если вы планируете использовать cachegrind, обратите внимание, что это только симулятор хита/прошивки. Это не всегда будет точно. Например: если вы получаете доступ к некоторым местам памяти, скажите 0x1234 в цикле 1000 раз, cachegrind всегда покажет вам, что был только один промах кеша (первый доступ), даже если у вас есть что-то вроде:
clflush 0x1234 в вашем цикле.
В x86 это приведет к промахе 1000 кешей.
Ответ 6
Некоторые номера для 3.4GHz P4 от запуска Everest Lavalys:
- dcache L1 - 8K (кешью 64 байт)
- L2 - 512K
- L1 время ожидания выборки - 2 цикла
- L2 fetch latency примерно удваивает то, что вы видите: 20 циклов
Подробнее здесь:
http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt
(для задержек смотрите в нижней части страницы)
Ответ 7
Трудно сказать что-либо точно без большого тестирования, но, по моему опыту, шкала различий определенно может быть отнесена к кешу CPU L1 и/или L2, особенно в сценарии со случайным доступом. Вы, вероятно, могли бы сделать это еще хуже, гарантируя, что каждый доступ имеет хотя бы минимальное расстояние от последнего.
Ответ 8
Самый простой способ - сделать масштабированную фотографию целевого процессора и физически измерить расстояние между ядром и кешем уровня 1. Умножьте, что расстояние на расстоянии электронов может перемещаться в секунду в меди. Затем выясните, сколько часов циклов вы можете иметь в это же время. Что минимальное количество циклов процессора, которые вы будете тратить на провал кеша L1.
Вы также можете выработать минимальную стоимость извлечения данных из ОЗУ с точки зрения количества циклов CPU, потраченных таким же способом. Вы можете быть поражены.
Обратите внимание, что то, что вы видите здесь, определенно имеет какое-то отношение к промахам кэш-памяти (будь то L1 или оба L1 и L2), потому что обычно кеш вытаскивает данные в одной и той же строке кэша, когда вы получаете доступ к чему-либо в этом кеше -line, требующий меньше отключений в ОЗУ.
Однако то, что вы, вероятно, также видите, это тот факт, что оперативная память (даже при том, что она вызывает оперативную память) все еще предпочитает доступ к линейной памяти.
