Танненбаум Е. Архітектура компютера [pdf]

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

Мультипроцессоры UMA с координатными коммутаторами

Даже при всех возможных оптимизациях использование только одной ш ограничивает размер мультипроцессора UMA до 16 или 32 процессоров. Чт получить больший размер, требуется другой тип коммуникационной сети. Са простая схема соединения п процессоров с к блоками памяти — координатный мутатор (рис. 8.19). Координатные коммутаторы используются на протяже многих десятилетий для соединения группы входящих линий с рядом выходя линий произвольным образом.

Модулипамяти

Координатн

коммутато

открыт

Координатн

коммутато

закрыт

Закрытый	Открытый
координатный	координатный
коммутатор	коммутатор

Рис. 8.19. Координатный коммутатор 8x8 (а); открытый узел (б); закрытый узел (в)

В каждом пересечении горизонтальной (входящей) и вертикальной (исх щей) линии находится соединение (crosspoint), которое можно открыть или крыть в зависимости от того, нужно соединять горизонтальную и вертикаль линии или нет. На рис. 8.19, а мы видим, что три узла закрыты, благодаря ч устанавливается связь между парами (процессор, память) (001, 000), (101, 10 (110, 010) одновременно. Возможны другие комбинации. Число комбинаций

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

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

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

Не лучшим свойством координатного коммутатора является то, что ч лов растет как п2. При наличии 1000 процессоров и 1000 блоков памяти н добится миллион узлов. Это неприемлемо. Тем не менее координатные к торы вполне применимы для систем средних размеров.

Sun Enterprise 10000

В качестве примера мультипроцессора UMA, основанного на координатн мутаторе, рассмотрим систему Sun Enterprise 10000 [23, 24]. Эта система из одного корпуса с 64 процессорами. Координатный коммутатор Giga запакован в плату, содержащую 8 гнезд на каждой стороне. Каждое гнездо ет огромную плату процессора (40x50 см), содержащую 4 процессора Ultr на 333 МГц и ОЗУ на 4 Гбайт. Благодаря жестким требованиям к синхро и малому времени ожидания доступ к памяти вне платы занимает столько мени, сколько доступ к памяти на плате.

Иметь только одну шину для взаимодействия всех процессоров и все памяти неудобно, поэтому в системе Enterprise 10000 применяется друга гия. Здесь есть координатный коммутатор 16x16 для перемещения данны основной памятью и блоками кэш-памяти. Длина строки кэш-памяти со 64 байта, а ширина канала связи составляет 16 байтов, поэтому для перем строки кэш-памяти требуется 4 цикла. Координатный коммутатор работает к точке, поэтому его нельзя использовать для сохранения совместимости памяти.

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

адресные шины одновременно, поэтому если ответа нет, это значит, что мая строка отсутствует в кэш-памяти и ее нужно вызывать из основной п Вызов из памяти происходит от точки к точке по координатному ком по 16 байтов. Цикл шины составляет 12 не (83,3 МГц), и каждая адресн может отслеживаться в каждом цикле любой другой шины, то есть всего в 167 млн отслеживаний/с. Каждое отслеживание может потребовать п строки кэш-памяти в 64 байта, поэтому узел должен быть способен пе 9,93 Гбайт/с (напомним, что 1 Гбайт= 1,0737x109 байт/с, а не 109байт/с). кэш-памяти в 64 байта можно передать через узел за 4 цикла шины (48

		Мультипроцессоры с памятью совместного использования	60
Блок
передачи —		Координатный коммутатор 16x16 (Gigaplane XB)
этоблок
кэш-памяти
размером		ПроцессорUltraSPARC
64 байта
Плата		,
содержит

	4 Гбайт памяти	Ч Модуль памяти
	и 4 процессора
		размером1Гбайт

4-адресные Г шины для J отслеживания 1 изменений

по адресам

Рис. 8.20. Мультипроцессор Sun Enterprise 10000

Enterprise 10000 использует 4 отслеживающие шины параллельно, плюс очен широкий координатный коммутатор для передачи данных. Ясно, что такая систе ма преодолевает предел в 64 процессора. Но чтобы существенно увеличить коли чество процессоров, требуется совсем другой подход.

Мультипроцессоры UMA

с многоступенчатыми сетями

В основе «совсем другого подхода» лежит небольшой коммутатор 2x2 (рис. 8.21, а Этот коммутатор содержит два входа и два выхода. Сообщения, приходящие на лю бую из входных линий, могут переключаться на любую выходную линию. В на шем примере сообщения будут содержать до четырех частей (рис. 8.21, б). Пол Модуль сообщает, какую память использовать. Поле Адрес определяет адрес в это модуле памяти. В поле Код операции содержится операция, например READ ил WRITE. Наконец,дополнительное полеЗначениеможетсодержатьоперанд, наприме 32-битное слово, которое нужно записать при выполнении операции WRITE. Комму татор исследует поле Модуль и использует его для определения, через какую выход ную линию нужно отправить сообщение: через X или через Y.

А —	— х	Модуль	Адрес Код операции Значениеi
	•Y
а			б

Рис. 8.21. Коммутатор2x2(а); форматсообщения (б)

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

коммутаторов, что намного лучше, чем п2узлов (точек пересечения), особ больших п.

3 ступени

Процессоры

~000

Рис. 8.22. Сеть omega

Рисунок разводки сети omega часто называют полным тасованием, п смешение сигналов на каждой ступени напоминает колоду карт, которую ли пополам, а затем снова соединили, чередуя карты. Чтобы понять, как сеть omega, предположим, что процессору 011 нужно считать слово из м мяти 110. Процессор посылает сообщение READ, чтобы переключить ко ID, который содержит 110 в поле Модуль. Коммутатор берет первый (то е ний левый) бит от 110 и по нему узнает направление. 0 указывает на верхн а 1 — на нижний. Поскольку в данном случае этот бит равен 1, сообщени ляется через нижний выход в 2D.

Все коммутаторы второй ступени, включая 2D, для определения нап используют второй бит. В данном случае он равен 1, поэтому сообщение ется через нижний выход в 3D. Затем проверяется третий бит. Он равен 0. тельно, сообщение переходит в верхний выход и прибывает в память 110 идобивались. Путь,пройденныйданнымсообщением,обозначеннарис. 8.22

Как только сообщение пройдет через сеть, крайние левые биты номе больше не требуются. Их можно использовать, записав туда номер входн чтобы было известно, по какому пути посылать ответ. Для пути а входные это 0 (верхний вход в ID), 1 (нижний вход в 2D) и 1 (нижний вход в 3D ственно. При отправке ответа тоже используется 011, только теперь числ ся справа налево.

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

ется через верхний, верхний и нижний выходы соответственно. На рис

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

60

А теперь рассмотрим, что произойдет, если процессору 000 одновременно с эти понадобился доступ к модулю памяти 000. Его запрос вступит в конфликт с запро сом процессора 001 на коммутаторе ЗА. Одному из них придется подождать. В отли чие от координатного коммутатора, сеть omega — это блокируемая сеть. Не всяки набор запросов может передаваться одновременно. Конфликты могут возникат при использовании одного и того же провода или одного и того же коммутатора, также между запросами, направленными к памяти, и ответами, исходящими и памяти.

Желательно равномерно распределить обращения к памяти по модулям. Оди из возможных способов — использовать младшие биты в качестве номера модул памяти. Рассмотрим адресное пространство с побайтовой адресацией для компью тера, который в основном получает доступ к 32-битным словам. Два младши бита обычно будут 00, но следующие три бита будут равномерно распределен Если использовать эти три бита в качестве номера модуля памяти, последовательн адресуемые слова будут находиться в последовательных модулях. Система памят в которой последовательные слова находятся в разных модулях памяти, называе ся расслоенной. Расслоенная система памяти доводит параллелизм до максим ма, поскольку большая часть обращений к памяти — это обращения к последов тельным адресам. Можно разработать неблокируемые сети, в которых существуе несколько путей от каждого процессора к каждому модулю памяти.

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

Размер мультипроцессоров UMA с одной шиной обычно ограничивается до н скольких десятков процессоров, адля координатных мультипроцессоров или мул типроцессоров с коммутаторами требуется дорогое аппаратное обеспечение, и он ненамного больше по размеру. Чтобы получить более 100 процессоров, нужно чт то предпринять. Отметим, что все модули памяти имеют одинаковое время доступ Это наблюдение приводит к разработке мультипроцессоров NUMA (NonUnifor MemoryAccess —снеоднороднымдоступомкпамяти).Какимультипроцессор UMA, они обеспечивают единое адресное пространство для всех процессоров, н в отличие от машин UMA, доступ к локальным модулям памяти происходит бы трее, чем к удаленным. Следовательно, все программы UMA будут работать бе изменений на машинах NUMA, но производительность будет хуже, чем на маши не UMA с той же тактовой частотой.

Машины NUMA имеют три ключевые характеристики, которыми все они обл дают и которые в совокупности отличают их от других мультипроцессоров:

1.Существует одно адресное пространство, видимое для всех процессоров.

2.ДоступкудаленнойпамятипроизводитсясиспользованиемкомандLOADиSTOR

3.Доступ к удаленной памяти происходит медленнее, чем доступ к локально

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

ПрограммистычастоназываютееаппаратнойDSM (DistributedSharedM распределенная совместно используемая память), поскольку она по сут с программной DSM, но реализуется в аппаратном обеспечении с использ страниц маленького размера.

Одной из первых машин NC-NUMA была Carnegie-Mellon Cm*. Она п стрирована в упрощенной форме рис. 8.23 [143]. Машина состояла и процессоров LSI-11, каждый с собственной памятью, обращение к которо водится по локальной шине. (LSI-11 — это один из видов процессора DEC на одной микросхеме; этот мини-компьютер был очень популярен в 70 Кроме того, системы LSI-11 были связаны друг с другом системной шино запрос памяти приходил в блок управления памятью, производилась пр определялось, находится ли нужное слово в локальной памяти. Если да, т отправлялся по локальной шине. Если нет, то запрос направлялся по си шине к системе, которая содержала данное слово. Естественно, вторая о занимала гораздо больше времени, чем первая. Выполнение программы и ной памяти занимало в 10 раз больше времени, чем выполнение той же пр из локальной памяти.

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

Контроллер
управления-
памятью	Локальная	Локальная	Локальная	Ло
	шина	шина	шина

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

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

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

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

к ней вызвало ошибку из-за отсутствия страницы. Когда происходит така

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

609

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

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

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

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

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

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

Чтобы лучше понять, что собой представляет мультипроцессор на основе каталога, рассмотрим в качестве примера систему из 256 узлов, в которой каждый узел состоит из одного процессора и 16 Мбайт ОЗУ, связанного с процессором через локальную шину. Общий объем памяти составляет 232 байтов. Она разделена на 226 строк кэш-памяти по 64 байта каждая. Память статически распределена по узлам: 0-16 М в узле 0, 16 М-32 М — в узле 1 и т. д. Узлы связаны через сеть (рис. 8.24, а). Сеть может быть в виде решетки, гиперкуба или другой топологии. Каждый узел содержит элементы каталога для 218 64-байтных строк кэш-памяти, составляя свою 224-байтную память. Наданныймоментмы предполагаем, что строка может содержаться максимум в одной кэш-памяти.

Чтобы понять, как работает каталог, проследим путь команды LOAD из процессора 20, который обращается к кэшированной строке. Сначала процессор, выдавший команду, передает ее в блок управления памятью, который переводит ее в физический адрес, например 0x24000108. Блок управления памятью разделяет этот адрес на три части, как показано на рис. 8.24, 6. В десятичной системе счисления эти три части — узел 36, строка 4 и смещение 8. Блок управления памятью видит,

что слово памяти, к которому производится обращение, находится в узле 36, а не

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

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

	Узел 0	Узел 1	Узел
Процессор Память		Процессор Память	Процессор
Каталог			СП
	Локальная	Локальная	Лок
	шина	шина	ш
		Сеть межсоединений
Биты 8	18	21 8 -1	I
Узел	Блок	Смещение
		0
		0
		J l	82
		~ol
		0

Рис. 8.24. Мультипроцессор на основе каталога, содержащий 256 узлов (а); разбиение 32-битного адреса памяти на поля (б); каталог в узле 36 (в)

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

Давайте вычислим, сколько памяти занимают каталоги. Каждый узел жит 16 Мбайт ОЗУ и 218 9-битных элементов для слежения за этим ОЗУ. образом, непроизводительные затраты каталога составляют примерно 9х2 от 16 Мбайт или около 1,76%, что вполне допустимо. Даже если длина кэш-памяти составляет 32 байта, непроизводительные затраты составят вс Если длина строки кэш-памяти равна 128 байтов, непроизводительные з

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

6

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

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

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

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

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

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

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

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

Межкластерный интерфейс	Межкластерная шина
Процессор	(без отслеживания
с кэш-памятью	изменений по адресам)
Память

Локальная шина				Кластер	Ка
(с отслеживанием
изменений по адресам)
			Кластер	Состояние
	Блок		0 1 2 3 4 5 6 7 8 9 И	Ь /
		Р		I
		3
Это каталог кластера13.		2 |2| | | | | | | [ | | | | | | | | -+\— Uncached, shared, mo
Этот бит показывает,		Г,
содержится ли блок 1
		0
в какой-нибудь кэш-памяти
кластера 0			g

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

Полный объем адресного пространства в данной системе равен 256 Адресное пространство разделено на 16 областей по 16 Мбайт каждая. Гло память кластера 0 включает адреса с 0 по 16 М. Глобальная память кластера

чает адреса с 16 М по 32 М и т. д. Размер строки кэш-памяти составляет 16