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

У современных процессоров архитектуры 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("%in", 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 килобайт).

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. ”

Автор: izard

Источник