В.А. Фисун - Параллельная обработка данных (2005) (1127758), страница 7
Текст из файла (страница 7)
Такие участки должны бытьвыполнены в режиме "взаимного исключения", т.е. в каждый момент времени не болеечем один процесс может быть занят выполнением своего, критического относительнонекоторого ресурса, участка. Проблема критического участка - программированиеработы критических участков в режиме взаимного исключения решается с помощьюсемафоров. Общий семафор - это целочисленная переменная, над которой разрешенытолько две неделимые операции P и V.
Аргументом у этих операций являетсясемафор. Определять семантику этих операций можно только для семафоров положительных чисел, или включать и отрицательный диапазон. Операции могутбыть определены так:24P(S) - декремент и анализ семафораS := S-1IF (S < 0) THEN <блокировка текущего процесса>ENDIFV(S) - инкремент семафораS := S+1IF S <= 0 THEN <запустить блокированный процесс>ENDIFP и V операции неделимы: в каждый момент только один процесс можетвыполнять Р или V операцию над данным семафором.Если семафор используется как счетчик ресурсов, то:S >= 1 - есть некоторое количество (S) доступных ресурсов,S = 0 - нет доступного ресурса,S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.Вводится, также, операция инициализации семафора (присвоение начальногозначения).Общий семафор - избыточный, т.к.
его можно реализовать через двоичныесемафоры, которые принимают только два значения 0,1.Семафоры позволяют:- синхронизировать работу процессов,- управлять распределением ресурсом (использованием положительногодиапазона значений семафора как счетчика ресурсов) ,- организовывать очередь блокированных процессов (отрицательные значениясемафора показывают число блокированных процессов).В системах программирования вводится специальный тип данных, определяющийструктуру семафора, например, SEMAPHOR,SIGNAL,GETA.Использование семафоровbegin integer S; S:=1;parbegintask1: begindo while (true)P(S);<критический участок 1>;V(S);<обычный участок>;enddoend;task2: begindo while (true)P(S);25<критический участок 2>;V(S);<обычный участок>;enddoendparendend26.
Назначение системы М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 задается:26- адрес буфера в памяти;- количество посылаемых элементов;- тип данных каждого элемента;- номер процесса-адресата в его группе;- тег сообщения;- коммуникатор.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.
Распараллеливание последовательных программ. ( Метод гиперплоскостей)Метод гиперплоскостей применим только к многомерным циклам. Впространстве итераций ищется прямая (плоскость), на которой возможнопараллельное асинхронное выполнение тела цикла, причем в отличие от метода27координат, эта прямая (плоскость) может иметь наклон по отношению к осямкоординат. Цикл вида:DO I = 2,NDO J = 2,MA(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+NTн = MMAX(2,K-N)Tк = MMIN(M,K-2)DO 5 T = Tн,Tк : PARI=TJ=K-T5 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. Ограничения на распараллеливание циклов.28Распараллеливание циклов возможно, если все итерации цикла независимы. Телоцикла не должны содержать:- операторов перехода- операторов ввода-выводаИндексные выражения не должны иметь индекс в индексе А(В(С))29. Алгоритмы преобразования программ методом координатМетод координат:- позволяет определить возможность выполнения цикла в синхронномрежиме(для архитектуры SIMD);- содержит алгоритмы преобразования тела цикла к синхронному виду.Например, по Лэмпорту, цикл:DO 24 I=2,MDO 24 J=2,N21 A(I,J) = B(I,J)+C(I)22 C(I) = B(I-1,J)23 B(I,J) = A(I+1,J) ** 224 CONTINUEпреобразуется в цикл:DO 24 J=2,NDO 24 SIM FOR ALL I i:2<=i<=M C SIM - SI Multeneusly(одновременно)TEMP(I) = A(I+1,J)21 A(I,J) = B(I,J)+C(I)23 B(I,J) = TEMP(I) ** 222 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)C(I) = A(I) + A(I+1)D(I) = A(I)A(I) = B(I)C(I) = A(I) + D(I+1)30.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
