How Often Does Processor Cache Flush?

[Vovka]

Вот в этой вот статье в MSDN описывается случай гонок на мультипроцессорной машине.

А если рассмотреть упрощенный сценарий, когда имеем всего одну 32-бит переменную, которую одня нить пишет, а другая читает, безо всякой синхронизации. Понятно, что никаких гонок тут быть не может. Но каков максимальный промежуток времени между тем, как одна нить запишет значение, а другая нить прочитает это _новое_ значение?
Правильно ли я понимаю, что любые "синхронизирующие" вызовы (EnterCriticalSection, WaitFor*) сбрасывают кэш, а т.к. при переключении контекстов нитей чего-нить из этого добра используется (верно?), то максимальное время "рассинхронизации" - это квант времени, выделяемый одной нити?

[tengiz]

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

"Синхронизирующие" функции и переключение контекста используют ту или иную форму барьера - инструкции, которая не завершится или не начнётся, пока все ожидающие окончания операции по обмену кеша с памятью не очистятся.

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

[Vovka]

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

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

[dB13]

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

On current IA32 SMP systems(2-4 CPUs) this time is in about 10-100 CPU clock cycles -- less than 0.1 microseconds.
Big IA32 SMP systems (32 CPUs) have more complicated caches so the time is about 0.1-1 microsecond.

Правильно ли я понимаю, что любые "синхронизирующие" вызовы (EnterCriticalSection, WaitFor*) сбрасывают кэш?

No, they do not flush the cache. Flushing and the refilling the whole cache is really
expensive and is needed only for really exotic operations mostly done by BIOS during POST (on IA32).

[dB13]

Вообще говоря, это зависит от реализации алгоритма когерентности кешей на конкретной аппаратнай платформе.

I totally agree here.

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

You are mixing different things here.
IIRC, on standard Pentium III / Pentium 4 / Xeon systems CPU-to-CPU cache coherency protocol is independent of CPU cache-to RAM coherency protocol.
Here is a simplified example:

1) initial state of a particular memory address/cache line:
RAM - 0
CPU0 cache - 0 (shared)
CPU1 cahce - 0 (shared)

CPU0 writes at this addess 1. After that the state is:
RAM - 0
CPU0 cache - 1 (exclusive, modified)
CPU1 cache - 0 (invalid)

Now CPU1 reads from this address and gets 1. After that:
RAM - 0
CPU0 cache - 1 (shared, modified)
CPU1 cache - 1 (shared, modified)

Now a PCI DMA device (a network card for example) reads this address. After that:
memory/PCI controller polls CPUs (or CPUs snoop the chipset/CPU bus).
CPUx returns 1, 1is written to RAM and 1 is returned to the DMA device.
RAM - 1
CPU0 cache - 1 (shared)
CPU1 cache - 1 (shared)

If somebody wants more details then one should google for "MESI" and "coherency" keywords.

[tengiz]

You are mixing different things here.

I don't think so. То, о чём Вы говорите - это теоретически лучший случай, который я даже не уверен, если где-нибудь на системах с write-back кешами реализован без того, чтобы зависеть от задержки на те самые pending writes. Однако неполная ассоциативность кешей всё портит даже без этого. То, что я имел в виду - это практический худший случай, который как раз и отвечает на вопрос, какова верхняя оценка времени, в течение которого изменение (обычное, без барьера) сделанное одним процессором не будет видно другими. Сценарий такой:

1. Процессор 1 сделал обычную (без барьера) запись по адресу A.
2. Содержимое ячейки A НЕ находится в кеше процессора 2, поэтому прямой механизм обеспечения когерентности ничего не сделал (если бы даже и мог).
3. Так как операция записи обычная, то она становится pending write и помещается в буфер.
4. Процессор 1 сделал обычную запись по адресу B, которая из-за неполной ассоциативности кеша выкинула cacheline, содержащий A.
5. Операция записи в память по адресу A всё ещё pending.
6. Процессор 2 читает ячейку A и видит старое значение, так как прямой механизм когерентности уже не может ничего сделать (опять же, даже если бы и мог) - cacheline, содержащий любые сведения о ячейке A, включая её когерентное состояние MESI, в кеше процессора 1 уже отсутствует.
7. Процессор 1 завершает pending записи в память, включая запись в A, о чём становится известно процессору 2, который инвалидирует cacheline, содержащий A.

Теперь замечание по поводу "если бы даже и мог". Известные мне механизмы когерентности кешей (MESI included) следят за транзакциями на шине памяти - как только кто-то делает обращения к ячейке памяти, все остальные замечают её адрес и если их кеши содержат этот адрес, то делают соответствующие изменения. Запись в память в системах с write-back кешем осуществляется только при фактическом исполнении тех самых pending writes, а не при записи в кеш, поэтому хочешь, не хочешь, а время, пока операции записи болтаются в буфере, реально учитывать приходится.

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

[uncle_Pasha]

Однако неполная ассоциативность кешей всё портит даже без этого.

А при чем здесь ассоциативность?

Удачи!

[tengiz]

А при чем здесь ассоциативность?

При том, что из-за неполной ассоциативности кеша, cacheline, в которую попадают два обращения по разным адресам памяти, теряет информацию о первой записи, включая статус, необходимый для нормальной работы протокола MESI. Единственный след от первой записи в кеш остаётся только в pending writes буфере. Разница с просто "старением" информации в cacheline в том, что LRU или подобные механизмы повторного использования, обычно выкидыват cacheline намного позже, чем все соответствующие pending writes завершены.

[olg2002]

...имеем всего одну 32-бит переменную, которую одня нить пишет, а другая читает, безо всякой синхронизации.

Это классическое определение data race condition.

Так что я с чистой совестью забиваю на всякую синхронизацию, спасибо.

Обычно приходится возвращаться к такому коду и править его (после часов отладки).
Удачи!

[uncle_Pasha]

Кэш должен быть ассоциативным. (в качестве аттрибута используется физический адрес)
Неполная ассоциативность (как это и используется сейчас), если правильно помню, это изначально был компромис для удешевления больших кэшей - выбирать по атрибуту из ассоциативной памяти не сами данные, а адрес быстрой памяти, устроенной по обычному способу и потом адресоваться. Все строилось, естественно, аппаратно, но издержки были и такая память, хоть и выглядела для CPU, как ассоциативная но была медленнее. Зато существенно дешевле (по крайней мере лет 15 назад).
Сейчас (при нынешних размерах кэшей и количестве элементов на кристалл), это компромис, что пихать на один кристалл с процессором.
В интеле сейчас (если тоже память не изменяет), ассоциативная память, хранящая адреса "быстрой" памяти влазит и ставится на кристалл процессора, а сама "быстрая" память - внешняя.
Ассоциативность с алгоритмами вытеснения (LRU, etc) не связана.

Как Вы описываете, процессор 2 начал чтение после записи процессором 1 и данные в его кэше отсутствуют. Соответственно, ответ на обращение к кэшу от процессора 2 (дай данные для А) будет "read miss". Он полезет в память. Когда дойдет его очередь читать - данные уже там будут актуальные (идет запись в ОЗУ по адресу А - обращение к ОЗУ от 2 будет в ожидании).

Ежели же процессор 2 начнет чтение первым, то адрес в кэше 2 уже есть.
И он получит broadcast invalidate при записи процессором 1.

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

Удачи!

[dB13]

[quote="tengiz
Однако, как всегда, с удовольствием послушаю любую критику, если я где-нибудь маханулся. Я всё же не специалист по железу (хотя когда-то и был), но до сих пор за самыми главными вещами стараюсь следить.[/quote]

Tengiz, this detailed scenario is much better than your original explanation.
It is definitely plausible. What the real P3, P4, Anthon
SMP systems do is a harder question. I am not sure that
Intel/AMD publish such details of their MESI protocol implementations.
I'll try to dig up something here, I was involved more with PCI side
of chipsets at Intel.

[dB13]

...имеем всего одну 32-бит переменную, которую одня нить пишет, а другая читает, безо всякой синхронизации.

Это классическое определение data race condition.

Так что я с чистой совестью забиваю на всякую синхронизацию, спасибо.

Обычно приходится возвращаться к такому коду и править его (после часов отладки).
Удачи!

No, it is totally reasonable approach in this case (IA32).

The only requirements is that this 32-bit variable has to be
aligned, so reads/writes to it are atomic.

For example, one thread updates the variable but always keeps exactly 19 bits set in it.

The second thread just logs its value to a file.
It is guaranteed that the values in the file will be consistent --
all will have exactly 19 bits set.

[tengiz]

Вгз

I'm sorry - я не уверен, как на это отвечать так как никогда не видел такой аббревиатуры.

[tengiz]

Кэш должен быть ассоциативным. (в качестве аттрибута используется физический адрес)…В интеле сейчас (если тоже память не изменяет), ассоциативная память…

В Intel используется не fully associative cache, а multiway associative cache - по-русски это ещё называют многозаходным кешем, если я не ошибаюсь. Другими словами - многозаходный кеш – это вариант не полностью ассоциативного кеша, который имеет неприятное свойство отображать группы адресов на строго определённые группы cachelines. Поэтому если для 2-way associative cache предыдущие два обращения к памяти попали в определённую группу и заняли все слоты в группе, то если третье обращение отображается в ту же группу, то одно из предыдущих значений будет из кеша выброшено вне зависимости от того, что в других cache lines сидят намного более старые значения.

Ассоциативность с алгоритмами вытеснения (LRU, etc) не связана.

Я вроде и не писал о том, что они связаны. LRU упоминался в следующем контексте: если в кеш-группе нет места, то LRU логика для группы по отношению к более старым значеням в других кеш-группах не соблюдается. Т.е. когда не полностью ассоциативному кешу не хватает места в определённой группе (а вероятность этого тем выше, чем меньше этих ways у Кеша), то алгоритм LRU идёт на фиг и только что прочитанное/записанное значение выбрасывается из кеша намного раньше, чем если бы это случилось согласно LRU.

Как Вы описываете, процессор 2 начал чтение после записи процессором 1 и данные в его кэше отсутствуют. Соответственно, ответ на обращение к кэшу от процессора 2 (дай данные для А) будет "read miss". Он полезет в память. Когда дойдет его очередь читать - данные уже там будут актуальные (идет запись в ОЗУ по адресу А - обращение к ОЗУ от 2 будет в ожидании).

Ежели же процессор 2 начнет чтение первым, то адрес в кэше 2 уже есть.
И он получит broadcast invalidate при записи процессором 1.

Пожалуйста, прочитайте моё сообщение ещё раз – там чётко написано, что речь идёт об обычной записи без барьера (и блокировок), соответственно, процессор имеет право оптимизировать операцию записи (например, набрать пачку записей) и не обязан немедленно начать транзакцию на шине. Поэтому второй процессор, у которого может не оказаться другой работы, может полезть в память до того, как первый соизволит туда сунуться даже несмотря на то, инструкция записи в первом процессоре была выбрана и выполнена физически раньше. Строгая очерёдность из-за того, что есть write-back и pending writes буферы не может быть гарантирована.

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

Автор дискуссии задал вполне однозначный вопрос о том, что произойдёт, если при многопроцессорном доступе к одной переменной программист не будет использовать специальных «синхронизирующих» инструкций, т.е. никаких барьеров и блокировок. Именно об этом случае и только о нём идёт речь в моём сообщении.

[uncle_Pasha]

Автор дискуссии задал вполне однозначный вопрос о том, что произойдёт, если при многопроцессорном доступе к одной переменной программист не будет использовать специальных «синхронизирующих» инструкций, т.е. никаких барьеров и блокировок. Именно об этом случае и только о нём идёт речь в моём сообщении.

Я не собираюсь спорить, т.к. у нас взаимное недопонимание
Что касается основного вопроса, ответ однозначный: результат не предсказуем. Автор должен использовать Mutex (или как это в виндах ).

Удачи!
PS но ассоциативность все равно ни при чем. "грязная" ячейка не вытеснится до завершения операции записи в память.