Почему использование одной и той же строки кеша из нескольких потоков не вызывает серьезного замедления?

Эта небольшая программа многократно увеличивает четыре соседних байта из четырех разных потоков. Раньше я использовал правило: не используйте одну и ту же строку кэша из разных потоков, так как совместное использование строк в кеше плохо. Поэтому я ожидал, что версия с четырьмя потоками (N=4) намного медленнее, чем версия одного потока (N=1).

Однако это мои измерения (на процессоре Haswell):

Итак, N=4 не намного медленнее. Если я использую разные строки кэша (замените *1 на *64), тогда N=4 станет немного быстрее: 1,1 с.

Те же измерения для атомного доступа (свопинг комментариев в typedef), в той же строке кэша:

Итак, случай N=4 намного медленнее (как я и ожидал). Если используются разные строки кэша, то N=4 имеет схожую производительность как N=1: 3,3 с.

Я не понимаю причины этих результатов. Почему бы мне не получить серьезное замедление в неатомном случае N=4? У четырех ядер есть одинаковая память в их кэшах, поэтому они должны каким-то образом синхронизировать их, не так ли? Как они могут работать почти идеально параллельно? Почему просто атомный случай серьезно замедляется?

Я думаю, мне нужно понять, как память обновляется в этом случае. Вначале в своих кешах нет ядер buffer. После одной итерации for (в fn) все 4 ядра имеют buffer в своих кеш-строках, но каждое ядро записывает другой байт. Как синхронизировать эти строки кэша (в неатомном случае)? Как знает кеш, какой байт грязный? Или есть какой-то другой механизм для обработки этого случая? Почему этот механизм намного дешевле (фактически, он почти свободен), чем атомный?

Ответы

Ответ 1

То, что вы видите, - это в основном эффект перенос отгрузки к загрузке, позволяющий каждому ядру работать в основном независимо, несмотря на совместное использование строки кэша, Как мы увидим ниже, это действительно странный случай, когда больше конфликтов плох, вплоть до точки, тогда еще больше конфликтов внезапно делает вещи очень быстрыми!

Это похоже на то, что будет большим соперничеством и, следовательно, намного медленнее, чем идеально. Однако происходит то, что, как только каждое ядро получает одну незапланированную запись в своем буфере записи, все последующие чтения могут быть удовлетворены из буфера записи (пересылка хранилища), а затем записи просто переходят в буфер. Это превращает большую часть работы в полностью локальную операцию. Линия кэша все еще подпрыгивает между ядрами, но она отцепляется от основного пути выполнения и нужна только для фактического фиксации магазинов сейчас, а затем ¹.

Версия std::atomic не может использовать эту магию вообще, поскольку она должна использовать операции lock ed, чтобы поддерживать атомарность и побеждать буфер хранилища, поэтому вы видите как полную стоимость раздора, так и стоимость долгого -латентность атомных операций ².

Попробуем фактически собрать некоторые доказательства того, что это то, что происходит. В приведенном ниже обсуждении рассматривается версия тега atomic, не использующая atomic, которая использует volatile для принудительного чтения и записи из buffer.

Сначала проверьте сборку, чтобы убедиться, что мы ожидаем:

0000000000400c00 <fn(unsigned char volatile*)>:
  400c00:   ba 00 65 cd 1d          mov    edx,0x1dcd6500
  400c05:   0f 1f 00                nop    DWORD PTR [rax]
  400c08:   0f b6 07                movzx  eax,BYTE PTR [rdi]
  400c0b:   83 c0 01                add    eax,0x1
  400c0e:   83 ea 01                sub    edx,0x1
  400c11:   88 07                   mov    BYTE PTR [rdi],al
  400c13:   75 f3                   jne    400c08 <fn(unsigned char volatile*)+0x8>
  400c15:   f3 c3                   repz ret

Это просто: пять циклов команд с байтовой загрузкой, приращение загруженного байта, хранилище байтов и приращение цикла и условный переход. Gcc совершил неудачный прыжок, разбив sub и jne, блокируя макро-слияние, но в целом это нормально, и латентность пересылки хранилища в любом случае ограничивает цикл.

Затем рассмотрим количество промахов L1D. Каждый раз, когда ядро нужно записывать в линию, которая была украдена, она будет страдать от пропусков L1D, которые мы можем измерить с помощью perf. Во-первых, однопоточный (N=1) случай:

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment 

 Performance counter stats for './cache-line-increment':

       1070.188749      task-clock (msec)         #    0.998 CPUs utilized          
     2,775,874,257      cycles                    #    2.594 GHz                    
     2,504,256,018      instructions              #    0.90  insn per cycle         
       501,139,187      L1-dcache-loads           #  468.272 M/sec                  
            69,351      L1-dcache-load-misses     #    0.01% of all L1-dcache hits  

       1.072119673 seconds time elapsed

Это о том, чего мы ожидаем: в основном нулевые пропуски L1D (0,01% от общего числа, вероятно, в основном из-за прерываний и другого кода за пределами цикла), всего более 500 000 000 обращений (число циклов, которые мы зацикливаем). Обратите также внимание на то, что мы можем легко вычислить число циклов в цикле: около 5.5, что в первую очередь отражает стоимость пересылки между хранилищем и загрузкой, плюс один цикл для приращения, который является цепочкой зависимостей, поскольку одно и то же местоположение повторно обновляется (и volatile означает, что он не может быть вставлен в регистр).

Посмотрим на случай N=4:

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment 

 Performance counter stats for './cache-line-increment':

       5920.758885      task-clock (msec)         #    3.773 CPUs utilized          
    15,356,014,570      cycles                    #    2.594 GHz                    
    10,012,249,418      instructions              #    0.65  insn per cycle         
     2,003,487,964      L1-dcache-loads           #  338.384 M/sec                  
        61,450,818      L1-dcache-load-misses     #    3.07% of all L1-dcache hits  

       1.569040529 seconds time elapsed

Как и ожидалось, L1 загружается с 500 миллионов до 2 миллиардов, так как есть 4 потока, каждый из которых выполняет 500 миллионов нагрузок. Количество промахов L1D также подскочило примерно в 1000 раз, до примерно 60 миллионов. Тем не менее, это число не так много по сравнению с 2 миллиардами нагрузок (и 2 миллиарда магазинов - не показано, но мы знаем, что они есть). Это ~ 33 загрузки и ~ 33 магазина для каждой промахи. Это также означает 250 циклов между каждым промахом.

Это действительно не соответствует модели линии кэша, которая скачкообразно перескакивает между ядрами, где, как только ядро получает строку, это требует другое ядро. Мы знаем, что линии отскакивают между ядрами, разделяющими L2, возможно, на 20-50 циклов, поэтому отношение одного прохода каждые 250 циклов кажется низким.

Две гипотезы

Несколько идей spring для понимания описанного выше поведения:

Возможно, вариант протокола MESI, используемый в этом чипе, является "умным" и признает, что одна строка горячая среди нескольких ядер, но только небольшая работа выполняется каждый раз, когда ядро получает блокировку и линию тратит больше времени на перемещение между L1 и L2, чем на самом деле удовлетворяющий нагрузкам и запасам для некоторого ядра. В свете этого некоторые интеллектуальные компоненты в протоколе согласованности решают принудительно выполнить какое-то минимальное "время владения" для каждой строки: после того, как ядро получит строку, она будет поддерживать ее для N циклов, даже если это требуется другим ядром ( другие ядра просто должны ждать).

Это поможет сбалансировать накладные расходы на пинг-понг в кеш-памяти с реальной работой за счет "справедливости" и отзывчивости других ядер, вроде компромиссов между несправедливыми и справедливыми шлюзами и противодействием эффект [описанный здесь], где более быстрый и более справедливый протокол согласованности, тем хуже могут работать некоторые (обычно синтетические) циклы.

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

Некоторые тесты

Попробуйте выделить два случая с некоторыми изменениями.

Чтение и запись отличительных байтов

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

Как насчет того, что мы просто читаем из местоположения x, а затем пишем в папку x + 1? Мы дадим каждому потоку два последовательных местоположения (т.е. thr[i] = std::thread(&fn, &buffer[i*2])), чтобы каждый поток работал на двух частных байтах. Модифицированный fn() выглядит следующим образом:

for (int i=0; i<500000000; i++)
    unsigned char temp = p[0];
    p[1] = temp + 1;
}

Контур ядра почти идентичен предыдущему:

  400d78:   0f b6 07                movzx  eax,BYTE PTR [rdi]
  400d7b:   83 c0 01                add    eax,0x1
  400d7e:   83 ea 01                sub    edx,0x1
  400d81:   88 47 01                mov    BYTE PTR [rdi+0x1],al
  400d84:   75 f2                   jne    400d78

Единственное, что изменилось, это то, что мы пишем [rdi+0x1], а не [rdi].

Теперь, как я уже упоминал выше, цикл исходного (такого же местоположения) на самом деле работает довольно медленно примерно на 5,5 циклов на итерацию даже в случае однопоточного случая в лучшем случае из-за связанной с циклом зависимости load->add->store->load.... Этот новый код нарушает эту цепочку! Загрузка больше не зависит от хранилища, поэтому мы можем выполнять все в значительной степени параллельно, и я ожидаю, что этот цикл будет работать примерно на 1,25 цикла на итерацию (5 инструкций/ширина процессора 4).

Здесь однопоточный корпус:

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment 

 Performance counter stats for './cache-line-increment':

        318.722631      task-clock (msec)         #    0.989 CPUs utilized          
       826,349,333      cycles                    #    2.593 GHz                    
     2,503,706,989      instructions              #    3.03  insn per cycle         
       500,973,018      L1-dcache-loads           # 1571.815 M/sec                  
            63,507      L1-dcache-load-misses     #    0.01% of all L1-dcache hits                 

       0.322146774 seconds time elapsed

Итак, около 1,65 циклов на итерацию ³ примерно в три раза быстрее, чем приращение того же места.

Как насчет 4 потоков?

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment 

 Performance counter stats for './cache-line-increment':

      22299.699256      task-clock (msec)         #    3.469 CPUs utilized          
    57,834,005,721      cycles                    #    2.593 GHz                    
    10,038,366,836      instructions              #    0.17  insn per cycle         
     2,011,160,602      L1-dcache-loads           #   90.188 M/sec                  
       237,664,926      L1-dcache-load-misses     #   11.82% of all L1-dcache hits  


       6.428730614 seconds time elapsed

Итак, это примерно в 4 раза медленнее, чем тот же случай местоположения. Теперь, а не просто немного медленнее, чем однопоточный, он примерно в 20 раз медленнее. Это утверждение, которое вы искали! Теперь также, что количество промахов L1D также увеличилось в 4 раза, прекрасно объяснив ухудшение производительности и соглашаясь с идеей, что, когда пересылка между хранилищем и загрузкой не может скрыть конкуренции, пропуски будут увеличиваться на много.

Увеличение расстояния между магазинами

Другим подходом было бы увеличить расстояние во времени/инструкции между магазином и последующей загрузкой. Мы можем сделать это, увеличивая SPAN последовательные местоположения в методе fn(), а не всегда в одном и том же месте. Например, если SPAN равно 4, последовательно увеличивайте 4 местоположения, например:

for (long i=0; i<500000000 / 4; i++) {
    p[0]++;
    p[1]++;
    p[2]++;
    p[3]++;
}

Обратите внимание, что мы все еще увеличиваем 500 миллионов местоположений, просто увеличивая приращения между 4 байтами. Интуитивно вы ожидаете, что общая производительность будет увеличиваться, так как теперь у вас есть SPAN параллельная зависимость с длиной 1/SPAN, поэтому в приведенном выше случае вы можете ожидать, что производительность улучшится в 4 раза, поскольку 4 параллельные цепи могут продолжаться примерно в 4 умноженной на общую пропускную способность.

Здесь мы фактически получаем время (измеренное в циклах) для 1 потока и 3 потока ⁴ для SPAN значений от 1 до 20:

Первоначально вы видите существенное увеличение производительности как в одномодовых, так и в многопоточных случаях; увеличение от a SPAN от одного до двух и трех близко к теоретически ожидаемому в случае совершенного parallelism для обоих случаев.

Однопоточный случай достигает асимптоты примерно в 4,25 раза быстрее, чем запись в одном месте: на данный момент латентность пересылки хранения не является узким местом, а другие узкие места заняли (максимальное количество IPC и сохранение порта, в основном).

Многопоточный корпус сильно отличается от этого! Как только вы нажмете SPAN около 7, производительность быстро ухудшится, выровнявшись примерно в 2,5 раза хуже, чем случай SPAN=1 и почти в 10 раз хуже по сравнению с лучшей производительностью в SPAN=5. Случается, что остановка пересылки между загрузкой и загрузкой происходит из-за того, что хранилище и последующая загрузка достаточно далеко друг от друга во времени/циклах, которые хранилище удалили на L1, поэтому нагрузка фактически должна получить линию и участвовать в MESI.

Также построены пропуски L1D, которые, как упоминалось выше, указывают на "переводы строк кеша" между ядрами. Однопоточный корпус по существу равен нулю, и они не связаны с производительностью. Однако производительность многопоточного корпуса в значительной степени отслеживает пропуски кэша. При значениях SPAN в диапазоне от 2 до 6, где сохранение хранилища все еще работает, пропорционально меньше промахов. Очевидно, что ядро способно "накапливать" больше хранилищ между каждой передачей строки кэша, поскольку цикл ядра быстрее.

Другим способом думать об этом является то, что в рассматриваемом случае промахи L1D в основном постоянны в единицу времени (что имеет смысл, поскольку они в основном связаны с задержкой L1- > L2- > L1, а также некоторыми служебными данными протокола согласованности), поэтому чем больше работы вы можете выполнять между линиями передачи кеша, тем лучше.

Здесь код для многопролетного случая:

void fn(Type *p) {
    for (long i=0; i<500000000 / SPAN; i++) {
        for (int j = 0; j < SPAN; j++) {
            p[j]++;
        }
    }
}

bash script для запуска perf для всех значений SPAN от 1 до 20:

PERF_ARGS=${1:--x, -r10}

for span in {1..20}; do
    g++ -std=c++11 -g -O2 -march=native -DSPAN=$span  cache-line-increment.cpp  -lpthread -o cache-line-increment
    perf stat ${PERF_ARGS} -e cycles,L1-dcache-loads,L1-dcache-load-misses,machine_clears.count,machine_clears.memory_ordering ./cache-line-increment
done

Наконец, "транспонируйте" результаты в правильный CSV:

FILE=result1.csv; for metric in cycles L1-dcache-loads L1-dcache-load-misses; do { echo $metric; grep $metric $FILE | cut -f1 -d,; } > ${metric}.tmp; done && paste -d, *.tmp

Окончательный тест

Вот окончательный тест, который вы можете сделать, чтобы показать, что каждое ядро эффективно выполняет большую часть своей работы наедине: используйте версию теста, в которой потоки работают в одном месте (что не меняет характеристики производительности) проверьте сумму окончательных значений счетчика (вам нужно int счетчики, а не char). Если бы все было атомным, у вас была бы сумма в 2 миллиарда, а в неатомном случае, насколько близко общее значение к этому значению является приблизительным показателем того, как часто ядра проходят по линиям. Если ядра работают почти полностью в частном порядке, стоимость будет ближе к 500 миллионам, чем 2 миллиарда, и я предполагаю, что вы найдете.

С еще более умным приращением вы можете даже отслеживать каждый поток, как часто значение, которое они увеличивали, приходилось с их последнего приращения, а не на увеличение числа потоков (например, с помощью нескольких бит значения, чтобы зашифровать идентификатор потока). С еще более умным тестом вы могли бы практически восстановить тот способ, по которому линия кэша перемещалась между ядрами (есть ли шаблон, например, делает ли ядро A предпочтительным передать основное ядро B?), И какие ядра внесли наибольший вклад в окончательное значение, и др.

Все оставлено как упражнение:).

¹ Кроме того, если у Intel есть коалесцирующий буфер хранилища, где более поздние магазины, которые полностью перекрывают предыдущие, убивают более ранние хранилища, ему нужно было бы только одно значение присвоить L1 (последний магазин ) каждый раз, когда он получает линию.

² Вы не можете разделить эти два эффекта здесь, но мы сделаем это позже, победив переадресацию хранилища к загрузке.

³ Немного больше, чем я ожидал, возможно, плохое планирование, ведущее к давлению порта. Если gcc будет плавать только все sub и jne, он будет работать в 1,1 цикла на итерацию (все же хуже, чем ожидаемый 1.0). Он будет делать то, что я использую -march=haswell вместо -march=native, но я не собираюсь возвращаться и изменять все числа.

⁴ Результаты также выполняются с 4 потоками: но у меня только 4 ядра, и я использую дерьмо, как Firefox, в фоновом режиме, поэтому использование 1 меньше ядра делает измерения намного менее шумными, Измерение времени в циклах также помогает.