CPU
June 2013 19

Кэш в многопроцессорных системах. Когерентность кэша. Протокол MESI

From Sandbox
Привет, Хабр!

В свое время это тема показалась мне очень интересной, поэтому я решил поделиться своими скромными знаниями с вами. Данная статья не претендует на полное детальное описание, скорее это краткий обзор.

Введение


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

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

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

Было придумано множество протоколов когерентности, отличающиеся алгоритмами, количеством состояний и, как следствие скоростью работы и масштабируемостью. Большинство современных протоколов когерентности представляют вариации протокола MESI [1]. По этой причине мы его и рассмотрим.

MESI

В данной схеме каждая линию кэша может находиться в одном из четырех состояний:

  • Модифицированная (M) англ. modified. Таким флагом может быть помечена только линия в одном кэше. Данное состояние означает, что данная линия была изменена, но до памяти эти изменения еще не дошли. Хозяин такой линии может спокойно читать и писать в нее без опроса остальных.
  • Эксклюзивная (E) англ. exclusive. Обозначенная таким флагом линия, так же, как и M-линия может находиться только в одном кэше. Содержащиеся в ней данные полностью идентичны данным в оперативной памяти. Записывать и читать из нее можно без внешних запросов, так как она хранится только в одном кэше. После записи такая строка должна быть помечена, как модифицированная.
  • Разделяемая (S) англ. shared. Линия может одновременно содержаться в кэшах нескольких устройств и использоваться совместно. Запросы на запись в такую линию всегда идут на общую шину, что привод к тому, что все линии с таким адресов в остальных кэшах помечаются как недействительные. При этом содержание основной памяти также обновляется. Чтение же из такой линии, не требует ни каких внешних запросов.
  • Недействительная (I) англ. invalid. Такая линия считается невалидной и попытка прочитать приведет к кэш-промаху. Линия помечается недействительной в случае если она пусти или содержит устаревшую информацию.


Диаграмма переходов протокола MESI. Доступ являет местным, если он был инициирован процессоров данного кэша, удаленным — если его вызвал любой другой.

image

Также хочу рассмотреть одну из оптимизаций протокола MESI

MOESI

Для данного протокола флаги состояния были расширены еще одним значением «Владелец» (O) англ. owner. Данное состояние является комбинацией состояний «Модифицированная» и «Разделяемая». Такое состояние позволяет избежать необходимости записи измененной линии в память, тем самым снижая трафик направленный в память. Кэш линия в такой состоянии содержит наиболее свежие данные. Описанное состояние похоже на Shared тем, что и другие процессоры тоже могут иметь наиболее более свежие по отношению к ОЗУ данные у себя в кэш-памяти. Однако в отличие от него такое состояние обозначает, что данные в памяти устарели. Только одна линия с определенным адресом может иметь такое состояние, при этом на все запросы о чтении по данному адресу отвечать будет именно она, а не память.

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

Дополнительную информацию на эту тему можно найти в источниках обозначенных ниже.

Литература


[1] Обзор существующих протоколов, с диаграммами перехода
[2] Г.С. Речистов, Е.А. Юлюгин, А.А. Иванов, П.Л. Шишпор, Н.Н. Щелкунов «Основы программного моделирования ЭВМ» URL
[3]Ulrich Drepper «What Every Programmer Should Know About Memory» URL
+7
3.5k 23
Comments 2
Top of the day