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

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

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

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

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

В настоящее время известны три способа реализации протоколов когерентности кэш-памяти на основе справочника: полный справочник, ограниченные справочники и сцепленные справочники.

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

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

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

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

Основные проблемы протокола полного справочника связаны с большим количеством записей. Для каждой ячейки в справочнике системы из N процессоров требуется N+1 бит, то есть с увеличением числа процессоров коэффициент сложности возрастает линейно. Протокол полного справочника допускает наличие в каждом локальном кэше копий всех совместно используемых ячеек. На практике такая возможность далеко не всегда остается востребованной — в каждый конкретный момент обычно используется лишь одна или несколько копий. В протоколе с ограниченными справочниками копии отдельной строки могут находиться только в ограниченном числе кэшей — одновременно может быть не более чем n копий строки, при этом число указателей в записях справочника уменьшается до n (n < N). Чтобы однозначно идентифицировать кэш-память, хранящую копию, указатель вместо одного бита должен состоять из log₂N бит, а общая длина указателей в каждой записи справочника вместо N бит будет равна nlog₂N бит. При постоянном значении n темпы роста коэффициента сложности ограниченного справочника по мере увеличения размера системы ниже, чем в случае линейной зависимости.

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

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

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

В односвязном списке (рис. 11.18) каждая запись справочника содержит указатель на копию строки в одном из локальных кэшей. Копии одноименных строк в разных кэшах системы образуют цепочку. Для этого в их тегах предусмотрено специальное поле, куда заносится указатель на кэш-память, содержащую следующую копию цепочки. В тег последней копии цепочки заносится специальный символ — ограничитель. Сцепленный справочник допускает цепочки длиной в N, то есть поддерживает N копий ячейки. При создании еще одной копии цепочку нужно разрушить, а вместо нее сформировать новую. Пусть, например, в процессоре 5 нет копии ячейки x и он обращается за ней к основной памяти. Указатель в справочнике изменяется так, чтобы указывать на кэш с номером 5, а указатель в кэше 5 изменяется таким образом, чтобы указывать на кэш 2. Для этого контроллер основной памяти наряду с затребованными данными должен передать в кэш-память 5 также и указатель на кэш-память с номером 2. Лишь после того как будет сформирована вся структура цепочки, процессор 5 получит разрешение на доступ к ячейке x. Если процессор производит запись в ячейку, то вниз по тракту, определяемому соответствующей цепочкой указателей, посылается сигнал аннулирования. Цепочка должна обновляться и при удалении копии из какой-либо кэш-памяти.

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

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

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

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

Протокол Censier. В схеме справочника Censier для указания того, какие процессоры содержат локальную копию данного блока памяти, используется битовый вектор указателей. Такой вектор имеется для каждого блока памяти. Недостатками метода является его неэффективность при большом числе процессоров и, кроме того, для обновления содержимого блоков кэша требуется доступ к основной памяти [LILJ93].

Протокол Archibald. Схема справочника Archibald — это замысловатая пара схем для иерархически организованных сетей процессоров. С детальным описанием этого протокола можно ознакомится в [ARCH88].

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