Протокол МЕСЯЦЕВ

Протокол MESI на основе Invalidate — это протокол согласованности кэша и один из наиболее распространенных протоколов, поддерживающих кэши с обратной записью . Он также известен как протокол Иллинойса из-за его разработки в Университете Иллинойса в Урбана-Шампейн . ^[1] Кэши с обратной записью могут сэкономить значительную часть полосы пропускания, которая обычно тратится на запись через кэш . В кэшах обратной записи всегда присутствует «грязное» состояние, которое указывает на то, что данные в кэше отличаются от данных в основной памяти. Протокол Иллинойса требует передачи из кэша в кэш при промахе, если блок находится в другом кэше. Этот протокол уменьшает количество транзакций с основной памятью по сравнению с протоколом MSI . Это означает значительное улучшение производительности. ^[2]

Штаты

Буквы в аббревиатуре MESI обозначают четыре исключительных состояния, которыми может быть отмечена строка кэша (закодированная с использованием двух дополнительных битов ):

Модифицированный (М): Строка кэша присутствует только в текущем кэше и является «грязной» — она была изменена (состояние M) по сравнению со значением в основной памяти . Кэш необходим для записи данных обратно в основную память в какой-то момент в будущем, прежде чем будет разрешено любое другое чтение (уже недействительного) состояния основной памяти. Обратная запись переводит строку в общее состояние (S).
Эксклюзивный (Е): Строка кэша присутствует только в текущем кэше, но чистая — соответствует основной памяти. Его можно изменить в состояние «Общий» в любое время в ответ на запрос на чтение. Альтернативно, он может быть переведен в состояние «Изменено» при записи в него.
Общий (S): Указывает, что эта строка кэша может храниться в других кэшах машины и является чистой — соответствует основной памяти. Строка может быть удалена (переведена в состояние «Недействительно») в любой момент.
Недействительный (Я): Указывает, что эта строка кэша недействительна (не используется).

Для любой пары кэшей разрешенные состояния данной строки кэша следующие:

	М	И	С	я
М	Н	Н	Н	И
И	Н	Н	Н	И
С	Н	Н	И	И
я	И	И	И	И

Когда блок помечен как M (модифицированный) или E (исключительный), копии блока в других кэшах помечаются как I (недействительный).

Операция

Протокол MESI определяется конечным автоматом , который переходит из одного состояния в другое на основе двух стимулов.

Первым стимулом является запрос на чтение и запись, специфичный для процессора. Например: процессор P1 имеет блок X в своем кэше, и от процессора поступает запрос на чтение или запись из этого блока.

Второй стимул подается через шину, соединяющую процессоры. В частности, «запросы на стороне шины» поступают от других процессоров, у которых нет блока кэша или обновленных данных в их кэше. Запросы на шину отслеживаются с помощью Snoopers , ^[4] которые контролируют все транзакции шины.

Ниже приведены различные типы запросов процессора и запросов на стороне шины:

Запросы процессора на кэширование включают следующие операции:

PrRd: процессор запрашивает чтение блока кэша.
PrWr: процессор запрашивает запись блока кэша.

Запросы со стороны шины следующие:

BusRd: отслеживаемый запрос, указывающий на наличие запроса на чтение блока кэша, запрошенного другим процессором.
BusRdX: отслеживаемый запрос, указывающий на наличие запроса на запись в блок кэша, запрошенного другим процессором, у которого еще нет этого блока.
BusUpgr: Отслеживаемый запрос, указывающий на наличие запроса на запись в блок кэша, запрошенного другим процессором, у которого этот блок кэша уже находится в его собственном кэше .
Flush: Отслеживаемый запрос, который указывает, что весь блок кэша записывается обратно в основную память другим процессором.
FlushOpt: отслеживаемый запрос, который указывает, что весь блок кэша отправляется на шину для передачи его другому процессору (передача из кэша в кэш).

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

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

Snooper в сторону процессора/кэша.
Функция отслеживания на стороне памяти выполняется контроллером памяти.

Объяснение:

Каждый блок Cache имеет свой собственный конечный автомат с 4 состояниями (см. рисунок 1.1). Переходы между состояниями и реакции в конкретном состоянии по отношению к различным входным сигналам показаны в Таблице 1.1 и Таблице 1.2.

Таблица 1.1. Переходы состояний и реакция на различные операции процессора
Исходное состояние	Операция	Ответ
Недействительно(Я)	ПрРд	Выдать BusRd на шину другие кеши видят BusRd и проверяют, есть ли у них действительная копия, сообщают об отправке кеша Переход состояния в (S) Shared , если в других кэшах есть действующая копия. Переход в состояние (E) Exclusive , если его нет (необходимо убедиться, что все остальные сообщили об этом). Если в других кэшах есть копия, один из них отправляет значение, иначе извлекается из основной памяти.
	ПрВр	Выдать сигнал BusRdX на шине Переход состояния в (M) Изменено в кэше запросчика. Если в других кэшах есть копия, они отправляют значение, в противном случае извлекают его из основной памяти. Если в других кэшах есть копия, они видят сигнал BusRdX и делают свои копии недействительными. Блок записи в кэш изменяет значение.
Эксклюзивный(Е)	ПрРд	Транзакции шины не создаются Состояние остаётся прежним. Чтение в блоке является попаданием в кэш
	ПрВр	Транзакция шины не генерируется Переход состояния от эксклюзивного к (M) измененному Запись в блок — это попадание в кэш
Общий(S)	ПрРд	Транзакции шины не создаются Состояние остаётся прежним. Чтение в блоке является попаданием в кэш.
	ПрВр	Выдает сигнал BusUpgr на шине. Переход состояния в (M) Modified . другие кэши видят BusUpgr и помечают свои копии блока как (I)Invalid.
Модифицированный(М)	ПрРд	Транзакции шины не создаются Состояние остаётся прежним. Чтение в блоке — это попадание в кэш.
	ПрВр	Транзакции шины не создаются Состояние остаётся прежним. Запись в блок — это попадание в кэш.

Таблица 1.2. Переходы состояний и реакция на различные операции шины
Исходное состояние	Операция	Ответ
Недействительно(Я)	Автобусная улица	Никаких изменений штата. Сигнал игнорируется.
	БусРдХ/БусУпгр	Никаких изменений штата. Сигнал игнорируется
Эксклюзивный(Е)	Автобусная улица	Переход на Shared (поскольку подразумевает чтение, происходящее в другом кеше). Поместите FlushOpt на шину вместе с содержимым блока.
	АвтобусRdX	Переход в недействительный . Поместите FlushOpt на шину вместе с данными из теперь уже недействительного блока.
Общий(S)	Автобусная улица	Никакого изменения состояния (другой кэш выполнял чтение этого блока, поэтому он все еще доступен). Может поместить FlushOpt на шину вместе с содержимым блока (выбор дизайна, какой кеш с состоянием Shared это делает).
	БусРдХ/БусУпгр	Переход в Invalid (кэш, отправивший BuxRdX/BusUpgr, становится Модифицированным) Может поместить FlushOpt на шину вместе с содержимым блока (выбор дизайна, какой кеш с состоянием Shared это делает)
Модифицированный(М)	Автобусная улица	Переход к (S)Общему. Поместите FlushOpt на шину с данными. Получен отправителем BusRd и контроллера памяти, который записывает в основную память.
	АвтобусRdX	Переход к (I)Invalid . Поместите FlushOpt на шину с данными. Получен отправителем BusRdx и контроллера памяти, который записывает в основную память.

Запись может выполняться свободно только в том случае, если строка кэша находится в состоянии «Изменено» или «Исключительно». Если он находится в состоянии «Общий», все остальные кэшированные копии должны быть сначала признаны недействительными. Обычно это делается с помощью широковещательной операции, известной как Request For Ownership (RFO) .

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

Кэш, который содержит строку в состоянии «Общая», должен прослушивать широковещательные сообщения о недействительности или запросе владения из других кэшей и отбрасывать строку (переводя ее в состояние «Недействительно») при совпадении.

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

В этом смысле эксклюзивное состояние является оппортунистической оптимизацией: если ЦП хочет изменить строку кэша в состоянии S, необходима транзакция шины, чтобы сделать недействительными все остальные кэшированные копии. Состояние E позволяет изменять строку кэша без транзакции шины.

Иллюстрация операций протокола MESI

Предположим, что следующий поток ссылок на чтение/запись. Все ссылки относятся к одному и тому же месту, а цифра относится к процессору, выдавшему ссылку.

Поток: R1, W1, R3, W3, R1, R3, R2.

Изначально предполагается, что все кэши пусты.

Таблица 1.3 Пример работы МЭСИ Все операции с одним и тем же блоком кэша (Пример: «R3» означает чтение блока процессором 3)
	Местный запрос	П1	П2	П3	Сгенерировано Запрос автобуса	Поставщик данных
0	Изначально	-	-	-	-	-
1	Р1	И	-	-	Автобусная улица	Мем
2	П1	М	-	-	-	-
3	Р3	С	-	С	Автобусная улица	Кэш P1
4	W3	я	-	М	BusUpgr	-
5	Р1	С	-	С	Автобусная улица	Тайник P3
6	Р3	С	-	С	-	-
7	Р2	С	С	С	Автобусная улица	Тайник P1/P3

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

Шаг 1: Поскольку кеш изначально пуст, основная память предоставляет P1 блок, и он переходит в эксклюзивное состояние.
Шаг 2: Поскольку блок уже присутствует в кеше и находится в эксклюзивном состоянии, он напрямую изменяет его без каких-либо инструкций шины. Блок теперь находится в измененном состоянии.
Шаг 3: На этом этапе на шину отправляется BusRd, и шпион на P1 это воспринимает. Затем он сбрасывает данные и меняет свое состояние на общее. Блок на P3 также меняет свое состояние на общий, поскольку получил данные из другого кэша. Данные также записываются обратно в основную память.
Шаг 4: Здесь BusUpgr отправляется на шину, и шпион на P1 обнаруживает это и делает блок недействительным, поскольку он будет изменен другим кэшем. Затем P3 меняет свое состояние блока на измененное.
Шаг 5: Поскольку текущее состояние недействительно, на шине будет размещен BusRd. Шпион на P3 это почувствует и стирает данные. Состояние обоих блоков на P1 и P3 теперь станет общим. Обратите внимание, что в этом случае даже основная память будет обновлена ранее измененными данными.
Шаг 6: В кеше произошло попадание, и он находится в общем состоянии, поэтому здесь не делается запрос к шине.
Шаг 7: На P2 произошел промах кэша, и отправлен BusRd. Злоумышленники на P1 и P3 это почувствуют, и оба попытаются сбросить данные. Тот, кто первым получит доступ к шине, выполнит эту операцию.

Прочтите для владения

Чтение для владения (RFO) — это операция в протоколах когерентности кэша , которая сочетает в себе чтение и широковещательную рассылку недействительности. Операция выполняется процессором, который пытается выполнить запись в строку кэша, находящуюся в общем (S) или недействительном (I) состояниях протокола MESI. Эта операция приводит к тому, что все остальные кэши устанавливают состояние такой строки в I. Транзакция чтения для владения — это операция чтения с намерением записать по этому адресу памяти. Поэтому данная операция является эксклюзивной. Он переносит данные в кеш и делает недействительными все остальные кеши процессора, содержащие эту строку памяти. В таблицах выше это называется «BusRdX».

Барьеры памяти

MESI в своей простой и простой реализации демонстрирует две конкретные проблемы с производительностью. Во-первых, при записи в недействительную строку кэша возникает длительная задержка, пока строка извлекается из других процессоров. Во-вторых, перевод строк кэша в недопустимое состояние отнимает много времени. Чтобы смягчить эти задержки, процессоры реализуют буферы хранения и делают очереди недействительными. ^[5]

Сохранить буфер

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

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

Недействительные очереди

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

В результате требуются барьеры памяти. Барьер хранилища очищает буфер хранилища, гарантируя, что все записи были применены к кешу этого ЦП. Барьер чтения очищает очередь аннулирования, гарантируя, что все операции записи, выполненные другими ЦП, станут видимыми для очищающего ЦП. Более того, блоки управления памятью не сканируют буфер хранилища, что приводит к аналогичным проблемам. Этот эффект заметен даже в однопоточных процессорах. ^[6]

Преимущества MESI перед MSI

Самое поразительное различие между MESI и MSI — это дополнительное «эксклюзивное» состояние, присутствующее в протоколе MESI. Это дополнительное состояние было добавлено, поскольку оно имеет много преимуществ. Когда процессору необходимо прочитать блок, которого нет ни у одного из других процессоров , а затем записать в него, в случае MSI будут выполнены две транзакции шины. Сначала выдается запрос BusRdX на чтение блока, за которым следует запрос BusUpgr перед записью в блок. Запрос BusRdX в этом сценарии бесполезен, поскольку ни один из других кешей не имеет такого же блока, но ни один из кешей не может узнать об этом. Таким образом, протокол MESI преодолевает это ограничение, добавляя монопольное состояние, что приводит к сохранению запроса шины. Это имеет огромное значение при работе последовательного приложения. Поскольку с фрагментом данных работает только один процессор, все доступы будут эксклюзивными. MSI в этом случае работает гораздо хуже из-за дополнительных сообщений шины. Даже в случае высокопараллельного приложения с минимальным обменом данными MESI работает намного быстрее. Добавление эксклюзивного состояния также осуществляется бесплатно, поскольку 3 и 4 состояния могут быть представлены двумя битами.

Недостаток МЕСЯЦЕВ

В случае, если непрерывные операции чтения и записи выполняются различными кэшами в определенном блоке, данные необходимо каждый раз сбрасывать на шину. Таким образом, основная память будет тянуть это при каждой очистке и оставаться в чистом состоянии. Но это не является обязательным требованием, а является лишь дополнительными накладными расходами, вызванными использованием MESI. Эта проблема была решена протоколом MOESI . ^[7]

В случае S (Shared State) несколько шпионов могут ответить FlushOpt с одними и теми же данными (см. пример выше). Состояние F в MESIF устраняет эту избыточность.

См. также

Протокол согласованности
Протокол MSI — базовый протокол, на основе которого создан протокол MESI.
Однократная запись (когерентность кэша) — ранняя форма протокола MESI.
протокол MOSI
Протокол MOESI
Протокол MESIF
протокол СПАСИБО
Протокол Дракона
Протокол Светлячка

Ссылки

^ Папамаркос, Миссисипи; Патель, Дж. Х. (1984). «Решение когерентности с низкими издержками для мультипроцессоров с частной кэш-памятью» (PDF) . Материалы 11-го ежегодного международного симпозиума по компьютерной архитектуре - ISCA '84 . п. 348. дои : 10.1145/800015.808204 . ISBN 0818605383 . S2CID 195848872 . Проверено 19 марта 2013 г.
^ Гомес-Луна, Дж.; Эррузо, Э.; Бенавидес, Дж.И. «Симулятор когерентности кэша MESI для учебных целей». Электронный журнал Clei . 12 (1, ДОКУМЕНТ 5, АПРЕЛЯ 2009 ГОДА). CiteSeerX 10.1.1.590.6891 .
^ Каллер, Дэвид (1997). Параллельная компьютерная архитектура . Издательство Морган Кауфманн. стр. Рисунок 5–15. Диаграмма перехода состояний для протокола Illinois MESI. Стр. 286.
^ Бигелоу, Нарасиман, Сулеман. «Оценка протоколов согласованности кэша на основе Snoopy» (PDF) . Департамент ДОО Техасского университета в Остине. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Хэнди, Джим (1998). Книга кэш-памяти . Морган Кауфманн. ISBN 9780123229809 .
^ Чен, Г.; Коэн, Э.; Ковалёв, М. (2014). «Уменьшение буфера хранилища с помощью MMU». Проверенное программное обеспечение: теории, инструменты и эксперименты . Конспекты лекций по информатике. Том. 8471. с. 117. дои : 10.1007/978-3-319-12154-3_8 . ISBN 978-3-319-12153-6 .
^ «Система памяти (когерентность и протокол памяти)» (PDF) . Технология AMD64. Сентябрь 2006 г.

Внешние ссылки

[1] Папамаркос, Миссисипи; Патель, Дж. Х. (1984). «Решение когерентности с низкими издержками для мультипроцессоров с частной кэш-памятью» (PDF) . Материалы 11-го ежегодного международного симпозиума по компьютерной архитектуре - ISCA '84 . п. 348. дои : 10.1145/800015.808204 . ISBN 0818605383 . S2CID 195848872 . Проверено 19 марта 2013 г.

[2] Гомес-Луна, Дж.; Эррузо, Э.; Бенавидес, Дж.И. «Симулятор когерентности кэша MESI для учебных целей». Электронный журнал Clei . 12 (1, ДОКУМЕНТ 5, АПРЕЛЯ 2009 ГОДА). CiteSeerX 10.1.1.590.6891 .

[3] Каллер, Дэвид (1997). Параллельная компьютерная архитектура . Издательство Морган Кауфманн. стр. Рисунок 5–15. Диаграмма перехода состояний для протокола Illinois MESI. Стр. 286.

[4] Бигелоу, Нарасиман, Сулеман. «Оценка протоколов согласованности кэша на основе Snoopy» (PDF) . Департамент ДОО Техасского университета в Остине. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Хэнди, Джим (1998). Книга кэш-памяти . Морган Кауфманн. ISBN 9780123229809 .

[6] Чен, Г.; Коэн, Э.; Ковалёв, М. (2014). «Уменьшение буфера хранилища с помощью MMU». Проверенное программное обеспечение: теории, инструменты и эксперименты . Конспекты лекций по информатике. Том. 8471. с. 117. дои : 10.1007/978-3-319-12154-3_8 . ISBN 978-3-319-12153-6 .

[7] «Система памяти (когерентность и протокол памяти)» (PDF) . Технология AMD64. Сентябрь 2006 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]