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

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

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

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

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

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

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

с помощью централизованного контроллера, физически представляющего собой

часть контроллера основной памяти. Собственно справочник хранится в основ­

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

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

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

содержащей последнюю версию запрошенных данных. Центральный контроллер

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

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

яние блока данных.

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

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

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

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

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

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

кэшах, где такие копии имеются.

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

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

пии данной строки. Кроме того, в каждой записи выделен один бит модификации

(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 для каждого блока данных пре­

дусматривает шесть допустимых состояний. Этот протокол относительно прост

и подходит для любых топологий межсоединений процессоров. Справочник хра­

нится в основной памяти. В случае кэш-промаха при чтении происходит обраще­

ние к основной памяти, которая посылает сообщение являющейся

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

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

процессорам, совместно использующим эти данные, для того чтобы они обновили

свои битовые векторы. Схема не очень эффективна при большом числе процессо­

ров.

Не нашли, что искали? Воспользуйтесь поиском по сайту: