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 но ассоциативность все равно ни при чем. "грязная" ячейка не вытеснится до завершения операции записи в память.

[tengiz]

Я не собираюсь спорить, т.к. у нас взаимное недопонимание

А зачем спорить? Давайте обсуждать и обмениваться информацией - в этом же весь смысл?

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

Пример процессора можете привести где это так? На последних альфах и на всех последних интелах - "грязная" ячейка "выдавленная" из кеша бесприкословно следует в victim buffer (Alpha) или во write buffer a.k.a. store buffer (Intel).

[dB13]

You are mixing different things here.

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

6. Процессор 2 читает ячейку A и видит старое значение, так как прямой механизм когерентности уже не может ничего сделать (опять же, даже если бы и мог) - cacheline, содержащий любые сведения о ячейке A, включая её когерентное состояние MESI, в кеше процессора 1 уже отсутствует.
7. Процессор 1 завершает pending записи в память, включая запись в A, о чём становится известно процессору 2, который инвалидирует cacheline, содержащий A.

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

Can you tell where did you work with HW before the current job?
You know too much about HW for a database engine developer.
I wish I knew about databases as you know about CPUs.

You are mistaken in #6, at least on P6 Intel CPU family(PPro,P2, P3).
P6 CPU bus uses a spit transaction bus.
The write buffer keeps MESI tags and participates in the snooping protocol.
In your example there will be an "implicit writeback" bus transaction:

1) CPU2 initiates a read from A
2) CPU1 write buffer gets a snoop hit and provides the cache line containing A
3) This cache line is written SIMULTANEOUSLY to RAM and to CPU2 cache.
BTW, the world A will be provided first regardless of its location in the 32 byte cache line.

The reference: "Pentium Pro and Pentium II System Architecture", Second Edition, By Tom Shanley/MindShare, Addison-Wesley, 0-201-30973-4
I can't find a detailed description of P6 bus protocol on Web.

[uncle_Pasha]

Пример процессора можете привести где это так? На последних альфах и на всех последних интелах - "грязная" ячейка "выдавленная" из кеша бесприкословно следует в victim buffer (Alpha) или во write buffer a.k.a. store buffer (Intel).

Но это не значит, что "грязная" cacheline available на запись до освобождения буфера - завершения записи в память. Даже если вместо буфера будет очередь.

Удачи!

[tengiz]

Но это не значит, что "грязная" cacheline available на запись до освобождения буфера - завершения записи в память.

Ну так весь смысл victim cache именно в том, чтобы не случилась дополнительной задержки в случае повторного cache miss попавшего на грязную cacheline. К сожалению, я не могу найти ссылки на толковой материал по этому поводу, а набирать текст из энциклопедии Hennessy о современных компьютерных архитектурах мне неохота - Computer Architecture : A Quantitative Approach by John L. Hennessy, David Goldberg, David A. Patterson.

[tengiz]

The write buffer keeps MESI tags and participates in the snooping protocol.

Ага, значит реальность заметно хитрее, чем это следует из менее подробных описаний архитектуры. Спасибо!

[tengiz]

Can you tell where did you work with HW before the current job?
You know too much about HW for a database engine developer.

Академя Наук CCCP, Институт Океанологии. Я там занимался экспериментальной физикой (а именно, подводной акустикой) и мне довольно много приходилось возиться с разработкой нестандартного аналогового и аналогово-цифрового барахла для наших основных занятий. Включая и SW для ввода этих данных, а затем и для высокоскоростной обработки реального времени и эффективного хранения. С самого начала это всё было как бы второстепенным вспомогательным занятием, хотя и критически важным, а потом внезапно оказалось, что подобная чисто инженерная работа может быть безумно интересной и увлекательной. Ну а дальше мне просто повезло - мне посчастливилось участвовать в качестве ключевой персоны в большом количестве совершенно разнородных HW/SW проектов, благодаря чему мне удалось набраться очень разного опыта.

[dB13]

Академя Наук CCCP, Институт Океанологии. Я там занимался экспериментальной физикой (а именно, подводной акустикой) и мне довольно много приходилось возиться с разработкой нестандартного аналогового и аналогово-цифрового барахла для наших основных занятий...

И куда только не заносит людей из 24-й группы!

dB13, 22(б)

[tengiz]

И куда только не заносит людей из 24-й группы!

dB13, 22(б)

!!! Физкульт-привет ИФТТ и ИФП (пардон, не помню что из нех есть <а>, а что <б>)! Я, кстати, и в 22 тоже побывал - в ИТФ в Черноголовке у "пьяницы и дебошира" Горькова. Только это наверное 22 (в) должно было называться.

[dB13]

И куда только не заносит людей из 24-й группы!

dB13, 22(б)

!!! Физкульт-привет ИФТТ и ИФП (пардон, не помню что из нех есть <а>, а что <б>)!

22(б) -- ИФТТ