24. Статический и динамический способы образования параллельных процессов.

"Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам. Эти правила описываются программой, которую ин­терпретирует процессор." /Цикритзис Д./.

Вычислительный процесс можно рассматривать как последовательность команд ЭВМ, которая работает с данными ей ресурсами. (Задача, задание, процесс, нить, TASK). Так, на микропроцессоре могут работать одновременно несколько независимых процессов: счет вычислительной задачи, редактирование текстов и т.д. Далее рассматриваются вычислительные процессы, одновременно выполняющиеся на нескольких процессорах для решения общей задачи. Работа такой задачи может начинаться с порождения главного процесса, который при работе может порождать другие процессы динамически. Эти процессы могут работать параллельно с главной и также порождать другие процессы.

Другим способом порождения процессов является статический способ, когда производится одновременная инициализация на всех процессорах одинаковых процессов (SPMD – Single Program Multiple Data). Эти процессы опрашивают состояние решающего поля и настраиваются на выполнение своей части вычислений.(Они могут узнать: сколько их порождено, свои уникальные, внутренние имена, и т.д.)

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

25. Двоичные и общие семафоры

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

Участки программы процесса, в которых происходит обращение к кри­тическим ресурсам, называются критическими участками. Такие участки должны быть выполнены в режиме "взаимного исключения", т.е. в каждый момент времени не более чем один процесс может быть занят выполнением своего, критического относительно некоторого ресурса, участка. Пробле­ма критического участка - программирование работы критических участков в режиме взаимного исключения решается с помощью семафоров. Общий семафор - это целочисленная переменная, над которой разре­шены только две неделимые операции P и V. Аргументом у этих операций является семафор. Определять семантику этих операций можно только для семафоров - положительных чисел, или включать и отрицательный диапа­зон. Операции могут быть определены так:

P(S) - декремент и анализ семафора

S := S-1

IF (S < 0) THEN <блокировка текущего процесса>

ENDIF

V(S) - инкремент семафора

S := S+1

IF S <= 0 THEN <запустить блокированный процесс>

ENDIF

P и V операции неделимы: в каждый момент только один процесс может выполнять Р или V операцию над данным семафором.

Если семафор используется как счетчик ресурсов, то:

S >= 1 - есть некоторое количество (S) доступных ресурсов,

S = 0 - нет доступного ресурса,

S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.

Вводится, также, операция инициализации семафора (присвоение начального значения).

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

Семафоры позволяют:

- синхронизировать работу процессов,

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

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

В системах программирования вводится специальный тип данных, оп­ределяющий структуру семафора, например, SEMAPHOR,SIGNAL,GETA.

Использование семафоров

begin integer S; S:=1;

parbegin

task1: begin

do while (true)

P(S);

<критический участок 1>;

V(S);

<обычный участок>;

enddo

end;

task2: begin

do while (true)

P(S);

<критический участок 2>;

V(S);

<обычный участок>;

enddo

end

parend

end

26. Назначение системы МPI

Главные цели создания системы параллельного программирования:

Создать интерфейс прикладного программирования для МРР систем;

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

Допускать удобное сопряжение с языками C, Fortran 77, Fortran 90 и C++;

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

Основные понятия языка

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

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

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

Имеются предопределенные коммуникаторы (точнее, создавае­мые при инициализации MPI-системы): * MPI_COMM_ALL - все процессы и операции над группами (локальные, без обмена сообщениями), например, Дай размер группы. MPI_GROUP_SIZE(IN group, OUT size) Дай номер в группе обратившегося процесса. MPI_GROUP_RANK(IN group, OUT rank)

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

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

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

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

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

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

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

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

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

MPI_SEND(IN start, IN count, IN datatype, IN dest, IN tag, IN comm) Типы данных - свои в MPI, но имеется соответствие между ними и типами Fortran и С.

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

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

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

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

- номер процесса-отправителя в его группе;

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

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

- ссылка на объект-статус, содержащий необходимую инфор­мацию о состоянии и результате операции.

Имеется возможность указать "любой отправитель" и "любой тег".

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

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

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

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

27. Распараллеливание последовательных программ. ( Метод гиперплоскостей)

Метод гиперплоскостей применим только к многомерным циклам. В пространстве итераций ищется прямая (плоскость), на которой возможно параллельное асинхронное выполнение тела цикла, причем в отличие от метода координат, эта прямая (плоскость) может иметь наклон по отношению к осям координат. Цикл вида:

DO I = 2,N

DO J = 2,M

A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5

методом координат не векторизуется. Действительно, при фиксированном

значении переменной I (I = i) значение, вычисленное в точке (i,j)

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

точке (i,j-1), так что параллельное выполнение тела цикла по переменной J невозможно. Аналогично нельзя проводить параллельные вычисления по переменной I.

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

на 1-м шаге - в точке (2,2),

на 2-м шаге - в точках (3,2) и (2,3),

на 3-м шаге - в точках (4,2), (3,3) и (2,4),

на 4-м шаге - в точках (5,2), (4,3), (3,4) и (2,5) и т.д.

Вычисления в указанных точках для каждого шага, начиная со второго, можно проводить параллельно и асинхронно. Перечисленные кортежи точек лежат на параллельных прямых вида I+J=K, а именно: на первом ша­ге - на прямой I+J=4, на втором - I+J=5, на третьем шаге - I+J=6 и т.д., на последнем ((N-2)+(M-2)+1) - ом шаге - на прямой I+J=M+N.

Для приведенного примера множество точек, в которых возможно параллельное выполнение, является однопараметрическим (прямая) и определяется из решения уравнения I+J=K. Цикл (5) может быть преобразован к виду: DO 5 K = 4,M+N

Tн = MMAX(2,K-N)

Tк = MMIN(M,K-2)

DO 5 T = Tн,Tк : PAR

I = T

J = K - T

5 A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5

Функция MMAX(X,Y) выбирает ближайшее целое, большее или равное максимуму из чисел X и Y, а функция MMIN(X,Y) - ближайшее целое, меньшее или равное минимуму из X и Y.

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

28. Ограничения на распараллеливание циклов.

Распараллеливание циклов возможно, если все итерации цикла независимы. Тело цикла не должны содержать:

• операторов перехода

• операторов ввода-вывода

Индексные выражения не должны иметь индекс в индексе А(В(С))

29. Алгоритмы преобразования программ методом координат

Метод координат:

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

- содержит алгоритмы преобразования тела цикла к синхронному виду. Например, по Лэмпорту, цикл:

DO 24 I=2,M

DO 24 J=2,N

21 A(I,J) = B(I,J)+C(I)

22 C(I) = B(I-1,J)

23 B(I,J) = A(I+1,J) ** 2

24 CONTINUE

преобразуется в цикл:

DO 24 J=2,N

DO 24 SIM FOR ALL I i:2<=i<=M C SIM - SI Multeneusly (одновременно)

TEMP(I) = A(I+1,J)

1. A(I,J) = B(I,J)+C(I)

23 B(I,J) = TEMP(I) ** 2

1. C(I) = B(I-1,J)

24 CONTINUE

Примеры векторизации

Исходные тела циклов Преобразованные тела циклов

A(I) = B(I) C(I) = A(I+1)

C(I) = A(I+1) A(I) = B(I)

A(I) = B(I) D(I) = A(I)

C(I) = A(I) + A(I+1) A(I) = B(I)

C(I) = A(I) + D(I+1)

30. Синхронный и асинхронный способы передачи сообщений

В MPI имеется три режима коммуникаций - стандартный, режим готовности и синхронный.