Файл: Tannenbaum.pdf

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

 583

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

Альтернативный подход — взаимодействие через передачу сообщений. В дан-

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

Существует множество вариантов передачи сообщений, но все они сводятся

к применению двух примитивов send и recei ve. Они обычно реализуются как сис-
темные вызовы. Более подробно этот процесс мы рассмотрим ниже в этой главе.

Следующий вопрос при передаче сообщений — количество получателей. Са-

мый простой случай — один отправитель и один получатель

 (двухточечная пере-

дача сообщений).

 Однако в некоторых случаях требуется отправить сообщение

всем процессам

 (широковещание)

 или определенному набору процессов

 (муль-

тивещание).

Отметим, что в мультипроцессоре передачу сообщений легко реализовать путем

простого копирования от отправителя к получателю. Таким образом, возможности
физической памяти совместного использования (мультипроцессор/мультикомпью-
тер) и логической памяти совместного использования (взаимодействие через об-
щие переменные/передача сообщений) никак не связаны между собой. Все четыре
комбинации имеют смысл и могут быть реализованы. Они приведены в табл. 8.1.

Таблица 8.1

. Комбинации совместного использования физической

и логической памяти

Физическая память Логическая память Примеры

(аппаратное (программное

обеспечение) обеспечение)

Мультипроцессор Разделяемые переменные Обработка изображения (см. рис. 8.1).
Мультипроцессор Передача сообщений Передача сообщений с использованием

буферов памяти

Мультикомпьютер Разделяемые переменные DSM, Linda, Orca и т. д. на SP/2 или сети

персонального компьютера

Мультикомпьютер Передача сообщений PVM или MPI на SP/2 или сети

персонального компьютера

Базисные элементы синхронизации

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

 взаимного исключения,

 чтобы несколько процессов не

могли использовать одни и те же данные одновременно.

5 8 4

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

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

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

Во многих параллельных программах существует и такой вид примитивов

(базисных элементов), которые блокируют все процессы до тех пор, пока опреде-
ленная фаза работы не завершится (см. рис. 8.11,

 б).

 Наиболее распространенным

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

Классификация компьютеров

параллельного действия

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

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

[39, 43, 148]. К сожалению, хорошей классификации компьютеров параллельного

действия до сих пор не существует. Чаще всего используется классификация Флин-

на (Flynn), но даже она является очень грубым приближением. Классификация
приведена в табл. 8.2.

Таблица 8.2.

 Классификация компьютеров параллельного действия,

разработанная Флинном

Потоки команд Потоки данных Названия Примеры

1 1 SISD Классическая машина фон Неймана
1 Много S1MD Векторный суперкомпьютер, массивно-

параллельный процессор

Много 1 MISD Не существует
Много Много MIMD Мультипроцессор, мультикомпьютер

В основе классификации лежат два понятия: потоки команд и потоки данных.

Поток команд соответствует счетчику команд. Система с п процессорами имеет
п счетчиков команд и, следовательно, п потоков команд.

Поток данных состоит из набора операндов. В примере с вычислением темпе-

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

Потоки команд и данных в какой-то степени независимы, поэтому существует

4 комбинации (см. табл. 8.2). SISD (Single Instruction stream Single Data stream —

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

5 8 5

один поток команд, один поток данных) — это классический последовательный
компьютер фон Неймана. Он содержит один поток команд и один поток данных и
может выполнять только одно действие одномоментно. Машины SIMD (Single
Instruction stream Multiple Data stream — один поток команд, несколько потоков

данных) содержат один блок управления, выдающий по одной команде, но при
этом есть несколько АЛ У, которые могут обрабатывать несколько наборов данных

одновременно. ILLIAC IV (см. рис. 2.6) — прототип машин SIMD. Существуют
и современные машины SIMD. Они применяются для научных вычислений.

Машины MISD (Multiple Instruction stream Single Data stream — несколько

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

Последняя категория — машины MIMD (Multiple Instruction stream Multiple

Data stream — несколько потоков команд, несколько потоков данных). Здесь не-

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

Мы расширили классификацию Флинна (схема на рис. 8.12). Машины SIMD

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

Архитектуры компьютеров

параллельного действия

SISD

SIMD

MISD

(Фон Нейман)

MIMD

Векторный

процессор

Массивно-

параллельный

процессор

UMA

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

СОМА

NUMA

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

/

МРР

\

COW

С шинной

организацией

С координатными

коммутаторами

CC-NUMA NC-NUMA

В виде

решетки

В виде

гиперкуба

Совместно используемая память Передача сообщений

Рис. 8.12.

 Классификация компьютеров параллельного действия

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

В нашей классификации категория MIMD распалась на мультипроцессоры

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

 UMA (Uniform Memory Access — архитектура с однородным досту-

пом к памяти), NUMA (NonUniform Memory Access — архитектура с неодно-
родным доступом к памяти)

 и

 СОМА (Cache Only Memory Access — архитек-

тура с доступом только к кэш-памяти).

 В машинах UM А каждый процессор имеет

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

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

Мультипроцессор NUMA, напротив, не обладает этим свойством. Обычно есть

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

Во вторую подкатегорию машин MIMD попадают мультикомпьютеры, кото-

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

 NORMA (NO Remote Memory Access — без доступа к от-

даленным модулям памяти).

Мультикомпьютеры можно разделить на две категории. Первая категория со-

держит процессоры

 МРР (Massively Parallel Processors — процессоры с массо-

вым параллелизмом)

 — дорогостоящие суперкомпьютеры, которые состоят из

большого количества процессоров, связанных высокоскоростной коммуникаци-
онной сетью. В качестве примеров можно назвать Cray T3E и IBM SP/2.

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

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

 NOW (Network of Workstations — сеть рабочих станций)

и

 COW (Cluster of Workstattions — кластер рабочих станций).

Компьютеры SIMD 587

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

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

Компьютеры SIMD

Компьютеры SIMD (Single Instruction Stream Multiple Data Stream — один поток
команд, несколько потоков данных) используются для решения научных и техни-

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

(vector processors). Рассмотрим каждый из этих типов по отдельности.

Массивно-параллельные процессоры

Идея массивно-параллельных процессоров была впервые предложена более 40 лет
назад [151]. Однако прошло еще около 10 лет, прежде чем такой процессор (ILLI АС IV)

был построен для NASA. С тех пор другие компании создали несколько коммер-
ческих массивно-параллельных процессоров, в том числе СМ-2 и Maspar MP-2,
но ни один из них не пользовался популярностью на компьютерном рынке.

В

 массивно-параллельном процессоре

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

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

Хотя все массивно-параллельные процессоры соответствуют этой общей моде-

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

вычайно простой до чрезвычайно сложной. Самые простые обрабатывающие эле-
менты — 1-битные АЛУ (как в СМ-2). В такой машине каждый АЛУ получает два

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

граммы (например, бит переноса). Результат операции — 1 бит данных и несколь-
ко флаговых битов. Чтобы совершить сложение двух целых 32-битных чисел, бло-
ку управления нужно транслировать команду 1-битного сложения 32 раза. Если
на одну команду затрачивается 600 не, то для сложения целых чисел потребуется

19,2 мке, то есть получается медленнее, чем в первоначальной IBM PC. Но при

наличии 65 536 обрабатывающих элементов можно получить более трех миллиар-

дов сложений в секунду при времени сложения 300 пикосекунд.

Обрабатывающим элементом может быть 8-битное АЛУ, 32-битное АЛУ или

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

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