Файл: 481-550.pdf

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

в ограниченном числе кэшей — одновременно может быть не более чем

 п

 копий

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

 п

 (n <

 N).

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

2

N биT, а общая длина указателей в каж-

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

 пlog

2

N

 бит. При постоянном

значении

 п

 темпы роста коэффициента сложности ограниченного справочника по

мере увеличения размера системы ниже, чем в случае линейной зависимости.

Когда одновременно требуется более чем « копий, контроллер принимает ре-

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

Метод

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

 также имеет целью сжать объем справочника.

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

лизован как односвязный (однонаправленный) и двусвязный (двунаправленный).

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

В односвязном списке (рис. 11.18) каждая запись справочника содержит указа-

тель на копию строки в одном из локальных кэшей. Копии одноименных строк

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

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

длиной в

 N,

 то есть поддерживает

 N

 копий ячейки. При создании еще одной копии

цепочку нужно разрушить, а вместо нее сформировать новую. Пусть, например,
в процессоре 5 нет копии ячейки х и он обращается за ней к основной памяти. Ука-

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

 2.

 Для этого контроллер

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

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

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

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

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

Схемы на основе справочника «страдают» от «заторов» в централизованном

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

Ниже дана краткая характеристика актуальных на настоящее время протоко-

лов обеспечения когерентности кэш-памяти на основе справочника. Для деталь-

ного ознакомления с этими протоколами приведены ссылки на соответствующие

литературные источники.

Протокол Tang.

 Здесь присутствует централизованный глобальный справоч-

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

Протокол Censier. В

 схеме справочника Censier для указания того, какие процес-

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

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

для обновления строк кэша требуется доступ к основной памяти [155].

Протокол Archibald.

 Схема справочника Archibald — это пара замысловатых

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

Протокол Stenstrom.

 Справочник Stenstrom для каждого блока данных пре-

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

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

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

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

Контрольные вопросы

1. Проанализируйте влияние особенностей ВС с общей памятью и ВС с распреде-

ленной памятью на разработку программного обеспечения. Почему эти ВС на-
зывают соответственно сильно связанными и слабо связанными?

2. Поясните идею с чередованием адресов памяти. Из каких соображений выбира-

ется механизм распределения адресов? Как он связан с классом архитектуры ВС?

Контрольные вопросы  5 2 3

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

к памяти.

4. В чем заключаются преимущества архитектуры СОМА?
5. Проведите сравнительный анализ моделей с кэш-когерентным и кэш-некоге-

рентным доступом к неоднородной памяти.

6. Сформулируйте достоинства и недостатки архитектуры без прямого доступа

к удаленной памяти.

7. Объясните смысл распределенной и совместно используемой памяти.
8. Разработайте свой пример, иллюстрирующий проблему когерентности кэш-

памяти.

9. Охарактеризуйте особенности программных способов решения проблемы ко-

герентности, выделите их преимущества и слабые стороны.

10. Сравните методики записи в память с аннулированием и записи в память с тран-

сляцией, акцентируя их достоинства и недостатки.

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

в мультипроцессорных системах.

12. Выполните сравнительный анализ известных вам протоколов наблюдения.
13. Какой из протоколов наблюдения наиболее популярен? Обоснуйте причины

повышенного к нему интереса.

14. Дайте развернутую характеристику протоколов когерентности на основе спра-

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

Глава 12

Топологии вычислительных

систем

В основе архитектуры любой многопроцессорной вычислительной системы лежит

способность к обмену данными между компонентами этой ВС. Коммуникацион-

ная система ВС представляет собой

 сетъ,узлы

 которой связаны трактами передачи

данных —

 каналами.

 В роли узлов могут выступать процессоры, модули памяти,

устройства ввода/вывода, коммутаторы либо несколько перечисленных элемен-
тов, объединенных в группу. Организация внутренних коммуникаций вычисли-
тельной системы называется

 топологией.

Топологию сети межсоединений (CMC) определяет множество узлов N объе-

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

 двух-

точечной схеме

 (point-to-point). Любые два узла, связанные каналом связи, назы-

вают смежными узлами или соседями. Каждый канал С соединяет один

узел-источник

 (source node)

 х

 с одним

 узлом-получателем

 (recipient node)

 у,

 где

 х,

Узел-источник, служащий началом канала с, будем обозначать

 s

c

 а узел-по-

лучатель — второй конец канала — r

с

.

 Часто пары узлов соединяют два канала -

по одному в каждом направлении. Канал с =

 (х, у)

 характеризуется шириной

 (w

c

или w

xy

) — числом сигнальных линий; частотой (f

с

 или f

xy

) — скоростью передачи

битов по каждой сигнальной линии; задержкой

 (t

c

 или t

xy

) — временем пересылки

бита из узла

 х

 в узел

 у.

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

симости от физической длины линии связи (l

с

) и скорости распространения сигнала

(v):l

c

 =

vt

c

 Полоса пропускания канала b

с

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

 b

c

 = wf

c

.

В зависимости от того, остается ли конфигурация взаимосвязей неизменной,

по крайней мере пока выполняется определенное задание, различают сети со

 ста-

тической

 и

 динамической

 топологиями. В статических сетях структура взаимосвя-

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

изменена.

Узел в сети может быть терминальным, то есть источником или приемником

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

ной, или совмещать обе роли. В сетях

 с непосредственными связями

 (direct networks)

Топологии вычислительных систем  5 2 5

каждый узел одновременно является как терминальным узлом, так и коммутато-

ром, и сообщения пересылаются между терминальными узлами напрямую. В се-
тях

 с косвенными связями

 (indirect networks) узел может быть либо терминальным,

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

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

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

Тремя важнейшими атрибутами CMC являются:

-

 стратегия синхронизации;

- стратегия коммутации;
- стратегия управления.

Две возможных стратегии синхронизации операций в сети — это

 синхронная

и

 асинхронная.

 В синхронных CMC все действия жестко согласованы во времени,

что обеспечивается за счет единого генератора тактовых импульсов (ГТИ), сигна-
лы которого одновременно транслируются во все узлы. В асинхронных сетях еди-

ного генератора нет, а функции синхронизации распределены по всей системе,
причем в разных частях сети часто используются локальные ГТИ.

В зависимости от выбранной стратегии коммутации различают

 сети с комму-

тацией соединений

 и

 сети с коммутацией пакетов.

 Как в первом, так и во втором

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

 Пакет

 представляет собой

группу битов, для обозначения которой применяют также термин

 сообщение.

В сетях с коммутацией соединений путем соответствующей установки комму-

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

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

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

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