Файл: Tannenbaum.pdf

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

параллельно. Здесь существует несколько вариантов. Некоторые компьютеры па-
раллельного действия одновременно выполняют несколько независимых задач. Эти
задачи никак не связаны друг с другом и не взаимодействуют. Типичный пример —
компьютер, содержащий от 8 до 64 процессоров, представляющий собой большую
систему UNIX с разделением времени, с которой могут работать тысячи пользова-
телей. В эту категорию попадают системы обработки транзакций, которые ис-
пользуются в банках (например, банковские автоматы), на авиалиниях (напри-
мер, системы резервирования) и в больших web-серверах. Сюда же относятся
независимые прогоны моделирующих программ, при которых используется не-
сколько наборов параметров.

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

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

Далее идут машины с высокой степенью конвейеризации или с большим коли-

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

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

 степени детализации.

 В мно-

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

 параллелизмом на уровне крупных

 структурных единиц. Диамет-

рально противоположный случай (при обработке векторных данных) называется

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

Термин «степень детализации» применяется по отношению к алгоритмам и про-

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

 системами с косвен-

ной (слабой) связью.

 Им противопоставляются

 системы с непосредственной (тес-

ной) связью,

 в которых компоненты обычно меньше по размеру, расположены

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

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

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

559

В следующих разделах мы рассмотрим некоторые вопросы разработки компью-

теров параллельного действия. Мы начнем с информационных моделей и сетей
межсоединений, затем рассмотрим вопросы, связанные с производительностью и

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

Информационные модели

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

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

В первой разработке все процессоры разделяют общую физическую память, как

показано на рис. 8.1, а. Такая система называется

 мультипроцессором

 или

 систе-

мой с совместно используемой памятью.

Мультипроцессорная модель распространяется на программное обеспечение.

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

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

р

р

р

р

• Процессор

I I I

 ~

р

р

р

р

Память

совместного

использования

1

р

1

р

1

р

1

р

Рис.  8 . 1 . Мультипроцессор, содержащий 16 процессоров, которые разделяют общую

память (а); изображение, разбитое на 16 секций, каждую из которых анализирует

отдельный процессор (б)

Благодаря такой возможности взаимодействия двух и более процессов муль-

типроцессоры весьма популярны. Данная модель понятна программистам и при-
ложима к широкому кругу задач. Рассмотрим программу, которая изучает битовое
отображение и составляет список всех его объектов. Одна копия отображения хра-
нится в памяти, как показано на рис. 8.1, б. Каждый из 16 процессоров запускает

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

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

В качестве примеров мультипроцессоров можно назвать Sun Enterprise 10000,

Sequent NUMA-Q, SGI Origin 2000 и HP/Convex Exemplar.

Мультикомпьютеры

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

ную память, доступную только этому процессору. Такая разработка называется

мультикомпьютером

 или

 системой с распределенной памятью.

 Она изображена

на рис. 8.2,

 а.

 Мультикомпьютеры обычно (хотя не всегда) являются системами со

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

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

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

с другом просто путем чтения из общей памяти и записи в общую память, здесь
необходим другой механизм взаимодействия. Они посылают друг другу сообще-
ния, используя сеть межсоединений. В качестве примеров мультикомпьютеров
можно назвать IBM SP/2, Intel/Sandia Option Red и Wisconsin COW.

M

1

p

M

1

p

M

1

p

M

1

p

Собственная память

Процессор

M

М

М

м -

р -

I

 \

•ей*

1

Р

1

Р

1

Р

1

Р

«-Процессор

Сеть

с передачей

сообщений

1

р

1

м

1

р

1

м

1

р

1

м

1

р

1

м

-

-

р

р

р

р

-

-

-

-

м

м

м

м

- р -

{•

~ I I ~

Сеть

с передачей

сообщений

1

р

1

%

1

р

1

т

1

р

1

Ш

i

р

i

а

р

р

р

р

-

-

«

Рис. 8.2. Мультикомпьютер, содержащий 16 процессоров, каждый из которых имеет

свою собственную память (а); битовое отображение рис. 8.1, разделенное

между 16 участками памяти (б)

Вопросы разработки компьютеров параллельного действия 561

При отсутствии памяти совместного использования в аппаратном обеспечении

предполагается определенная структура программного обеспечения. В мультиком-
пьютере невозможно иметь одно виртуальное адресное пространство, из которого
все процессы могут считывать информацию и в которое все процессы могут запи-
сывать информацию просто путем выполнения команд LOAD и STORE. Например, если
процессор 0 (в верхнем левом углу) на рис. 8.1, ^обнаруживает, что часть его объекта
попадает в другую секцию, относящуюся к процессору 1, он может продолжать
считывать информацию из памяти, чтобы получить хвост самолета. Однако если
процессор 0 на рис. 8.2, # обнаруживает это, он не может просто считать инфор-

мацию из памяти процессора 1. Для получения необходимых данных ему нужно
сделать что-то другое.

В частности, ему нужно как-то определить, какой процессор содержит необходи-

мые ему данные, и послать этому процессору сообщение с запросом копии данных.
Затем процессор 0 блокируется до получения ответа. Когда процессор 1 получает
сообщение, программное обеспечение должно проанализировать его и отправить
назад необходимые данные. Когда процессор 0 получает ответное сообщение, про-
граммное обеспечение разблокируется и продолжает работу.

В мультикомпьютере для взаимодействия между процессорами часто исполь-

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

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

Возникает вопрос: зачем вообще создавать мультикомпыотеры, если мульти-

процессоры гораздо проще запрограммировать? Ответ прост: гораздо проще и де-
шевле построить большой мультикомпьютер, чем мультипроцессор с таким же
количеством процессоров. Реализация общей памяти, разделяемой несколькими
сотнями процессоров, — это весьма сложная задача, а построить мультикомпью-
тер, содержащий 10 000 процессоров и более, довольно легко.

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

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

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

вых и новых процессоров.

Один из подходов основан на том, что современные компьютерные системы не

монолитны, а состоят из ряда уровней. Это дает возможность реализовать общую

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

память на любом из нескольких уровней, как показано на рис. 8.3. На рис. 8.3,

 а

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

Второй подход — использовать аппаратное обеспечение мультикомпьютера и

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

 DSM (Distributed Shared Memory — распределенная

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

 [82,83, 84], каждая страница расположена в од-

ном из блоков памяти (см. рис. 8.2, с). Каждая машина содержит свою собствен-
ную виртуальную память и собственные таблицы страниц. Если процессор со-
вершает команду LOAD или STORE над страницей, которой у него нет, происходит
прерывание операционной системы. Затем операционная система находит нуж-
ную страницу и требует, чтобы процессор, который обладает нужной страницей,
преобразовал ее в исходную форму и послал по сети межсоединений. Когда стра-
ница достигает пункта назначения, она отображается в память, и выполнение пре-

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

Третий подход — реализовать общую разделенную память на уровне программ-

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

Другой пример памяти совместного использования, реализованной в программ-

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