14

Лекция 5

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

Все компьютеры в распределенной системе связаны между собой коммуникационной сетью. Коммуникационные сети подразделяются на широкомасштабные (Wide Area Networks, WANs) и локальные (Local Area Networks, LANs).

Широкомасштабные сети

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

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

Коммутация пакетов или коммутация линий.

Коммутация линий (телефонные разговоры) требует резервирования линий на время всего сеанса общения двух устройств.

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

Семиуровневая модель ISO

ISO OSI (International Standards Organizations»s Reference Model of Open Systems Interconnection) организует коммуникационные протоколы в виде семи уровней и специфицирует функции каждого уровня.

Локальные сети.

Особенности LAN:

• географическая область охвата невелика (здание или несколько зданий);

• высокая скорость передачи (10-100 Mbps);

• малая вероятность ошибок передачи.

Свойственные многоуровневой модели ISO OSI накладные расходы являются причиной того, что в LAN применяются более простые протоколы.

Клиент-сервер

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

Удаленный вызов процедур

Send, receive - подход ввода/вывода

Более естественный подход, применяемый в централизованных ЭВМ - вызов процедур.

Birrell and Nelson (1984) (независимо и раньше - Илюшин А.И.,1978) предложили позволить вызывающей программе находиться на другой ЭВМ.

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

Время передачи сообщения между двумя узлами транспьютерной матрицы (характеристики аппаратуры - время старта передачи Ts, время передачи одного байта информации соседнему узлу Tb, процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми). За время Ts+ Tb транспьютер может передать 1 байт информации своим четырем соседям и принять от них 4 байта информации (по одному байту от каждого).

Конвейеризация и параллельное использование нескольких маршрутов.

3.1 Обмен сообщениями между прикладными процессами

SEND, RECEIVE (адресат/отправитель, [тэг,] адрес памяти, длина)

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

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

Блокирующие операции send (до освобождения памяти с данными или до завершения фактической передачи) и неблокирующие.

Буферизуемые и небуферизуемые (rendezvous или с потерей информации при отсутствии receive).

Надежные и ненадежные.

MPI - Message-Passing Interface [4]

(Message Passing Interface Forum, May 5, 1994

http://www.mpi-forum.org)

(1) Цели:

• Создать интерфейс прикладного программирования (не только для компиляторов или библиотек реализации систем);

• Обеспечить возможность эффективных коммуникаций (избежать копирования из памяти в память, позволить совмещение вычислений и коммуникаций или разгрузку на коммуникационный процессор там, где он есть);

• Разрешить расширения для использования в гетерогенной среде;

• Исходить из надежности коммуникаций (пользователь не должен бороться с коммуникационными сбоями - это дело коммуникационных подсистем нижнего уровня);

• Определить интерфейс, который бы не слишком отличался от используемых в настоящее время, таких как PVM, Express, P4, и пр.;

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

**************************************************************

(2) Что включено в MPI ?

• Коммуникации точка-точка;

• Коллективные операции;

• Группы процессов;

• Коммуникационные контексты;

• Простой способ создания процессов для модели SPMD (одна программа используется для обработки разных данных на разных процессорах);

• Топология процессов.

**************************************************************

(3) Что не включено в MPI ?

• Явные операции с разделяемой памятью и явная поддержка нитей (процессов с общей памятью);

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

• Вспомогательные функции, такие как таймеры.

**************************************************************

(4) Некоторые понятия.

Коммуникационные операции могут быть:

неблокирущие - если возврат осуществляется до завершения операции;

блокируюшие - если возврат означает, что пользователь может использовать ресурсы (например, буфера), указанные в вызове;

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

(5) Группы, контексты, коммуникаторы.

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

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

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

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

Имеются предопределенные коммуникаторы (точнее, создаваемые при инициализации MPI-системы):

• MPI_COMM_ALL - все процессы

• MPI_COMM_PEER - все, кроме главного процесса.

**************************************************************

(6) Операции над группами (локальные, без обмена сообщениями).

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

Для поддержки связывания с серверами, имеются средства построения коммуникатора по некоторому имени, известному и серверу и клиентам.

(7) Точечные коммуникации.

Основные операции - send, receive

Операции могут быть блокирующими и неблокирующими.

В операции send задается:

• адрес буфера в памяти;

• количество посылаемых элементов;

• тип данных каждого элемента;

• номер процесса-адресата в его группе;

• тег сообщения;

• коммуникатор.

(последние 3 параметра - аналоги «почтового конверта»)

В операции receive задается:

• адрес буфера в памяти;

• количество посылаемых элементов;

• тип данных каждого элемента;

• номер процесса-адресата в его группе (либо «любой»);

• тег сообщения (либо «любой»);

• коммуникатор;

• статус (источник и тег, необходимые в том случае, когда они неизвестны - при их задании с помощью шаблона «любой»).

Предусмотрена конвертация данных при работе в гетерогенной среде.

Имеется четыре режима коммуникаций - стандартный, буферизуемый, синхронный и режим готовности.

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

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

В синхронном режиме последовательность выдачи операций произвольна, но операция send завершается только после выдачи и начала выполнения операции receive. Операция нелокальная.

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

Во всех четырех режимах операция receive завершается после получения сообщения в заданный пользователем буфер приема.

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

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

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

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

(8) Коллективные коммуникации.

Для обеспечения коллективных коммуникаций введены следующие функции:

• барьер для всех членов группы (BARRIER);

• передача сообщения всем членам группы от одного (BROADCAST);

• сбор данных от всех членов группы для одного (GATHER);

• рассылка данных всем членам группы от одного (SCATTER);

• сбор данных от всех членов группы для всех (ALLGATHER);

• рассылка данных всем членам группы от всех (ALLTOALL);

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

Схема перемещения данных между 4 процессами

Данные

Pr-0

A0

A0

Pr-1

BROADCAST

A0

Pr-2



A0

Pr-3

A0

Pr-0	A0	A1	A2	A3	SCATTER	A0
Pr-1						A1
Pr-2					GATHER	A2
Pr-3						A3

Pr-0

A0

B0

C0

D0

A0

Pr-1

A0

B0

C0

D0

ALLGATHER

B0

Pr-2

A0

B0

C0

D0



C0

Pr-3

A0

B0

C0

D0

D0