Действительно ли у каждого ядра есть «свой собственный» кэш первого и второго уровней?

У современных процессоров архитектуры Core i7 существует очевидный, документированный, но отчего-то не очень известный даже среди многих специалистов сценарий priority inversion. Его я опишу в этом посте. В нем есть код на С, три диаграммы, и некоторые подробности работы кэшей в процессорах архитектуры Core i7. Никаких покровов не срывается, вся информация давно общедоступна.

Priority inversion – ситуация, когда низкоприоритетный процесс может блокировать или замедлять высокоприоритетный. Обычно имеется в виду очередность доступа к исполнению на ядре для высокоприоритетного кода относительно низкоприоритетного. С этим должно неплохо справляться ядро ОС. Однако помимо вычислительных ядер, которые несложно распределять посредством affinity и MSI-X, в процессоре есть ресурсы, общие для всех задач – контроллер памяти, QPI, общий кэш третьего уровня, PCIe устройства. В вопросы PCIe я углубляться не буду, т.к. не являюсь экспертом в данной теме. Priority inversion на почве доступа к памяти и QPI я давно не наблюдал – пропускной способности современного многоканального контроллера как правило хватает и высокоприоритетным, и низкоприоритетным задачам. Остановлюсь на кэшах.

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

На этом достаточно высоком уровне абстракции разница между Nehalem, Westmere, Sandy Bridge, Ivy Bridge и Haswell незаметна. Кстати, самое подробное описание как это все устроено внутри Sandy Bridge можно прочитать в статье Хеннеси (да, того самого).

Мы видим, что кэш третьего уровня (LLC), самый большой, одновременно обслуживает все ядра – и те, которые «рисуют формочки» — низкоприоритетные процессы, и те, на которые приходят прерывания от внешнего устройства или local APIC timer, которые надо как можно быстрее обработать и выдать результат. Eviction policy кэша последнего уровня – некое приближение к LRU. Следовательно, чем больше и чем чаще некое ядро пользуется кэшем, тем большая часть LLC ему достанется. Приоритеты? Какие приоритеты?? Кстати, не очень важные задачи очень часто программируются не так аккуратно, как высокоприоритетные, и поэтому требуют особенно много памяти и кэша. А высокоприоритетная задача зачастую ждет внешнего события, в то время как ее данные и код вытесняются из LLC. Я как-то об этом уже писал, но в комментариях к тому посту неправильно ответил на вопрос об эксклюзивности L1/L2 кэша.

Если смотреть на диаграмму выше, то кажется, что у каждого ядра есть «свой» кэш, объемом как минимум 256 килобайт. Более чем достаточно для .text и .data многих realtime задач. Ну хотя бы на хранение 32кб данных + 32кб кода в кэше с временем отклика в несколько тактов всегда можно рассчитывать? Это несложно проверить.

Отключаю гипертрединг и power management. Запускаю следующий микробенчмарк:

Helper functions

#define POOL_SIZE_L1D_LINES 512 #define POOL_SIZE_L2_LINES 8192 // This can differ on your CPU. Check with CPUID or some system diagnostics tool #define POOL_SIZE_LLC_LINES 6*1024*1024/64   // Yes, I waste 3/4 of space for the sake of test simplicity // 1 cache line == 1 linked list item.  // Pointer length is hard coded to 8 bytes (Intel 64) struct list_item {     unsigned long long int tick;     list_item *next;     unsigned char padding[48]; };  // Build a linked list of size N with pseudo-random pattern void build_list(list_item *head, int N, int A, int B) {     int C = B;     list_item *current = head;     for (int i = 0; i < N - 1; i++) {         current->tick = 0;         C = (A*C + B) % N;         current->next = (list_item*)&(head[C]);         current = current->next;     } }  // Touch first N elements in a linked list void warmup_list(list_item* current, int N) {     bool write = (N > POOL_SIZE_L2_LINES) ? true : false;     for(int i = 0; i < N - 1; i++) {         current = current->next; // No write is needed to keep a line in L1, but looks like it is needed to keep it in L2!!         if (write) current->tick++; // FIXME AK: to check on IVB, HSW     } } 

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

Теперь на ядре номер 2 запускаем обход списка, и измеряем, сколько в среднем времени требуется на каждую итерацию.

Linked list traversal speed measurements

void measure(list_item* head, int N) {     unsigned __int64 i1, i2, avg = 0;      for (int j = 0; j < 50; j++) {         list_item* current = head; #if WARMUP_ON         while(in_copy) warmup_list(head, N); #else         while(in_copy) spin_sleep(1);  #endif         i1 = __rdtsc();         for(int i = 0; i < N; i++) {             current->tick++;             current = current->next;         }         i2 = __rdtsc();         avg += (i2-i1)/50;         in_copy = true;     }     printf("%i\n", avg/N); } 

Код потока, измеряющего время прохода по спискам различных размеров будет вот такой:

Measurements for different linked list sizes

// We initialize the linked list only once, and make it big enough to make sure  // we do not observe effects of spatial locality but only effects of temporal locality // Magic numbers 509, 509 <= Hull-Dobell Theorem criteria build_list(head, POOL_SIZE_LLC_LINES*2, 509, 509);  for (int i = 10; i < POOL_SIZE_L1D_LINES; i+=5) {     warmup(head, i);     measure(head, i); };  for (int i = POOL_SIZE_L1D_LINES; i < POOL_SIZE_L2_LINES; i+=50) {     warmup(head, i);     measure(head, i); };  for (int i = POOL_SIZE_L2_LINES; i < POOL_SIZE_LLC_LINES*2; i+=1000) {     warmup(head, i);     measure(head, i); }; 

Добавим второй поток, забивающий кэш третьего уровня: пусть крутится на ядре номер 3, и копирует 18Мб данных туда-сюда. 18Мб – чтобы наверняка забить LLC. Пусть он синхронизируется с первым потоком, чтобы почти в любой момент времени лишь один из них активно работал с кэшем. (Я в курсе, что реализация спинлока неправильная и неэффективная, и все работает только благодаря подходящему таймингу.)

A thread that runs on another core and consumes LLC

list_item *area1 = (list_item *)malloc(POOL_SIZE_LLC_LINES*64*2); list_item *area2 = (list_item *)malloc(POOL_SIZE_LLC_LINES*64*2);  while (true) {     while(!in_copy) spin_sleep(1);  #if DISRUPT_ON     memcpy(area1, area2, POOL_SIZE_LLC_LINES*64*3);     memcpy(area2, area1, POOL_SIZE_LLC_LINES*64*3); #else     spin_sleep(10);  #endif     in_copy = false; }; 

Проведем три вида измерений:

• Baseline, «красный» тест, показывает скорость обхода списка в благоприятных условиях — второй поток не использует кэш.
• Плохой вариант, «синий» тест, показывает, что будет, если второй поток успеет забрать себе весь объем LLC, пока первый поток висит в спинлоке.
• Наконец, «зеленый» тест показывает, что будет, если первый поток во время ожидания будет периодически читать свои данные.

Для контроля я также запускал тест, в котором данные потока-вредителя умещались в его «собственный» L2. Как и ожидалось, в этом случае никакого влияния на скорость обхода списка первым потоком не было. (Теоретически могли быть видны conflict miss’ы, но я их не наблюдал)

Вот результаты измерений:

По горизонтали — количество элементов в списке. По вертикали — циклы CPU, потраченые на проход через один элемент. Интересно, что чтобы получить «ступеньки» (график, на котором видны границы кэшей) надо лишь чуть-чуть изменив бенчмарк, добавив немного spatial locality.

Для сравнения, на компьютере, на котором я гонял этот тест, времена доступа к элементам иерархии памяти следующие:

• L1D hit = 4 цикла,
• L2 hit = 11 циклов,
• LLC hit = 31 цикл,
• DRAM hit = ~100 циклов,

Время, потраченое на один переход по списку, пропорционально
L1D_hit*P(L1D_hit) + L2_hit*P(L2_hit) + LLC_hit*P(LLC_hit) + DRAM_hit*P(DRAM_hit), где P — вероятности нахождения следующего элемена списка в данном уровне кэша. Т.е.
P(L1D_hit) + P(L2_hit) + P(LLC_hit) + P(DRAM_hit) = 1
Конкретное распределение вероятностей зависит от величины списка относительно кэшей, и может быть измерено при помощи Vtune, oprofile или Linux perf. Например, вот измерение вероятностей при помощи Vtune для фиксированой длины списка, равной 16384 элементов (512 килобайт).

	undisturbed	disturbed	warmup
L1 hit%	0.08	0	63
L2 hit%	72	0.07	0.1
LLC hit%	25	2.6	22
DRAM hit%	3	97	15
DTLB miss%	21	66	37

Vtune подтверждает, что разница в производительности между «синим» и «зеленым» вариантом кроется в пропорции промахов по кэшам различных уровней, вызванных переходом к очередному элементу списка. Видно, что если данные высокоприоритетного потока были вытеснены из кэша третьего уровня, они автоматически инвалидируются в кэшах первого и второго уровня соответствующего ядра. Однако сами цифры измеренных вероятностей были для меня неожиданными. В «синей» колонке сюрпризов нет, а в красной я ожидал больше попаданий в L1, а в «зеленой» — гораздо больше попаданий в L2.

Если бы первый поток просыпался по прерыванию, в «синем» варианте даже IDT и код ISR для него приходилось бы тащить из памяти, так как он был бы уже вытеснен из L1I, L2, и LLC. К моему огромному сожалению, у современных процессоров архитектуры Core i7 нет возможности «залочить» часть LLC для эксклюзивного использования определенным ядром. Поэтому единственный способ избежать удаления важных данных из LLC, и, как следствие, из L2 и L1 — переодически их обновлять, даже если они в данный момент и не нужны.

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

Уфф! Кажется, я только что написал большой текст, суть которого можно было бы поместить в твит: “When a cache line is evicted from LLC, the same cache line is evicted from L1 and/or L2. So warming up cache could be useful. ”