Согласованность памяти и согласованность кэша

16

Правда ли, что последовательная согласованность является более сильным свойством, чем когерентность кэша?

В соответствии с

Сорин, Даниэль Дж; Hill, Mark D; Вуд, Дэвид А. Учебник по последовательности памяти и согласованности кэша , Morgan & Claypool, 2011

последовательная согласованность может быть описана как (не формально):

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

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

Теперь они продолжают и описывают последовательность:

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

Другими словами, система является связной, если для заданных событий памяти каждого потока для каждого местоположения мы можем упорядочить события для этого местоположения, так что: 1) для каждого потока сохраняется порядок его событий в этом местоположении , и 2) для каждого Расположение заказа является серийным.

Наконец, они указывают на разницу:

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

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

Означает ли это, что последовательность менее строга, чем последовательность? (что кажется забавным!) Есть ли следы, которые являются последовательными, но не последовательными?

Айрат
источник
2
Обратите внимание, что нам не нравятся вопросы формы «пожалуйста, проверьте мой ответ!». Можете ли вы добавить более конкретный вопрос? Как вы думаете, где ваш разрыв может быть?
Рафаэль
@ Рафаэль, ты прав, и когда я писал вопрос, было не очень хорошо. Но что делать, если я не смог найти ответ в Интернете (кроме смутных утверждений, таких как «согласованность говорит об одном бите, который отличается от согласованности, который говорит обо всех битах»), и поэтому попытался найти ответ, и когда кажется, обнаружил, что не уверен, правильно ли это. Я должен был придумать подозрительный вопрос? Или не дать ответ на вопрос? :)
Айрат
@ Айрат Я прочитал последнюю часть вашего вопроса как ответ, который вы хотите проверить. Если это так, то должны быть некоторые сомнения (иначе, зачем спрашивать?), Которые вы должны определить для читателей. Может я неправильно понял?
Рафаэль
@ Рафаэль «последняя часть хочет быть проверена» - да. 'зачем спрашивать?' - тема новая, и я не был уверен, что вывод правильный. Я постараюсь избежать подобных вопросов в будущем и, возможно, найду кого-нибудь, кто сможет это проверить.)
Айрат,

Ответы:

9

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

Доказательство последовательно согласованного подразумевает связное:

ИксИкс

ИксYИкс0Y0ИксYИксYYИкс

Это может привести к неожиданным результатам. Например

initially A=B=0
process 1               process 2
store A := 1            load B (gets 1)
store B := 1            load A (gets 0) 

Этот след является последовательным:

  • для А заказ: proc2 loads A(gets 0),proc1 stores A:=1
  • для B заказ: proc1 stores B:=1,proc2 loads B(gets 1)

Но это не соответствует! Так как если proc2 load Bвозвращает 1, то proc1 store A := 1уже произошло и proc2 load Aдолжно также вернуть 1.

Блуждающая логика
источник