Материал: Tannenbaum

608

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

Программисты часто называют ее

 аппаратной DSM (Distributed Shared Memory —

распределенная совместно используемая память),

 поскольку она по сути сходна

с программной DSM, но реализуется в аппаратном обеспечении с использованием
страниц маленького размера.

Одной из первых машин NC-NUMA была Carnegie-Mellon Cm*. Она проиллю-

стрирована в упрощенной форме рис. 8.23 [143]. Машина состояла из набора
процессоров LSI-11, каждый с собственной памятью, обращение к которой произ-
водится по локальной шине. (LSI-11 — это один из видов процессора DEC PDP-11
на одной микросхеме; этот мини-компьютер был очень популярен в 70-е годы.)
Кроме того, системы LSI-11 были связаны друг с другом системной шиной. Когда

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

ной памяти занимало в 10 раз больше времени, чем выполнение той же программы

из локальной памяти.

Процессор Память Процессор Память Процессор Память Процессор Память

Контроллер

управления-

памятью

Локальная

шина

Локальная

шина

Локальная

шина

Локальная

шина

Системная шина

Рис. 8.23. Машина NUMA с двумя уровнями шин. Cm* — первый мультипроцессор,

в котором использовалась данная разработка

Согласованность памяти гарантирована в машине NC-NUMA, поскольку там

отсутствует кэш-память. Каждое слово памяти находится только в одном месте,
поэтому нет никакой опасности появления копии с устаревшими данными: здесь
вообще нет копий. Имеет большое значение, в какой именно памяти находится та
или иная страница, поскольку от этого зависит производительность. Машины NC-
NUMA используют сложное программное обеспечение для перемещения страниц,
чтобы максимально увеличить производительность.

Обычно существует «сторожевой» процесс (демон), так называемый странич-

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

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

множество алгоритмов, но ни один из них не работает лучше других при любых
обстоятельствах [80].

Мультипроцессоры CC-NUMA

Мультипроцессоры, подобные тому, который изображен на рис. 8.23, плохо рас-
ширяются, поскольку в них нет кэш-памяти. Каждый раз переходить к удаленной
памяти, чтобы получить доступ к слову, которого нет в локальной памяти, очень
невыгодно: это сильно снижает производительность. Однако с добавлением кэш-
памяти нужно будет добавить и способ совместимости кэшей. Один из способов —
отслеживать системную шину. Технически это сделать несложно, но мы уже виде-
ли (когда рассматривали Enterprise 10000), что даже с четырьмя отслеживающи-
ми шинами и высокоскоростным координатным коммутатором шириной 16 байтов

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

Самый популярный подход для построения больших мультипроцессоров

 CC-

NUMA (Cache Coherent NUMA — NUMA с согласованной кэш-памятью) — муль-

типроцессор на основе каталога.

 Основная идея состоит в сохранении базы дан-

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

ном аппаратном обеспечении, которое способно выдавать ответ на запрос за долю
цикла шины.

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

лога, рассмотрим в качестве примера систему из 256 узлов, в которой каждый узел

состоит из одного процессора и 16 Мбайт ОЗУ, связанного с процессором через

локальную шину. Общий объем памяти составляет 2

32

 байтов. Она разделена на

2

26

 строк кэш-памяти по 64 байта каждая. Память статически распределена по

узлам: 0-16 М в узле 0, 16 М-32 М — в узле 1 и т. д. Узлы связаны через сеть

(рис. 8.24,

 а).

 Сеть может быть в виде решетки, гиперкуба или другой топологии.

Каждый узел содержит элементы каталога для 2

18

 64-байтных строк кэш-памяти,

составляя свою 2

24

-байтную память. На данный момент мы предполагаем, что строка

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

Чтобы понять, как работает каталог, проследим путь команды LOAD из процессо-

ра 20, который обращается к кэшированной строке. Сначала процессор, выдавший
команду, передает ее в блок управления памятью, который переводит ее в физи-
ческий адрес, например 0x24000108. Блок управления памятью разделяет этот
адрес на три части, как показано на рис. 8.24,

 6.

 В десятичной системе счисления

эти три части — узел 36, строка 4 и смещение 8. Блок управления памятью видит,
что слово памяти, к которому производится обращение, находится в узле 36, а не
в узле 20, поэтому он посылает запрос через сеть в узел 36, где находится нужная
строка, узнает, есть ли строка 4 в кэш-памяти, и если да, то где именно.

Когда запрос прибывает в узел 36, он направляется в аппаратное обеспечение

каталога. Аппаратное обеспечение индексирует таблицу их 2

18

 элементов (один

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

элемент на каждую строку кэш-памяти) и извлекает элемент 4. Из рис. 8.24,

 в

видно, что эта строка отсутствует в кэш-памяти, поэтому аппаратное обеспечение
вызывает строку 4 из локального ОЗУ, отправляет ее в узел 20 и обновляет эле-
мент каталога 4, чтобы показать, что эта строка находится в кэш-памяти в узле 20.

Узел 0

Процессор Память

Каталог

Локальная

шина

Узел 1

Процессор Память

Локальная

шина

Узел 256

Процессор Память

СП

Локальная

шина

Сеть межсоединений

Биты 8

18

Узел

Блок

Смещение

2

1 8

-1

I

0
0

J l

~ol

0

82

Рис. 8.24.

 Мультипроцессор на основе каталога, содержащий 256 узлов (а);

разбиение 32-битного адреса памяти на поля (б); каталог в узле 36 (в)

А теперь рассмотрим второй запрос, на этот раз о строке 2 из узла 36. Из рис.

8.24,

 в

 видно, что эта строка находится в кэш-памяти в узле 82. В этот момент аппа-

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

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

жит 16 Мбайт ОЗУ и 2

18

 9-битных элементов для слежения за этим ОЗУ. Таким

образом, непроизводительные затраты каталога составляют примерно 9х2

18

 битов

от 16 Мбайт или около 1,76%, что вполне допустимо. Даже если длина строки
кэш-памяти составляет 32 байта, непроизводительные затраты составят всего 4%.
Если длина строки кэш-памяти равна 128 байтов, непроизводительные затраты
будут ниже 1%.

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

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

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

Одна из возможностей — предоставить каждому элементу каталога к полей для

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

 k

 различных узлов). Вторая возможность —

заменить номер узла битовым отображением, один бит на узел. Здесь нет огра-
ничений на количество копий, но существенно растут непроизводительные затра-
ты. Каталог, содержащий 256 битов для каждой 64-байтной (512-битной) строки
кэш-памяти, подразумевает непроизводительные затраты выше 50%. Третья воз-
можность — хранить в каждом элементе каталога 8-битное поле и использовать
это поле как заголовок связанного списка, который связывает все копии строки
кэш-памяти вместе. При такой стратегии требуется дополнительное пространство
в каждом узле для указателей связанного списка. Кроме того, требуется просмат-
ривать связанный список, чтобы в случае необходимости найти все копии. Каждая
из трех стратегий имеет свои преимущества и недостатки. На практике использу-
ются все три стратегии.

Еще одна проблема данной разработки — как следить за тем, обновлена ли ис-

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

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

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

существует только одна копия строки кэш-памяти. Если существует несколько
копий, изменение одной из них требует объявления всех остальных недействи-
тельными. Поэтому нужен какой-либо протокол, чтобы устранить ситуацию со-
стояния гонок. Например, чтобы изменить общую строку кэш-памяти, один из дер-
жателей этой строки должен запросить монопольный доступ к ней перед тем, как
изменить ее. В результате все другие копии будут объявлены недействительными.
Другие возможные оптимизации CC-NUMA обсуждаются в книге [140].

Мультипроцессор Stanford DASH

Первый мультипроцессор CC-NUMA на основе каталога —

 DASH (Directory

Architecture for SHared memory — архитектура на основе каталога для памяти
совместного использования)

 — был создан в Стенфордском университете как ис-

следовательский проект [81]. Данная разработка проста для понимания. Она повли-
яла на ряд промышленных изделий, например SGI Origin 2000. Мы рассмотрим
64-процессорный прототип данной разработки, который был реально сконструи-
рован. Он подходит и для машин большего размера.

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

 а.

Она состоит из 16 кластеров, каждый из которых содержит шину, 4 процессора
MIPS R3000, 16 Мбайт глобальной памяти, а также некоторые устройства вво-

да-вывода (диски и т. д.), которые на схеме не показаны. Каждый процессор отсле-
живает только свою локальную шину. Локальная совместимость поддерживается

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

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

Межкластерный интерфейс

Процессор

с кэш-памятью

Память

Межкластерная шина

(без отслеживания

изменений по адресам)

Локальная шина

(с отслеживанием

изменений по адресам)

Кластер

Каталог

Кластер

Состояние

Блок

Р

3

2

Г,

0

0 1 2 3 4 5 6 7 8 9 И

Ь

/

I

Это каталог кластера13. 2 | | | | | | | | [ | | | | | | | |

 -+\

— Uncached, shared, modified

Этот бит показывает,

содержится ли блок 1

в какой-нибудь кэш-памяти

кластера 0 g

Рис.

 8.25. Архитектура DASH (а); каталог DASH (б)

Полный объем адресного пространства в данной системе равен 256 Мбайт.

Адресное пространство разделено на 16 областей по 16 Мбайт каждая. Глобальная
память кластера 0 включает адреса с 0 по 16 М. Глобальная память кластера 1 вклю-
чает адреса с 16 М по 32 М и т. д. Размер строки кэш-памяти составляет 16 байтов.
Передача данных также осуществляется по строкам в 16 байтов. Каждый кластер
содержит 1 М строк.

Каждый кластер содержит каталог, который следит за тем, какие кластеры в на-

стоящий момент имеют копии своих строк. Поскольку каждый кластер содержит