Файл: Tannenbaum.pdf

Мультипроцессоры с памятью совместного использования 613

1 М строк, в каталоге содержится 1 М элементов, по одному элементу на каждую

строку. Каждый элемент содержит битовое отображение по одному биту на кластер.
Этот бит показывает, имеется ли в данный момент строка данного кластера в кэш-
памяти. Кроме того, элемент содержит 2-битное поле, которое сообщает о состоянии
строки.

1 М элементов по 18 битов каждый означает, что общий размер каждого ката-

лога превышает 2 Мбайт. При наличии 16 кластеров вся память каталога будет
немного превышать 36 Мбайт, что составляет около 14% от 256 Мбайт. Если чис-
ло процессоров на кластер возрастает, объем памяти каталога не меняется. Боль-
шое число процессоров на каждый кластер позволяет погашать стоимость памяти
каталога, а также контроллера шины при наличии большого числа процессоров,
сокращая стоимость на каждый процессор. Именно поэтому каждый кластер име-
ет несколько процессоров.

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

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

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

Каждая строка кэш-памяти может находиться в одном из трех следующих со-

стояний:

1. UNCACHED (некэшированная) — строка находится только в памяти.

2. SHARED (совместно используемая) — память содержит новейшие данные;

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

3. MODIFIED (измененная) — строка, содержащаяся в памяти, неправильная;

данная строка находится только в одной кэш-памяти.

Состояние каждой строки кэш-памяти содержится в поле

 Состояние

 в соответ-

ствующем элементе каталога, как показано на рис. 8.25,

 б.

Протоколы DASH основаны на обладании и признании недействительности.

В каждый момент у каждой строки имеется уникальный владелец. Для строк в со-
стоянии UNCHANGED или SHARED владельцем является собственный кластер

данной строки. Для строк в состоянии MODIFIED владельцем является тот клас-
тер, в котором содержится единственная копия этой строки. Прежде чем записать
что-либо в строку в состоянии SHARED, нужно найти и объявить недействитель-
ными все существующие копии.

Чтобы понять, как работает этот механизм, рассмотрим, как процессор считы-

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

6 1 4 Глава 8. Архитектуры компьютеров параллельного действия

дится в состоянии MODIFIED, нужно проинформировать исходный каталог, что

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

1 бит на кластер, а не 1 бит на каждый процессор).

Если нужная строка не присутствует ни в одной кэш-памяти данного кластера,

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

UNCACHED или SHARED, аппаратное обеспечение, которое управляет катало-
гом, вызывает эту строку из глобальной памяти и посылает ее обратно в запраши-
вающий кластер. Затем аппаратное обеспечение обновляет свой каталог, помечая

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

Если нужная строка находится в состоянии MODIFIED, аппаратное обеспече-

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

Запись происходит по-другому. Перед тем как осуществить запись, процессор

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

памяти в системе. Если в кэш-памяти данного процессора уже есть эта строка и
она находится в состоянии MODIFIED, то запись можно осуществить сразу же.
Если строка в кэш-памяти есть, но она находится в состоянии SHARED, то снача-

ла в исходный кластер посылается пакет, чтобы объявить все остальные копии
недействительными.

Если нужной строки нет в кэш-памяти данного процессора, этот процессор по-

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

Если строка находится где-либо еще, пакет посылается в исходный кластер.

Здесь может быть три варианта. Если строка находится в состоянии UNCACHED,
она помечается как MODIFIED и отправляется к запрашивающему процессору.
Если строка находится в состоянии SHARED, все копии объявляются недействи-
тельными, и после этого над строкой совершается та же процедура, что и над
UNCASHED строкой. Если строка находится в состоянии MODIFIED (измене-
на), то запрос направляется в тот кластер, в котором строка содержится в данный
момент. Этот кластер удовлетворяет запрос, а затем объявляет недействительной
свою собственную копию.

Сохранить согласованность памяти в системе DASH довольно трудно, и про-

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

Мультипроцессоры с памятью совместного использования

6 1 5

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

Мультипроцессор Sequent NUMA-Q

Машина DASH никогда не была коммерческим продуктом. В этом разделе мы рас-

смотрим одно из коммерческих изделий — машину Sequent NUMA-Q 2000. В ней
используется очень интересный протокол когерентности кэширования —

 SCI

(Scalable Coherent Interface — масштабируемый когерентный интерфейс).

 Этот

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

В основе машины NUMA-Q лежит стандартная плата

 quard board,

 которая про-

изведена компанией Intel. Плата содержит 4 процессора Pentium Pro и до 4 Гбайт
ОЗУ. Каждый процессор содержит кэш-память первого уровня и кэш-память вто-
рого уровня. Непротиворечивость кэшей сохраняется благодаря отслеживанию
локальной шины платы quard board с использованием протокола MESI. Скорость
передачи данных в локальной шине составляет 534 Мбайт/с. Размер строки кэш-
памяти равен 64 байтам. Схема мультипроцессора NUMA-Q изображена на рис. 8.26.

Интерфейс

отслеживающей шины

Контроллер каталога

99999

-<н>-

19999

9

Плата quad board

— с 4 процессорами Pentium Pro

и до 4 Гбайт ОЗУ

Кэш ОЗУ 32 Мбайт
Каталог

-П

-П
НИ

-а

Плата IQ

ОЗУ

Процессор

Рис. 8.26. Мультипроцессор NUMA-Q

Чтобы расширить систему, нужно вставить плату сетевого контроллера в гнездо

платы quad board, предназначенное для контроллеров сети. Сетевой контроллер,

6 1 6 Глава 8. Архитектуры компьютеров параллельного действия

плата IQ-Link,

 соединяет все платы quad board в один мультипроцессор. Ее глав-

ная задача — реализовать протокол SCI. Каждая плата IQ-Link содержит 32 Мбайт
кэш-памяти, каталог, который следит за тем, что находится в кэш-памяти, интер-
фейс с локальной шиной платы quad board и микросхему, называемую

 информа-

ционным ядром,

 соединяющую плату IQ-Link с другими платами IQ-Link. Эта

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

Все платы IQ-Link в совокупности формируют кольцо, как показано на рис. 8.26.

В данной разработке присутствует два уровня протокола когерентности кэширо-

вания. Протокол SCI поддерживает непротиворечивость всех кэшей платы IQ-Link,
используя это кольцо. Протокол MESI используется для сохранения непротиворе-
чивости между четырьмя процессорами и кэш-памятью на 32 Мбайт в каждом узле.

В качестве связи между платами quad board используется интерфейс SCI. Этот

интерфейс был разработан для того, чтобы заменить шину в больших мультипро-
цессорах и мультикомпьютерах (например, NUMA-Q). SCI поддерживает непроти-
воречивость кэшей, которая необходима в мультипроцессорах, а также позволяет
быстро передавать блоки, что необходимо в мультикомпьютерах. SCI выдержива-
ет нагрузку до 64 К узлов, адресное пространство каждого из которых может быть

до 2

48

 байтов. Самая большая система NUMA-Q состоит из 63 плат quad board, ко-

торые содержат 252 процессора и почти 2

38

 байтов физической памяти. Как видим,

возможности SCI гораздо выше.

Кольцо, которое соединяет платы IQ-Link, соответствует протоколу SCI. В дей-

ствительности это вообще не кольцо, а отдельные двухточечные кабели. Ширина
кабеля составляет 18 битов: 1 бит синхронизации, 1 флаговый бит и 16 битов

данных. Все они передаются параллельно. Каналы синхронизируются с тактовой
частотой 500 МГц, при этом скорость передачи данных составляет 1 Гбайт/с.

По каналам передаются пакеты. Каждый пакет содержит заголовок из 14 байтов, 0,

16, 64 или 256 байтов данных и контрольную сумму на 2 байта. Трафик состоит

из запросов и ответов.

Физическая память в машине NUMA-Q 2000 распределена по узлам, так что

каждая страница памяти имеет свою собственную машину. Каждая плата quad board
может вмещать до 4 Гбайт ОЗУ. Размер строки кэш-памяти равен 64 байтам, по-
этому каждая плата quad board содержит 2

26

 строк кэш-памяти. Когда строка не

используется, она находится только в одном месте — в собственной памяти.

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

дого узла должна существовать

 таблица локальной памяти

 из 2

26

 элементов, по

которой можно находить местоположение строк. Один из возможных вариантов —
иметь на каждый элемент таблицы битовое отображение, которое показывает, ка-
кие платы IQ-Link содержат эту строку. Но в SCI не используется такое битовое
отображение, поскольку оно плохо расширяется. (Напомним, что SCI может вы-

держивать нагрузку до 64 К узлов, и иметь 2

26

 элементов по 64 К битов каждый

было бы слишком накладно.)

Вместо этого все копии строки кэш-памяти собираются в дважды связанный

список. Элемент в таблице локальной памяти исходного узла показывает, в каком
узле содержится головная часть списка. В машине NUM A-Q 2000 достаточно 6-бит-
ного номера, поскольку здесь может быть максимум 63 узла. Для системы SCI мак-
симального размера достаточно будет 16-битного номера. Такая схема подходит

Мультипроцессоры с памятью совместного использования

6 1 7

для больших систем гораздо лучше, чем битовое отображение. Именно это свой-

ство делает SCI более расширяемой по сравнению с системой DASH.

Кроме таблицы локальной памяти, каждая плата IQ-Link содержит каталог

с одним элементом для каждой строки кэш-памяти, которую плата в данный
момент содержит. Поскольку размер кэш-памяти составляет 32 Мбайт, а строка
кэш-памяти включает 64 байта, каждая плата IQ-Link может содержать до 2

19

 строк

кэш-памяти. Поэтому каждый каталог содержит 2

1Э

 элементов, по одному элемен-

ту на каждую строку кэш-памяти.

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

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

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

Таблица локальной

памяти в узле

Каталог кэш-памяти узла 4 Каталог кэш-памяти узла 9 Каталог кэш-памяти узла 22

Рис. 8.27. Протокол SCI соединяет всех держателей данной строки в дважды связанный

список. В данном примере строка находится одновременно в трех узлах

Каждый элемент каталога состоит из 36 битов. Шесть битов указывают на узел,

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