Файл: Tannenbaum.pdf

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

Последние 13 битов — это тег (нужен для идентификации строки). Напомним,

что самая большая система NUMA-Q2000 содержит 63х2

32

=2

38

 байтов ОЗУ, по-

этому имеется почти 2

32

 строк кэш-памяти. Все кэши прямого отображения, по-

этому 2

32

 строк отображаются на 2

19

 элементов кэш-памяти, существует 2

13

 строк,

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

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

Каждая строка имеет фиксированную позицию только в одном блоке памяти

(исходном). Эти строки могут находиться в одном из трех состояний: UNCACHED
(некэшированном), SHARED (совместного использования) и MODIFIED (изме-
ненном). В протоколе SCI эти состояния называются HOME, FRESH и GONE
соответственно, но мы во избежание путаницы будем использовать прежнюю тер-
минологию. Состояние UNCACHED означает, что строка не содержится ни в од-
ном из кэшей на плате IQ-Link, хотя она может находиться в локальной кэш-памя-

ти на той же самой плате quad board. Состояние SHARED означает, что строка
находится по крайней мере в одной кэш-памяти платы IQ-Link, а память содер-
жит обновленные данные. Состояние MODIFIED означает, что строка находится
в кэш-памяти на какой-то плате IQ-Link, но, возможно, эта строка была изменена,
поэтому память может содержать устаревшие данные.

Блоки кэш-памяти могут находиться в одном из 29 устойчивых состояний или

в одном из переходных состояний (их более 29). Для записи состояния каждой
строки необходимо 7 битов (рис. 8.27). Каждое устойчивое состояние показывает-
ся двумя полями. Первое поле указывает, где находится строка — в начале списка,
в конце, в середине или вообще является единственным элементом списка. Второе
поле содержит информацию о том, изменялась ли строка, находится ли она только
в этой кэш-памяти и т. п.

В протоколе SCI определены 3 операции со списком: добавление узла к списку,

удаление узла из списка и очистка всех узлов кроме одного. Последняя операция
нужна в том случае, если разделяемая строка изменена и становится единственной.

Протокол SCI имеет три варианта сложности. Протокол минимальной степе-

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

NUMA-Q используется протокол средней степени сложности, поэтому ниже мы
рассмотрим именно его.

Разберемся, как обрабатывается команда READ. Если процессор, выполняющий

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

Предположим, что состояние строки SHARED. Эта строка также берется из

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

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

Представим теперь, что требуемая строка находится в состоянии MODIFIED.

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

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

Обработка команды WRITE происходит немного по-другому. Если запрашиваю-

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

Мультипроцессоры СОМА

Машины NUMA и CC-NUMA имеют один большой недостаток: обращения к уда-

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

Мы видим, что машины UMA, например Sun Enterprise 10000, имеют очень

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

Машины NUMA могут расширяться до больших размеров, но в них требуется руч-
ное или полуавтоматическое размещение страниц, а оно не всегда проходит удачно.

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

CC-NUMA, например Sequent NUMA-Q, могут работать с очень низкой произво-

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

ных. Так или иначе, каждая из этих разработок имеет существенные недостатки.

Однако существует процессор, в котором все эти проблемы разрешаются за счет

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

 СОМА (Cache Only Memory Access).

 В ней страницы не

имеют собственных фиксированных машин, как в системах NUMA и CC-NUMA.

Вместо этого физическое адресное пространство делится на строки, которые

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

 attraction memory.

 Использование основной памяти в качестве большой

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

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

К сожалению, ничего идеального не бывает. В системе СОМА появляется две

новых проблемы:

1. Как размещаются строки кэш-памяти?

2. Если строка удаляется из памяти, что произойдет, если это последняя копия?
Первая проблема связана со следующим фактом. Если блок управления памя-

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

Было предложено несколько решений этой проблемы. Можно ввести новое

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

Другое решение — отображать страницы полностью, но при этом не требовать

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

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

Таким образом, система будет искать только те строки, которые действительно

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

Вторая проблема связана с удалением последней копии. Как и в машине СС-

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

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

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

ли другие копии. Если да, то строку можно смело выбрасывать. Если нет, то ее
нужно переместить куда-либо еще. Другое решение — пометить одну из копий каж-
дой строки кэш-памяти как главную копию и никогда ее не выбрасывать. При таком
подходе не требуется проверка каталога. Машина СОМА обещает обеспечить луч-
шую производительность, чем CC-NUMA, но дело в том, что было построено очень
мало машин СОМА, и нужно больше опыта. До настоящего момента создано всего
две машины СОМА: KSR-1 [20] и Data Diffusion Machine [53]. Дополнительную
информацию о машинах СОМА можно найти в книгах [36, 67,98, 123].

Мультикомпьютеры с передачей сообщений  6 2 1

Мультикомпьютеры с передачей сообщений

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

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

Однако мультипроцессоры имеют и некоторые недостатки, поэтому мульти-

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

до больших размеров. Чтобы расширить машину Interprise 10000 до 64 процессо-
ров, пришлось добавить огромное количество аппаратного обеспечения.

В Sequent NUMA-Q дошли до 256 процессоров, но ценой неодинакового

времени доступа к памяти. Ниже мы рассмотрим два мультикомпьютера, которые
содержат 2048 и 9152 процессора соответственно. Через много лет кто-нибудь скон-
струирует мультипроцессор, содержащий 9000 узлов, но к тому времени мульти-

компьютеры будут содержать уже 100 000 узлов.

Кроме того, конфликтная ситуация при обращении к памяти в мультипроцес-

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

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

рес к параллельным компьютерам, в которых каждый процессор имеет свою соб-
ственную память, к которой другие процессоры не могут получить прямой доступ.
Это мультикомпьютеры. Программы на разных процессорах в мультикомпьютере
взаимодействуют друг с другом с помощью примитивов send и receive, которые
используются для передачи сообщений (поскольку они не могут получить доступ
к памяти других процессоров с помощью команд LOAD и STORE). Это различие полно-
стью меняет модель программирования.

Каждый узел в мультикомпьютере состоит из одного или нескольких процес-

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

(см. раздел «Сети межсоединений»). Используется множество различных тополо-
гий, схем коммутации и алгоритмов выбора маршрута. Все мультикомпьютеры
сходны в одном: когда программа выполняет примитив send, процессор передачи

данных получает уведомление и передает блок данных в целевую машину (воз-

можно, после предварительного запроса и получения разрешения). Схема мульти-
компьютера показана на рис. 8.28.

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

Процессор

Память

Узел

Р

Локальная

коммуникация

Процессор

передачи данных

Диск

—| и устройства

ввода-вывода

Р-РР

Локальная

коммуникация

Диск

—| и устройства

ввода-вывода

Высокоскоростная коммуникационная сеть

Рис. 8.28. Схема мультикомпьютера

Мультикомпьютеры бывают разных типов и размеров, поэтому очень трудно

привести хорошую классификацию. Тем не менее можно назвать два общих типа:
МРР и COW. Ниже мы рассмотрим каждый из этих типов.

МРР — процессоры с массовым параллелизмом

МРР (Massively Parallel Processors — процессоры с массовым параллелизмом) —
это огромные суперкомпьютеры стоимостью несколько миллионов долларов. Они
используются в различных науках и промышленности для выполнения сложных

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

В большинстве таких машин используются стандартные процессоры. Это мо-

гут быть процессоры Intel Pentium, Sun UltraSPARC, IBM RS/6000 и DEC Alpha.
Отличает мультикомпьютеры то, что в них используется сеть, по которой можно
передавать сообщения, с низким временем ожидания и высокой пропускной спо-
собностью. Обе характеристики очень важны, поскольку большинство сообщений
малы по размеру (менее 256 байтов), но при этом суммарная нагрузка в большей
степени зависит от длинных сообщений (более 8 Кбайт).

Еще одна характеристика МРР — огромная производительность процесса вво-

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

Следующая специфическая черта МРР — отказоустойчивость. При наличии не

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

Было бы неплохо теперь рассмотреть основные принципы разработки МРР,

но, по правде говоря, их не так много. МРР представляет собой набор более или