5-6 лекция (MPI-Syncronization) (1162658), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Данные

Названия функций и параметры:

MPI_BARRIER(IN comm)

MPI_BCAST(IN/OUT buffer, IN cnt, IN type, IN root, IN comm)

MPI_GATHER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN root, IN comm)

MPI_SCATTER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN root, IN comm)

MPI_ALLGATHER(IN sendbuf, IN sendcnt, IN sendtype,

OUT recvbuf, IN recvcnt, IN recvtype, IN comm)

MPI_ALLTOALL(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN comm)

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

PVM (Parallel Virtual Machine).

Широко известная система PVM [5] была создана для объединения нескольких связанных сетью рабочих станций в единую виртуальную параллельную ЭВМ. Система представляет собой надстройку над операционной системой UNIX и используется в настоящее время на различных аппаратных платформах, включая и ЭВМ с массовым параллелизмом.

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

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

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

MPI-2 (1997 г.) http://www.mpi-forum.org

Развивает MPI в следующих направлениях:

• Динамическое создание и уничтожение процессов (важно для работы в сетях ЭВМ).

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

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

4 Синхронизация в распределенных системах

Обычно децентрализованные алгоритмы имеют следующие свойства:

(1) Относящаяся к делу информация распределена среди множества ЭВМ.

(2) Процессы принимают решение на основе только локальной информации.

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

(4) Не существует общих часов или другого источника точного глобального времени.

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

Последний пункт также очень важен - в распределенных системах достигнуть согласия относительно времени совсем непросто. Важность наличия единого времени можно оценить на примере программы make в ОС UNIX.

4.1 Синхронизация времени.

Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте.

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

Для синхронизации логических часов Lamport определил отношение «произошло до». Выражение a-->b читается как «a произошло до b» и означает, что все процессы согласны, что сначала произошло событие «a», а затем «b». Это отношение может в двух случаях быть очевидным:

(1) Если оба события произошли в одном процессе.

(2) Если событие «a» есть операция SEND в одном процессе, а событие «b» - прием этого сообщения другим процессом.

Отношение --> является транзитивным.

Если два события «x» и «y» случились в различных процессах, которые не обмениваются сообщениями, то отношения x-->y и y-->x являются неверными, а эти события называют одновременными.

Введем логическое время С таким образом, что если a-->b, то C(a) < C(b)

Алгоритм:

(1) Часы Ci увеличивают свое значение с каждым событием в процессе Pi:

Ci = Ci + d (d > 0, обычно равно 1)

(2) Если событие «a» есть посылка сообщения «m» процессом Pi, тогда в это сообщение вписывается временная метка tm=Ci(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом:

Cj = max(Cj,tm+d)

Поясним на примере, как осуществляется эта коррекция.

Логическое время без коррекции. Логическое время с коррекцией.

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

Однако логических часов недостаточно для многих применений (системы управления в реальном времени).

Физические часы.

Характеристики

Список файлов лекций