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

В системе из N процессоров каждая запись справочника будет содержать N од
нобитовых указателей. Если в соответствующей локальной кэш-памяти присут
ствует копия данных, бит-указатель устанавливается в 1, иначе - в 0. Схема с пол
ным справочником показана на рис. 11.17. Здесь предполагается, что копия строки
имеется в каждом кэше. Каждой строке придаются два индикатора состояния: бит
достоверности (V, Valid) и бит владения (Р, Private). Если информация в строке
корректна, ее V-бит устанавливается в 1. Единичное значение Р-бита указывает,
что данному процессору предоставлено право на запись в соответствующую стро
ку своей локальной кэш-памяти.
Предположим, что процессор 2 производит запись в ячейку х. В исходный мо
мент процессор не получил еще разрешения на такую запись. Он формирует за-В ответ на запрос во все кэши, где есть копии строки, содержащей ячейку х, вы да-ется сигнал аннулирования имеющихся копий. Каждый кэш, получивший этот сиг
нал, сбрасывает бит достоверности аннулируемой строки (V-бит) в 0 и возвращает
контроллеру справочника сигнал подтверждения. После приема всех сигналов под
тверждения контроллер справочника устанавливает в единицу бит модификации
(D-бит) соответствующей записи справочника и посылает процессору 2 сигнал,
разрешающий запись в ячейку х. С этого момента процессор 2 может продолжить
запись в собственную копию ячейки х, а также в основную память, если в кэше
реализована схема сквозной записи.
Основные проблемы протокола полного справочника связаны с большим ко
личеством записей. Для каждой ячейки в справочнике системы из N процессоров
требуется N+ 1 бит, то есть с увеличением числа процессоров коэффициент слож
ности возрастает линейно. Протокол полного справочника допускает наличие
в каждом локальном кэше копий всех совместно используемых ячеек. На практи
ке такая возможность далеко не всегда остается востребованной - в каждый конк
ретный момент обычно актуальны лишь одна или несколько копий. В протоколе
с ограниченными справочниками копии отдельной строки вправе находиться только
Мультипроцессорная когерентность кэш-памяти 5 2 1
в ограниченном числе кэшей - одновременно может быть не более чем и копий
строки, при этом число указателей в записях справочника уменьшается до п (n < N).
Чтобы однозначно идентифицировать кэш-память, хранящую копию, указатель
вместо одного бита должен состоять из log
N биT, а общая длина указателей в каж
дой записи справочника вместо N бит будет равна бит. При постоянном
значении п темпы роста коэффициента сложности ограниченного справочника по
мере увеличения размера системы ниже, чем в случае линейной зависимости.
Когда одновременно требуется более чем « копий, контроллер принимает ре
шение, какие из копий сохранить, а какие аннулировать, после чего производятся
соответствующие изменения в указателях записей справочника.
Метод сцепленных справочников также имеет целью сжать объем справочника.
В нем для хранения записей привлекается связный список, который может быть реа
лизован как односвязный (однонаправленный) и двусвязный (двунаправленный).

В односвязном списке (рис. 11.18) каждая запись справочника содержит указа
тель на копию строки в одном из локальных кэшей. Копии одноименных строк
в разных кэшах системы образуют однонаправленную цепочку. Для этого в их тегах
предусмотрено специальное поле, куда заносится указатель на кэш-память, содер
жащую следующую копию цепочки. В тег последней копии цепочки помещается
специальный символ-ограничитель. Сцепленный справочник допускает цепочки
длиной в N, то есть ячейки. При создании еще одной копии
цепочку нужно разрушить, а вместо нее сформировать новую. Пусть, например,
в процессоре 5 нет копии ячейки х и он обращается за ней к основной памяти. Ука
затель в справочнике изменяется так, чтобы указывать на кэш с номером 5, а ука
затель в кэше 5 — таким образом, чтобы указывать на кэш 2. Для этого контроллер
основной памяти наряду с затребованными данными должен передать в кэш-па
мять 5 также и указатель на кэш-память с номером 2. Лишь после того, как будет
сформирована вся структура цепочки, процессор 5 получит разрешение на доступ
к ячейке х. Если процессор производит запись в ячейку, то вниз по тракту, опреде
ляемому соответствующей цепочкой указателей, посылается сигнал аннулирования. Цепочка должна обновляться и при удалении копии из какой-либо кэш-памяти.
Двусвязный список поддерживает указатели как в прямом, так и в обратном на
правлениях. Это позволяет более эффективно вставлять в цепочку новые указатели
или удалять из нее уже не нужные, но требует хранения большего числа указателей.
Схемы на основе справочника «страдают» от «заторов» в централизованном
контроллере, а также от коммуникационных издержек в трактах между контрол
лерами локальных кэшей и центральным контроллером. Тем не менее они оказы
ваются весьма эффективными в мультипроцессорных системах со сложной топо
логией взаимосвязей между процессорами, где невозможно реализовать протоколы
наблюдения.
Ниже дана краткая характеристика актуальных на настоящее время протоко
лов обеспечения когерентности кэш-памяти на основе справочника. Для деталь
ного ознакомления с этими протоколами приведены ссылки на соответствующие
литературные источники.
Протокол Tang. Здесь присутствует централизованный глобальный справоч
ник, содержащий полную копию всей информации из каталогов каждого из ло-кальных кэшей [212]. Это приводит к проблеме узких мест, а также требует поиска
соответствующих входов.
Протокол Censier. В схеме справочника Censier для указания того, какие процес
соры содержат локальную копию данного блока памяти, используется битовый век
тор указателей. Такой вектор имеется для каждого блока памяти. Недостатками ме
тода является его неэффективность при большом числе процессоров, и, кроме того,
для обновления строк кэша требуется доступ к основной памяти [155].
Протокол Archibald. Схема справочника Archibald — это пара замысловатых
схем для иерархически организованных сетей процессоров, С детальным описа
нием этого протокола можно ознакомиться в [52].
Протокол Stenstrom. Справочник Stenstrom для каждого блока данных пре
дусматривает шесть допустимых состояний. Этот протокол относительно прост
и подходит для любых топологий межсоединений процессоров. Справочник хра
нится в основной памяти. В случае кэш-промаха при чтении происходит обраще
ние к основной памяти, которая посылает сообщение являющейся
владельцем блока, если такой находится. Получив это сообщение, кэш-владелец
посылает затребованные данные, а также направляет сообщение всем остальным
процессорам, совместно использующим эти данные, для того чтобы они обновили
свои битовые векторы. Схема не очень эффективна при большом числе процессо
ров.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2023 stydopedia.ru Все материалы защищены законодательством РФ.
|