Файл: 481-550.pdf

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

-

 Разделяемая

 (S, Shared) — строка в кэше совпадает с аналогичной строкой в ос-

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

- Недействителъная

 (I, Invalid) — кэш-строка, помеченная как недействитель-

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

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

Порядок перехода строки кэш-памяти из одного состояния в другое зависит от:

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

переходов без учета режима однократной записи.

Предположим, что один из процессоров делает запрос на чтение из строки, ко-

торой в текущий момент нет в его локальной кэш-памяти (промах при чтении).

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

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

Когда процессор делает запрос на запись в строку, отсутствующую в его ло-

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

должна быть считана из основной памяти (ОП) и модифицирована. Прежде чем
процессор сможет загрузить строку, он должен убедиться, что в основной памяти

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

отсутствует модифицированная копия данной строки. Формируемая в этом слу-
чае последовательность операций носит название

 чтения с намерением модифика-

ции

 (RWITM, Read With Intent To Modify). Если в одном из кэшей обнаружилась

копия нужной строки, причем в состоянии М, то процессор, обладающий этой ко-

пией, прерывает RWITM-последовательность и переписывает строку в ОП, после
чего меняет состояние строки в своем кэше на I. Затем RWITM-последователь-
ность возобновляется и делается повторное обращение к основной памяти для счи-
тывания обновленной строки. Окончательным состоянием строки будет М, при
котором ни в ОП, ни в других кэшах нет еще одной достоверной ее копни. Если
копия строки существовала в другом кэше и не имела состояния М, то такая копия
аннулируется и доступ к основной памяти производится немедленно.

Кэш-попадание при чтении не изменяет статуса читаемой строки. Если про-

цессор выполняет доступ для записи в существующую строку, находящуюся в со-

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

мировать другие кэши, обновляет строку в своем кэше и присваивает ей статус М.
Все остальные копии строки переводятся в состояние I. Если процессор произво-

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

На рис. 11.15 показана типичная последовательность событий в системе из двух

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

Проиллюстрируем этапы, когда процессор 2 пытается прочитать содержимое

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

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

состоянии М, поэтому он блокирует операцию чтения от процессора 2. Затем

процессор 1 переписывает строку, содержащую х", в ОП и освобождает про-
цессор

 2,

 чтобы тот мог повторить доступ к основной памяти. Теперь процес-

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

сор 2 получает строку, содержащую х", и загружает ее в свою кэш-память. Обе
копии помечаются как S.

До сих пор рассматривалась версия протокола MESI без однократной записи.

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

яние S. Первое попадание при записи сопровождается переходом в состояние Е

(так называемый переход однократной записи). Следующее попадание при записи
влечет за собой изменение статуса строки на М.

Протоколы на основе справочника

Протоколы обеспечения когерентности на основе справочника

 характерны для слож-

ных мультипроцессорных систем с совместно используемой памятью, где процес-

соры объединены многоступенчатой иерархической сетью межсоединений. Слож-

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

механизмом широковещания становится дорогостоящим и неэффективным.

Протоколы на основе справочника предполагают сбор и отслеживание инфор-

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

ной памяти. Когда контроллер локальной кэш-памяти делает запрос, контроллер

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

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

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

Справочник содержит множество записей, описывающих каждую кэшируемую

ячейку ОП, которая может быть совместно использована процессорами системы.

Обращение к справочнику производится всякий раз, когда один из процессоров

изменяет копию такой ячейки в своей локальной памяти. В этом случае информа-

ция из справочника нужна для того, чтобы аннулировать или обновить копии из-

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

Дли каждой строки общего пользования, копия которой может быть помещена

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

изводить запись в данную строку.

В настоящее время известны три способа реализации протоколов обеспечения

когерентности кэш-памяти на основе справочника: полный справочник, ограни-

ченные справочники и сцепленные справочники.

В протоколе

 полного справочника

 единый централизованный справочник поддер-

живает информацию обо всех кэшах. Справочник хранится в основной памяти.

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

Рис. 11.17. Протокол обеспечения когерентности кэш-памяти с полным справочником

В системе из N процессоров каждая запись справочника будет содержать

 N

 од-

нобитовых указателей. Если в соответствующей локальной кэш-памяти присут-
ствует копия данных, бит-указатель устанавливается в 1, иначе — в 0. Схема с пол-
ным справочником показана на рис. 11.17. Здесь предполагается, что копия строки
имеется в каждом кэше. Каждой строке придаются два индикатора состояния: бит

достоверности (V, Valid) и бит владения (Р, Private). Если информация в строке

корректна, ее V-бит устанавливается в 1. Единичное значение Р-бита указывает,

что данному процессору предоставлено право на запись в соответствующую стро-
ку своей локальной кэш-памяти.

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

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

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

нал, сбрасывает бит достоверности аннулируемой строки (V-бит) в 0 и возвращает
контроллеру справочника сигнал подтверждения. После приема всех сигналов под-

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

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

запись в собственную копию ячейки х, а также в основную память, если в кэше

реализована схема сквозной записи.

Основные проблемы протокола полного справочника связаны с большим ко-

личеством записей. Для каждой ячейки в справочнике системы из N процессоров
требуется N+ 1 бит, то есть с увеличением числа процессоров коэффициент слож-

ности возрастает линейно. Протокол полного справочника допускает наличие

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

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

 протоколе

с ограниченными справочниками

 копии отдельной строки вправе находиться только