company_banner

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

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

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

    Рассмотрим диаграмму с кэшами в процессорах архитектуры Core i7 третьего поколения. Впрочем, даже не важно, какого поколения.
    image
    На этом достаточно высоком уровне абстракции разница между 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 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;
    };
    


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

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

    Вот результаты измерений:
    image
    По горизонтали — количество элементов в списке. По вертикали — циклы 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. Впрочем, последнее отчасти объясняет непонятный пик на зеленом графике в районе 16к элементов списка.

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

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

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

    Intel

    154,00

    Компания

    Поделиться публикацией
    Комментарии 31
      0
      Так чем, в итоге, это объясняется? Что мешает процессору оставить кэшлайн в L1/L2?
        +2
        Тем, что L3 (LLC) в текущих реализациях Core i7 — fully inclusive of L1 and L2. То есть если линия вытеснена из LLC, LLC автоматически посылает сигнал об изменении статуса этих данных на Invalid в нижележащие кэши.

        Для сравнения, если по какой-то причине линия пропадает из L2, в L1 она все еще может оставаться.
          0
          О, вот это интересно — т.е. уже не полностью inclusive? Есть исключения?
            0
            Да, описано в SW Optimization guide (#248966, 2.3.4). L2 не обязательно включает весь L1, но L3 включает L1 I&D и L2.
              0
              А там описано почему выбрана именно такая политика? (Страшновато за него браться)
                +1
                Нет, не описано. Но можно нагуглить несколько релевантных академических статей, в том числе опубликованых архитекторами Intel по запросу «L1 L2 LLC inclusive».

                Обычно архитекторы просто прогоняют на модели нового дизайна огромный синтетический бенчмарк и пытаются выбрать вариант политики с лучшей производительности и наименьшим расходом энергии.
          0
          Кэши у интела inclusive — то, что есть в L1 обязательно должно быть и в L2 и в L3. en.wikipedia.org/wiki/CPU_cache#Exclusive_versus_inclusive
            0
            Насколько мне известно, у современных процессоров Intel кэш строго инклюзивный, т.е. если данные есть в кэше меньшего уровня, то гарантируется, что они также есть на последующих уровнях.
            Я думаю, что с эксклюзивным кэшем AMD все не так печально. Но, к сожалению, под рукой нет компьютера с АМД, чтобы проверить.
            0
            Извините за прямолинейность, но я не увидел в статье явного ответа на вопрос в заголовке «Действительно ли у каждого ядра есть «свой собственный» кэш первого и второго уровней?».
              +5
              В двух словах — они есть, но не совсем «свои собственные». То есть есть вероятность, что ядра в некоторых условиях могут вытеснять чужые данные из чужих L1, L2 кэшей.
                +2
                действительно, информация лежит на поверхности, и если вдуматься, то разделяемый LLC может позволить одному ядру обнулить L1/L2 другому.
                отличный пост! спасибо.
              0
              Несколько необычно видеть в блоге Intel пост о попытке разобраться в архитектуре i7. :)
                +1
                Это скорее подробное разжевывание тезиса о том, что LLC — inclusive. Что описано в документации. Несмотря на это, мне часто приходится объяснять это клиентам, которые ссылаются на первую диаграмму: «вот у вас же в powerpoint нарисовано, что у каждого ядра есть свой кэш. Куда же из него подевались наши данные, почему кэш миссы?».
                0
                Саша, ты лучше скажи мне другое. Левенталь говорил, что похожим образом легко сделать eviction для L1 instruction. Но наскоком у меня такой тест не вышел. Сделаешь? ;)
                  0
                  Мне кастомер жаловался, что у него это происходит. Как раз собирался воспроизводить. На след. неделе попробую, если получится напишу тебе.
                    0
                    Спасибо. Я не совсем понял про изменение данных. Если ядро меняет данные, то данные сразу меняются в LLC и становятся автоматически видны всем остальным ядрам? Разве ядро не должно менять данные в L1/L2? Если так то каким образом изменения данных сбрасываются из L1/L2 в LLC?
                      0
                      Cache coherency, и что происходит при записи в L1 в статье я не рассматривал. 2 потока из теста работают над непересекающимися областями данных, которые, однако, конкурируют за место в LLC. Единственный элемент, в который пишут оба потока — спинлок.

                      В статье Хеннеси, на которую я сослался в тексте, есть инфа, что происходит при L1 hit on store.

                      +2
                      Немного оффтоп:
                      Ребята, подскажите чего бы почитать на эту тему для newbie?
                      Статья безумно интересная, но я и половины не понимаю. Спасибо
                        +2
                        Computer Organization and Design;
                        Computer Architecture: A Quantitative Approach
                        Обе книги написаны Хеннеси(которого я уже упоминал) и Паттерсоном.

                        Я не сказал бы, что они для newbie, но с другой стороны, они (особенно первая) не требует каких-то prerequisites.
                          0
                          Спасибо, буду изучать
                          0
                          Серьёзный подход. Проникся. Интересно. Спасибо.
                            +2
                            Что-то мне подсказывает, что этот пост связан с новой возможностью «L3 Cache QoS», о которой вы могли бы рассказать.
                              0
                              А где вы слышали о «новой возможности «L3 Cache QoS» »??
                                +2
                                Вот здесь, страница 3-154. CPUID leaf 0xF (ecx = 0):
                                EDX Bit 01: Supports L3 Cache QoS if 1.
                                  +2
                                  Очень интересно! В официальном документе упомянули фичу, но ничего не написали о том, как ее использовать. Если внимательнее почитать, там же можно найти более подробную ссылку на CQoS monitoring. Вы, очевидно, ссылаетесь на CQoS control. Если бы такая фича существовала и была публична, я бы с радостью запостил статью на публичном ресурсе — Хабре.
                              0
                              Никто не обидится, если я не в свою песочницу залезу?
                              Вот если я обычный обыватель и купил себе десктоп на LGA2011 и 3960X — 6 ядер, 4 канала памяти, полный фарш во всем остальном, и даше хакинтош было дело попробовал — Mac OS встал как родной, чувствую себя уверенно, весь такой, а тут эта статья… Я правильно понимаю, что это всё может быть сильно обесценено единственным «грамотным» индусским драйвером устройства под виндой?
                              Второй вопрос это офф-топик, но вытекает из первого — я уже устал себя чувствовать уверенно на 2011 и 39хх — линейка совершенно не обновляется.
                              Прошло уже полтора «тик-така» по процессу с того времени как купил, но в топовом сегменте десктопов ничего не изменилось.
                              А у меня же подруги тупые — они не понимают что этот комп до сих пор «самый крутой процессор». Для них этот комп уже такой-же старый, как дата моего рождения в паспорте. Скоро мне вообще никто не даст! О_о
                              [irony kaput]
                              А если серьезно, есть какие-то доступные средства мониторинга такой оказии кэша из-за ПО третьих лиц? Может какой-то статистический анализ, выявляющий статистически значимые выбросы при работе определенного ПО или драйвера?
                              И что с перспективой LGA2011?
                              Заранее прошу прощения от низкоуровневых гуру, если я чего-то очевидного не знаю, я уже много лет в прикладном ПО, а в этом блоге спасаюсь от минерализации своего мозга в углерод к компании окаменелостоей динозавров. (и не хочу через миллион лет стать процесором телефона у продавца в Макдональдсе)
                                +1
                                На десктопных нагрузках вы вряд-ли заметите этот эффект.
                                1. Речь идет о микросекундах.
                                2. У десктопных нагрузок сложнее проявить этот эффект, так как у них есть spatial locality, и так как менее приоритетным задачам дается меньше времени на CPU, следовательно, у них меньше возможности вытеснить чужие данные.
                                3. Измерять можно при помощи Intel Vtune, но учитывая пункты 1,2 — просто незачем.

                                По поводу вашего вопроса о современном железе, я не знаю ответа, т.к. не интересуюсь десктопным железом. Может быть, мои коллеги ответят.
                                  –2
                                  Знаете, обидно было прочитать, что я десктоп пользователь, и поэтому выходит человек второго сорта.
                                  У вас мог бы возникнуть вопрос, нафиг мне 2011 с топовым Зеоном на борту понадобился, но вы этот вопрос не задали, но сразу отнесли меня к людям второго сорта, которыми можно пренебречь с их ничтожными «десктопами».
                                  Это официальная политика Интел сейчас, пренебрегать десктопами, на которые люди потратили десятки тысяч рублей ради топовых показателей, потому-что не имеют возможности покупать часы на суперкомпьютерах? Мои микросекунды менее нужны чем элите? Меня похоже в мягкой форме послали на#ер.
                                  Это официальная политика Intel сейчас?
                                    +3
                                    Я, к сожалению, не имею права выражать официальную позицию Интел.

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

                                    Лет 10 назад, я тоже следил за десктопными компьютерами, но как-то перегорел. Теперь слежу только за тем, что нужно по работе — за микроархитектурой и за платформами своего сегмента.

                                    По поводу микросекунд. Архитектура Интел всегда в первую очередь оптимизировалась под максимальную throughput производительность. В задачах, где важно время отклика (промышленность, алгоритмический трейдинг), часто требуется отдельная работа с софтом для выгадывания микросекунд. Так как человек — система не очень быстро реагирующая, десктопные нагрузки никто не оптимизирует в области микросекунд. Обычно речь идет о десятках миллисекунд.
                                      0
                                      Я вас немного потроллил конечно ))
                                      На самом деле мой софт лишь составляет тональную карту звуковых треков — задача недостойная суперкомпьютеров по важности, но числомолотилка серьезная, сильно упирается в количество ядер (тут я надеюсь как кодер не налажал), и в кеширование проца. Методом «тыка» подбираю размер обрабатываемых блоков и количество потоков, вот и влез в этот топик.
                                      То что я делаю, это конечно неправильно, и это переоптимизация под конкретную конфигурацию компа, я знаю.
                                      Но других десктопных Зеонов кроме 39хх я не знаю, раньше были Mac Pro, но похоже Apple похоронила эту линейку. В связи с чем и возник вопрос про 2011, ходят слухи, — был ли это неудачный проект для Mac Pro, и после отказа Apple были просто распроданы запасы, и теперь это тупиковая ветка и бесперспективный сокет?

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

                              Самое читаемое