Файл: Tannenbaum.pdf

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

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

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

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

Существуют и другие системы, но эти две наиболее распространенные.

PVM — виртуальная машина параллельного действия

PVM (Parallel Virtual Machine — виртуальная машина параллельного действия)

 —

это система с передачей сообщений, изначально разработанная для машин COW
с операционной системой UNIX [45, 142]. Позднее она стала применяться в дру-
гих машинах, в том числе в системах МРР. Это самодостаточная система с управ-
лением процессами и системой ввода-вывода.

PVM состоит из двух частей: библиотеки, вызываемой пользователем, и «сто-

рожевого» процесса, который работает постоянно на каждой машине в мульти-
компьютере. Когда PVM начинает работу, она определяет, какие машины должны
быть частью ее виртуального мультикомпьютера. Для этого она читает конфигу-
рационный файл. «Сторожевой» процесс запускается на каждой из этих машин.
Машины можно добавлять и убирать, вводя команды на консоли PVM.

Можно запустить п параллельных процессов с помощью команды

spawn -count n prog

Каждый процесс запустит

 prog.

 PVM решает, куда поместить процессы, но

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

 Pvm_spawn.

 Процессы могут быть организованы в группы, причем состав

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

Взаимодействие в машине PVM осуществляется с помощью примитивов для

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

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

цедуру

 pvm_send,

 которая представляет собой блокирующий сигнал send. Полу-

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

pvm_recv,

 которая блокирует получателя до тех пор, пока не придет подходящее

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

лучатель может вызвать процедуру

 pvmjtrecv,

 которая блокирует получателя на

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

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

 pvmjirecv,

 которая сразу же воз-

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

Помимо всех этих примитивов PVM поддерживает широковещание (процеду-

ра

pvm_bcast)

 и мультивещание (процедура

pvm_mcasi).

 Первая процедура отправ-

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

Синхронизация между процессами осуществляется с помощью процедуры

pvmjbarrier.

 Когда процесс вызывает эту процедуру, он блокируется до тех пор,

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

личии в большинстве компьютеров параллельного действия, что и объясняет его

популярность.

MPI — интерфейс с передачей сообщений

Следующий пакет для программирования мультикомпьютеров —

 MPI (Message-

Passing Interface — интерфейс с передачей сообщений).

 MPI гораздо сложнее,

чем PVM. Он содержит намного больше библиотечных вызовов и намного больше
параметров на каждый вызов. Первая версия MPI, которая сейчас называется MPI-1,
была дополнена второй версией, MPI-2, в 1997 году. Ниже мы в двух словах рас-
скажем о MPI-1, а затем посмотрим, что нового появилось в MPI-2. Более по-
дробную информацию об MPI см. в книгах [52, 134].

MPI-1, в отличие от PVM, никак не связана с созданием процессов и управлени-

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

В основе MPI лежат 4 понятия: коммуникаторы, типы передаваемых данных,

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

Сообщения могут быть разных типов: символьные, целочисленные (short, regular

и long integers), с обычной и удвоенной точностью, с плавающей точкой и т. д.
Можно образовать новые типы сообщений из уже существующих.

MPI поддерживает множество операций коммуникации. Ниже приведена опе-

рация, которая используется для отправки сообщений:

MPI_Send(buffer. count. data_type. destination, tag. communicator)

Этот вызов отправляет содержимое буфера

 (buffer)

 с элементами определен-

ного типа

 (datatype)

 в пункт назначения.

 Count —

 это число элементов буфера.

Поле

 tag

 помечает сообщение; получатель может сказать, что он будет принимать

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

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

 destination —

 это просто индекс спис-

ка процессов из определенной группы). Соответствующий вызов для получения
сообщения таков:

MPI_Recv(&buffer, count, datajtype, source, tag. communicator, Sstatus)

В нем сообщается, что получатель ищет сообщение определенного типа из

определенного источника с определенным тегом.

MPI поддерживает 4 основных типа коммуникации. Первый тип синхронный.

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

зависит от реализации и может быть либо синхронным, либо с буфером. Четвер-
тый тип сходен с первым. Здесь отправитель требует, чтобы получатель был до-
ступен, но без проверки. Каждый из этих примитивов бывает двух видов: блокиру-
ющим и неблокирующим, что в сумме дает 8 примитивов. Получение может быть
только в двух вариантах: блокирующим и неблокирующим.

MPI поддерживает коллективную коммуникацию — широковещание, распре-

деление и сбор данных, обмен данными, агрегацию и барьер. При любых формах

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

Четвертое основное понятие в MPI —

 виртуальная топология,

 когда процессы

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

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

В MPI-2 были добавлены динамические процессы, доступ к удаленной памяти,

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

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

на прикладном уровне

Из наших примеров видно, что мультикомпьютеры можно расширить до гораздо
больших размеров, чем мультипроцессоры. Sun Enterprise 10000, где максимальное
число процессоров — 64, и NUMA-Q, где максимальное число процессоров — 256,

являются представителями больших мультипроцессоров UMA и NUMA соответ-
ственно. А машины ТЗЕ и Option Red содержат 2048 и 9416 процессоров соответ-

ственно.

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

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

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

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

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

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

Один из классов систем с общей памятью на прикладном уровне — это системы со

страничной организацией памяти. Такая система называется

 DSM (Distributed

Shared Memory — распределенная совместно используемая память).

 Идея проста:

ряд процессоров в мультикомпьютере разделяет общее виртуальное адресное про-
странство со страничной организацией. Самый простой вариант — когда каждая
страница содержится в ОЗУ ровно для одного процессора. На рис. 8.34,

 а

 мы видим

общее виртуальное адресное пространство, которое состоит из 16 страниц и рас-
пространяется на 4 процессора.

Когда процессор обращается к странице в своем локальном ОЗУ, чтение и за-

пись происходят без задержки. Однако если процессор обращается к странице из

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

 б

 мы видим ситуацию

после того, как процессор 0 получил ошибку из-за отсутствия страницы 10, которая
была передана из процессора 1 в процессор 0.

Впервые идея была реализована в машине IVY [83, 84]. В результате в муль-

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

 в

 показана ситуация, когда два процессора

делят общую страницу, предназначенную только для чтения (это страница 10).

Но даже при такой оптимизации трудно достичь высокой производительности,

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

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

637

ницы, страница постоянно должна передаваться туда и обратно. Эта ситуация на-

зывается

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

Глобальная виртуальная память совместного использования, состоящая из 16 страниц

- Память

Сеть

0

9

2

10

5

Процессор 0

1

8

3 6

Процессор 1

4

12

| 7 | 11

Процессор 2

рГаГ] 15

Процессор 3

Рис. 8.34. Виртуальное адресное пространство, состоящее из 16 страниц, которые

распределены между четырьмя узлами в мультикомпьютере: исходное положение (а);

положение после обращения процессора 0 к странице 10 (б); положение после

обращения процессора 0 к странице 10 (в); в данном случае эта страница

предназначена только для чтения

Проблему ложного совместного использования можно разрешить по-разному.

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