Почему я должен явно сделать операцию атомарной?

Question

Рассмотрим следующий код:

int x=0;

#pragma omp parallel num_threads(4) default(none) shared(x)
 {
  for(int i=0; i<1000; ++i)
   x++;
 }
cout << x << endl;

Ожидаемый выход составляет 4000. Однако обычно я вижу что-то между 2500-3500.Я уже знаю почему (потому что я не сделал эту операцию атомарной).До сегодняшнего дня я думал, что это полностью приемлемо, но потом мне пришло в голову:

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

Теперь мне интересно, зачем мне получать какой-либо другой результат?чем 4000, даже если я не указываю, что это атомарная операция?

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

РЕДАКТИРОВАТЬ:
То, что я думаю о протоколах когерентности кэша, объясняется на следующем рисунке, взятом из здесь (стр. 19):

Теперь Я знаю эта цифра для многопроцессорных (а не многоядерных) систем, использующих битовый векторный протокол, но я думаю, что что-то близкое к этому используется в процессорах Intel, которые используют MESIпротокол.Если это так, то читатель не получит копию запрошенного значения, пока не будут подтверждены все недействительные значения.Поправьте меня если я ошибаюсь.Я пытался выяснить детали того, как работает протокол MESI, но я не нашел много.

Answer 1

Я согласен на 100% с ответом Грея. Однако неатомарность приращения - известная проблема, и она не только применима к многоядерным процессам, так же как и на одноядерном компьютере.

Дело в том, что x++ (обычно) фактически выполняется с помощью нескольких инструкций ассемблера, например:

load r,[x]  ; load memory into register
incr r       ; increment register
stor [x],r  ; store register back to memory

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

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

Answer 2

Почему вы думаете, что значение x хранится в согласованном месте кэша?Каждое ядро ​​имеет свою собственную кэш-память, но нет гарантий согласованности между этими кэшами, если только вы не попросите их.И нет никакой гарантии ни на порядок обновлений кеша, ни на частоту.Один поток может добавить 100 к x, и затем кэш может быть синхронизирован с перезаписью шага другого потока, равного 20.

При первом обращении к x он попадает в кэш памяти процессора (или ядра) изцентральная память.Скорее всего, каждый поток получит 0 в первый раз.Но это может быть в самом конце цикла, что все записывается обратно в центральную память, и каждый поток может легко записать от 1000 до x.Конечно, нет никаких гарантий, что x будет обновляться с каждым x++ - либо написанным, либо перечитанным.Фактически, вы в значительной степени гарантируете, что x не будет , а обновляться каждый раз, если он не синхронизирован.С точки зрения этого узкого цикла, x никогда не будет удален из кэша, поэтому он никогда не будет перечитываться автоматически.Даже если бы это не было таким уж трудным циклом, сделать предположение о том, когда x будет выселено, будет крайне сложно, даже если вы всегда работали на одном и том же оборудовании.

Наконец,Слово на самом деле это «синхронизация» вместо «атомарный».x++ в наши дни редко является атомарной операцией (на самом деле это чтение, приращение, сохранение), но она определенно не синхронизируется между ячейками кеш-памяти или центральным хранилищем.

Answer 3

Кэш-когерентность означает, что как только одно ядро ​​(или устройство управления шинами) записывает данные в ячейку памяти, эта ячейка становится недействительной в других (всех) кешах, которые ее содержат.Это заставляет их перезагружать местоположение (в виде 64-байтовой строки кэша), прежде чем они смогут получить к нему доступ (R или W) в следующий раз.

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

Что это за гарантия, еслиданные не гарантированно действительны?Это лучшее, что можно сделать в данных обстоятельствах.Выбор между полностью синхронизированными ядрами (которые будут работать очень медленно) и работающими на полной скорости с кешами (с конкретными, определенными последствиями и рабочими решениями для их обработки).Решения, по сути, очень короткие замедления, так что впоследствии все синхронизируется.Эти кратковременные, очень короткие замедления следует сопоставлять с постоянным замедлением полностью синхронизированных ядер.

В нормальных условиях нет конкуренции за одно и то же местоположение от разных ядер или устройств управления шинами.Но как только они начинают совместно использовать определенные области памяти, предоставленные решения позволяют программисту убедиться, что необходимая синхронизация может быть реализована.

Это похоже на довольно хорошую статью о кешах ... и это .

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