Файл: 481-550.pdf

Мультипроцессорная когерентность кэш-памяти  5 1 1

Рис. 11.10. Протокол Berkeley

Для постоянно читаемой и обновляемой строки в протоколе однократной за-

писи необходимы считывание этой строки в кэш, ее локальная модификация в кэше

и обратная запись в память. Вся процедура требует двух операций на шине: чтения

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

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

ми, в то время как протокол однократной записи передает блок из исходного кэша

в основную память, а затем из ОП в запросившие кэши, что имеет следствием об-
щую задержку системы памяти [141],

Протокол Illinois.

 Протокол Illinois, предложенный Марком Папамаркосом

[175], также направлен на снижение трафика шины и, соответственно, времени

ожидания процессором доступа к шине. Здесь, как и в протоколе Berkeley, главен-
ствует идея прав владения блоком, но несколько измененная. В протоколе Illinois
правом владения обладает любой кэш, где есть достоверная копия блока данных.

В этом случае у одного и того же блока может быть несколько владельцев. Когда

такое происходит, каждому процессору назначается определенный приоритет и ис-

точником информации становится владелец с более высоким приоритетом.

Как и в предыдущем случае, сигнал аннулирования формируется, лишь когда

копии данного блока имеются и в других кэшах. Возможные сценарии для прото-
кола Illinois представлены на рис. 11.11,

5 1 2 Глава 11. Организация памяти вычислительных систем

Рис.  1 1 . 1 1 . Протокол Illinois

Каждый раз когда какой-либо процессор производит запись в свою кэш-память,

изменяемая строка переводится в состояние «измененная частная» (PD, Private
Dirty). Если блок данных является совместно используемым, на шину посылается

сигнал аннулирования и во всех локальных кэшах, где есть копия данного блока,

эти копии переводятся в состояние «недействительная» (I, Invalid). Если при за-
писи случился промах, процессор получает копию из кэша текущего владельца

запрошенного блока. Лишь после означенных действий процессор производит за-

пись в свой кэш. Как видно, в этой части имеет место полное совпадение с прото-
колом Berkeley,

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

чтобы получить наиболее свежую версию последнего, и переводит свою новую
копию в состояние «эксклюзивная»- (Е, Exclusive) при условии, что он является
единственным владельцем строки. Б противном случае статус меняется на «разде-
ляемая» (S, Shared).

Существенно, что протокол расширяем и тесно привязан как к коэффициенту

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

Протокол Firefly.

 Протокол был предложен Такером и др.

 [211]

 и реализован

в мультипроцессорной системе Firefly Multiprocessor Workstation, разработанной
в исследовательском центре Digital Equipment Corporation.

В протоколе Firefly используется запись с обновлением. Возможные состояния

строки кэша совпадают с состояниями протокола Illinois (рис. 11,12). Отличие со-
стоит в том, что стратегия обратной записи применяется только к тем строкам,
которые находятся в состоянии PD или Е, в то время как применительно к строкам

Мультипроцессорная когерентность кэш-памяти  5 1 3

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

дающие кэши, обнаружившие у себя копию строки, возбуждают специальную

«разделяемую» линию шины с тем, чтобы записывающий контроллер мог при-
нять решение о том, в какое состояние переводить строку, в которую была про-

изведена запись. «Разделяемая» линия при кэш-промахе чтения служит для
информирования контроллера локальной кэш-памяти о месте, откуда посту-
пила копия строки: из основной памяти или другого кэша. Таким образом, со-
стояние S применяется только к тем данным, которые действительно исполь-
зуются совместно [162, 212].

Рис. 11.12. Протокол Firefly

Протокол имеет преимущества перед ранее описанными в том, что стратегия

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

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

Протокол Dragon.

 Протокол применен в мультипроцессорной системе Xerox

Dragon и представляет собой независимую версию протокола Firefly.

17 Заk. 470

 ;

5 1 4 Глава 11. Организация памяти вычислительных систем

В протоколе реализована процедура записи с обновлением. Строка кэша может

иметь одно из пяти состояний [162,212]:

- Invalid (I) —

 копия, хранящаяся в кэше, недействительна;

-

 Read Private (RP) —

 существует лишь одна копия блока, и она совпадает с содер-

жимым основной памяти;

- Private Dirty

 (PD) — существует лишь одна копия блока, и она не совпадает с со-

держимым основной памяти;

- Shared Clean

 (SC) — имеется несколько копий блока, и все они идентичны со-

держимому основной памяти;

- Shared Dirty

 (SO) — имеется несколько копий блока, не совпадающих с содер-

жимым основной памяти.
Дополнительное состояние SO предназначено для предотвращения записи

в основную память. Диаграмма состояний для данного протокола приведена на
рис. 11.13.

Рис. 11.13. Протокол Dragon

Протокол

 MESI.

 Безусловно, среди известных протоколов наблюдения самым

популярным является протокол MESI (Modified/Exclusive/Shared/Invalid). Про-

токол MESI широко распространен в коммерческих микропроцессорных систе-

мах, например на базе микропроцессоров Pentium и PowerPC. Так, его можно обна-
ружить во внутреннем кэше и контроллере внешнего кэша i82490 микропроцессора

Pentium, в процессоре i860 и контроллере кэш-памяти МС88200 фирмы Motorola,

Протокол был разработан для кэш-памяти с обратной записью. Одной из ос-

новных задач протокола MESI является откладывание на максимально возмож-

Мультипроцессорная когерентность кэш-памяти  5 1 5

ный срок операции обратной записи кэшированных данных в основную память

ВС. Это позволяет улучшить производительность системы за счет минимизации

ненужных пересылок информации между кэшами и основной памятью.

Протокол MESI приписывает каждой кэш-строке одно из четырех состояний,

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

системы. Управление состоянием кэш-строк может быть возложено и на внешние
логические устройства. Одна из версий протокола предусматривает использова-

ние ранее рассмотренной схемы однократной записи.

Рис. 11.14, Протокол MESI —диаграмма состояний без учета однократной записи

Согласно протоколу MESI, каждая строка бывает в одном из четырех возмож-

ных состояний (в дальнейшем будем ссылаться на эти состояния с помощью букв
М, Е, S и I):

-Модифицированная

 (М, Modified) — данные в кэш-строке, помеченной как М,

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

кэшах — недостоверна.

- Эксклюзивная

 (Е, Exclusive) — данная строка в кэше не подвергалась измене-

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