местах. Но PowerPC relaxed все равно будет медленным для этого теста, потому что он по-прежнему требует, чтобы хранилище фиксировало L1D, а не просто находилось в буфере хранилища, так что вы могли бы испытать пинг-понг в строке кэша.

трите на этот фрагмент:

#include <atomic>
#include <thread>

typedef volatile unsigned char Type;
// typedef std::atomic_uchar Type;

void fn(Type *p) {
    for (int i=0; i<500000000; i++) {
        (*p)++;
    }
}

int main() {
    const int N = 4;

    std::thread thr[N];
    alignas(64) Type buffer[N*64];

    for (int i=0; i<N; i++) {
        thr[i] = std::thread(&fn, &buffer[i*1]);
    }

    for (int i=0; i<N; i++) {
        thr[i].join();
    }

}

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

Тем не менее, это мои измерения (на процессоре Haswell):

N = 1: 1 секN = 4: 1,2 с

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

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

N = 1: 3,1 сN = 4: 48 с

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

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

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

 Jesper Juhl24 окт. 2017 г., 22:05
Я бы назвал 1,0 против 1,2 с (увеличение времени выполнения на 20%) серьезным замедлением для любого кода, где важна производительность.
 geza24 окт. 2017 г., 22:06
@JesperJuhl: это несерьезно по сравнению с замедлением атомного дела. 20% против 1400%.
 geza24 окт. 2017 г., 22:02
@ Мистик: это не так. этоvolatile, но я также проверил сборку: она использует правильную загрузку / сохранение памяти.
 Richard Byron25 окт. 2017 г., 04:52
Это будет зависеть от процессора, но сохранение для загрузки может означать, что кеш здесь даже не работает.
 David Schwartz27 окт. 2017 г., 00:52
Ваша тестовая программа на самом деле ничего не тестирует, так как четыре потока просто топтались друг на друга случайным образом. Окончательные значения этих приращений непредсказуемы.

Ответы на вопрос(2)

Решение Вопроса

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

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

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

Давайте попробуем собрать некоторые доказательства того, что это происходит. Все приведенные ниже обсуждения касаются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 миллиардов, так как каждый из них выполняет 500 миллионов нагрузок. Количество L1Dпромахов также подскочил примерно в 1000 раз, до 60 миллионов. Тем не менее, это число невелико по сравнению с 2 миллиардами загрузок (и 2 миллиардами магазинов - не показаны, но мы знаем, что они есть). Это ~ 33 загрузки и ~ 33 магазина длякаждый Мисс. Это также означает 250 циклов между каждым промахом.

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

Две гипотезы

Пара идей приходит на ум для вышеописанного поведения:

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

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

Теперь я никогда не слышал ничего подобного (и предыдущая ссылка показывает, что, по крайней мере, в эпоху Песчаного Мостанапротив направление), но это конечновозможно!

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

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

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

Чтение и запись, различающиеся байты

Очевидный подход заключается в изменении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 циклов за итерацию3отри раза быстрее по сравнению с увеличением того же места.

Как насчет 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 потока4, заSPAN значения от 1 до 20:

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

Однопоточный регистр достигает асимптоты примерно в 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 для запуска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?) И какие ядра внесли наибольший вклад в конечное значение, и т.п.

Это все осталось в качестве упражнения :).

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

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

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

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

 BeeOnRope28 окт. 2017 г., 02:38
@PeterCordes - ну да, я использую «старую» версиюgcc (5.4.0), поставляемый с моим дистрибутивом, Ubuntu 16.04, который был выпущен почти через год после выпуска Skylake (и, несомненно, через год после того, как стали доступны идентификаторы семейства и модели). Настолько "старый" в том смысле, что он не поддерживает Skylake, но вполне "нормальный" в том смысле, что это просто мой дистрибутивgcc вероятно, именно так его использует подавляющее большинство разработчиков. Так что да, это абсолютно отстой, что-march=native молча возвращается к некоторому полностью устаревшему профилю настройки.
 geza27 окт. 2017 г., 01:23
Каков типичный размер этого буфера записи?
 BeeOnRope28 окт. 2017 г., 02:42
Я имею в виду, что совет «просто использовать -march = native» часто может быть совершенно неверным в зависимости от такого поведения: он применим только к людям с достаточно новымgcc версии, другие люди будут молча генерировать иногда гораздо худший код. Это также приводит к странной ситуации, когда вы компилируете материал из исходного кода и обновляете свой компьютер, а затем материал начинает работать медленнее, поскольку материал перекомпилируется, потому что-march=native не создает плохой код (но существующие двоичные файлы, скомпилированные на старом компьютере, отлично работают на новом компьютере, потому что настройка для старой платформы - хорошая ставка для новой).
 geza27 окт. 2017 г., 01:21
Спасибо BeeOnRope, теперь я действительно понимаю, что происходит, отличный ответ! Может быть, вы пропустилиperf результаты дляN=4 случайно? (не беспокойтесь, если нет, ваш ответ понятен без него)
 BeeOnRope27 окт. 2017 г., 01:38
@geza - извините, отвлекся на IRL и усек мой ответ. Я все еще заканчиваю - там не так много "доказательств" :). Очередь записи (или буфер хранилища) составляет 42Haswell.

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

Изменчивая версия не делает никаких связей видимыми для других ядер, поэтому не пытается синхронизировать память, чтобы она была видна на других ядрах. Для многопоточной системы, использующей C ++ 11 или новее, volatile не является механизмом связи между потоками.

 Peter Cordes27 окт. 2017 г., 05:05
На x86 каждая атомарная инструкция RMW также является полным барьером (т.е.fetch_add(1, mo_seq_cst) компилируется в точно такой же asm на x86 какfetch_add(1, mo_relaxed), если только нет переупорядочения во время компиляции, которое позволяет расслабление.) Это не относится к другим ISA, таким как PowerPC, где вы можете делать атомарный RMW, не заказывая магазины дляДругие местах. Но PowerPC relaxed все равно будет медленным для этого теста, потому что он по-прежнему требует, чтобы хранилище фиксировало L1D, а не просто находилось в буфере хранилища, так что вы могли бы испытать пинг-понг в строке кэша.
 geza24 окт. 2017 г., 22:26
Как процессор синхронизирует кэши? Есть ли в нем грязные флаги на уровне байтов? Это было бы объяснением этого поведения (если нет, как кеш может узнать, какой байт является допустимым, а какой - нет?)
 WhiZTiM24 окт. 2017 г., 22:30
@geza, вы можете в Google "Протоколы когерентности кэша"
 LWimsey24 окт. 2017 г., 23:07
Атомная версия не просто медленнее из-за заборов, но потому, что приращение выполняется атомарно (RMW). Это требует, чтобы строка кэша была заблокирована во время операции, эффективно блокируя доступ к ней со стороны любого другого потока. Тот же код, использующий атомарные операции в разных строках кэша, может быть в 10 раз быстрее
 user366619724 окт. 2017 г., 22:43
@geza Вы также можете быть удивлены тем, что ваши потоки вообще не должны работать на разных процессорных ядрах NUMA. Таким образом, они все еще могут жить в той же иерархии L1d / L2 / L3-cache (s).

Ваш ответ на вопрос