Протокол MESI - MESI protocol

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

состояния

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

Модифицированный (M)

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

Эксклюзив (E)

Строка кэша присутствует только в текущем кэше, но есть чистый - соответствует основной памяти. Его можно изменить в состояние Shared в любое время в ответ на запрос чтения. Кроме того, его можно изменить в состояние Modified при записи в него.

Общий (S)

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

Недействительный (I)

Указывает, что эта строка кэша недействительна (не используется).

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

	M	E	S	я
M	N	N	N	Y
E	N	N	N	Y
S	N	N	Y	Y
я	Y	Y	Y	Y

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

Операция

Изображение 1.1 Диаграмма состояний протокола MESI Красный: транзакция инициирована шиной. Черный: транзакции, инициированные процессором.^[3]

Состояние конечного автомата переходит из одного состояния в другое на основе 2 стимулов. Первый стимул - это специфичный для процессора запрос на чтение и запись. Например: процессор P1 имеет блок X в своем кэше, и есть запрос от процессора на чтение или запись из этого блока. Второй стимул исходит от другого процессора, у которого нет блока кэша или обновленных данных в его кэше, через шину, соединяющую процессоры. Запросы на шину отслеживаются с помощью Snoopers^[4] который отслеживает все автобусные транзакции.

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

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

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

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

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

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

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

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

Объяснение:

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

Запись может выполняться свободно, только если строка кэша находится в состоянии Modified или Exclusive. Если он находится в состоянии Shared, все остальные кэшированные копии должны быть сначала признаны недействительными. Обычно это делается с помощью широковещательной операции, известной как Запрос на владение (RFO).

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

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

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

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

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

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

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

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

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

Шаг 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».

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

Эта статья может требовать уборка встретиться с Википедией стандарты качества. Конкретная проблема: Неправильная грамматика, форматирование и т. Д. Пожалуйста помоги улучшить эту статью если вы можете. (Март 2013 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Буфер хранения

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

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

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

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

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

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

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

Недостаток MESI

В случае, если непрерывные операции чтения и записи выполняются различными кэшами на конкретном блоке, данные должны каждый раз сбрасываться на шину. Таким образом, основная память будет вытягивать это при каждой очистке и оставаться в чистом состоянии. Но это не требование, а просто дополнительные накладные расходы, вызванные реализацией MESI. Этот вызов был преодолен Протокол MOESI.^[8]В случае S (Shared State) несколько наблюдателей могут ответить FlushOpt с одинаковыми данными (см. Пример выше). Состояние F в адресах MESIF для устранения этой избыточности.

Смотрите также

• Протокол согласованности
• Протокол MSI, основной протокол, из которого основан протокол MESI.
• Однократная запись (согласованность кеша), ранняя форма протокола MESI.
• Протокол MOSI
• Протокол MOESI
• Протокол MESIF
• Протокол MERSI
• Протокол дракона
• Протокол светлячка

Рекомендации

внешняя ссылка

• Интерактивное моделирование MESI
• Контроллер MESI с открытым исходным кодом (Verilog)