3-4-MPI-Sync (В.А. Крюков, В.А. Бахтин - Распределенные системы)
Описание файла
Файл "3-4-MPI-Sync" внутри архива находится в папке "В.А. Крюков, В.А. Бахтин - Распределенные системы". Документ из архива "В.А. Крюков, В.А. Бахтин - Распределенные системы", который расположен в категории "". Всё это находится в предмете "распределённые системы" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "3-4-MPI-Sync"
Текст из документа "3-4-MPI-Sync"
15
Лекция 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:
-
географическая область охвата невелика (здание или несколько зданий);
-
высокая скорость передачи (100-1000 Mbps);
-
малая вероятность ошибок передачи.
Свойственные многоуровневой модели ISO OSI накладные расходы являются причиной того, что в LAN применяются более простые протоколы.
Клиент-сервер
Можно избежать подтверждения получения сервером сообщения-запроса от клиента, если ответ сервера должен последовать скоро.
Удаленный вызов процедур
Send, receive - подход ввода/вывода
Более естественный подход, применяемый в централизованных ЭВМ - вызов процедур.
Birrell and Nelson (1984) (независимо и раньше - Илюшин А.И.,1978) предложили позволить вызывающей программе находиться на другой ЭВМ.
MPP с распределенной памятью может рассматриваться как частный случай локальной сети.
В середине 80-х годов английская фирма Inmos выпустила миникомпьютер, названный транспьютером. Его отличительной особенностью является наличие 8-ми каналов (4 входные и 4 выходные) для обмена информацией с другими транспьютерами или другими устройствами, такими как диски, терминалы и т.п.
Решетка транспьютеров, в которой каждый транспьютер параллельно с вычислениями может обмениваться одновременно по 8 каналам с 4 соседями, является хорошим примером, для которого будут формулироваться различные экзаменационные задачи.
Для передачи информации между двумя соседними (связанными одним каналом) узлами транспьютерной матрицы первый узел должен выдать операцию послать сообщение, а второй – операцию принять сообщение. При этом заданная в операции приема область памяти должна быть по размеру не меньше передаваемого сообщения. Операции посылки и приема сообщения завершаются только после полного завершения передачи сообщения.
Время передачи сообщения между двумя соседними узлами транспьютерной матрицы определяется двумя характеристиками аппаратуры - временем старта передачи Ts и временем передачи одного байта информации соседнему узлу Tb. При этом процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. За время Ts+Tb транспьютер может передать 1 байт информации своим четырем соседям и принять от них 4 байта информации (по одному байту от каждого). Для этого необходимо запустить на нем 8 служебных процессов.
Конвейеризация (разбиение сообщения на кванты, чтобы воспользоваться параллельной работой каналов вдоль маршрута передачи) и параллельное использование нескольких маршрутов – два метода ускорения передачи сообщений.
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_WORD - все процессы
-
MPI_COMM_SELF - один текущий процесс
**************************************************************
(6) Операции над группами (локальные, без обмена сообщениями).
Для поддержки пользовательских серверов имеется коллективная операция разбиения группы на подгруппы по ключам, которые указывает каждый процесс группы.
Для поддержки связывания с серверами, имеются средства построения коммуникатора по некоторому имени, известному и серверу и клиентам.
(7) Точечные коммуникации.
Основные операции - send, receive
Операции могут быть блокирующими и неблокирующими.
В операции send задается:
-
адрес буфера в памяти;
-
количество посылаемых элементов;
-
тип данных каждого элемента;
-
номер процесса-адресата в его группе;
-
тег сообщения;
-
коммуникатор.
(последние 3 параметра - аналоги «почтового конверта»)
В операции receive задается:
-
адрес буфера в памяти;
-
количество принимаемых элементов;
-
тип данных каждого элемента;
-
номер процесса-отправителяаботае в поиграть параметрами) идет в ку можно запускать отдельными шагамит не хватать памяти - можно попробовать ско в его группе (либо «любой»);
-
тег сообщения (либо «любой»);
-
коммуникатор;
-
статус (источник и тег, необходимые в том случае, когда они неизвестны - при их задании с помощью шаблона «любой»).
Предусмотрена конвертация данных при работе в гетерогенной среде.
Имеется четыре режима коммуникаций - стандартный, буферизуемый, синхронный и режим готовности.
В стандартном режиме последовательность выдачи операций send и receive произвольна, операция send завершается тогда, когда сообщение изъято из памяти процесса (например, переписано в системный буфер) и эта память уже может использоваться процессом. При этом выполнение операции может осуществляться независимо от наличия receive, либо требовать наличие (вопрос реализации MPI). Поэтому операция считается нелокальной.
В буферизуемом режиме последовательность выдачи операций send и receive произвольна, операция send завершается тогда, когда сообщение изъято из памяти и помещено в буфер, предварительно заведенный в памяти процесса. Если места в буфере нет - ошибка программы (но есть возможность определить свой буфер). Операция локальная.
В синхронном режиме последовательность выдачи операций произвольна, но операция send завершается только после выдачи и начала выполнения операции receive. Для этого посылающая сторона запрашивает у принимающей стороны подтверждение выдачи операции 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 |