СКИПОДы конспект лекций (1127769), страница 14

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

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

Проблема критического участка программирование работы критических участков в режиме взаимного исключения решается с помощьюсемафоров. Общий семафор - это целочисленная переменная, над которой разрешены только двенеделимые операции P и V. Аргументом у этих операций является семафор. Определять семантику этихопераций можно только для семафоров - положительных чисел, или включать и отрицательный диапазон.Операции могут быть определены так:P(S) - декремент и анализ семафораS := S-1IF (S < 0) THEN <блокировка текущего процесса>ENDIFV(S) - инкремент семафораS := S+1IF S <= 0 THEN <запустить блокированный процесс>ENDIFP и V операции неделимы: в каждый момент только один процесс может выполнять Р или Vоперацию над данным семафором.Если семафор используется как счетчик ресурсов, то:S >= 1 - есть некоторое количество (S) доступных ресурсов,S = 0 - нет доступного ресурса,31S < 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);<критический участок 2>;V(S);<обычный участок>;enddoendparendend54.

Упорядоченные секции. Распараллелить цикл, используя упорядоченные секции исемафоры:DO I=2,NA(I) = 2*A(I) + C(I)B(I) = C(I)*sin(X(I))Y(I) = Y(I-1) + X(I)D(I) = P(I)*B(I)/A(I)ENDDOИногда, почти полностью распараллеливающийся по данным, алгоритм имеет единственную зависимостьданных, которая на векторных машинах может потребовать расщепления цикла, чтобы изолироватьзависимость.Например:DO I = 1,NA(I) = EXP(SIN(B(I))) * EXP(COS(B(I)))C(I) = (D(I) + E(I)) / F(I) * A(I)X(I) = S * X(I-1) + C(I)Z(I) = X(I) * Y(I) + EXP(Z(I))ENDDOОператор присваивания X(I) включает рекурсию, что запрещает векторизацию. Обычно либо компилятор,либо программист выделит этот оператор в отдельный скалярный цикл, чтобы позволить другим тремоператорам присваивания выполняться в параллельном режиме.Это не всегда необходимо делать при распараллеливании.

Если имеется достаточно работы выше и/илиниже оператора присваивания X(I) и N достаточно велико, можно достичь эффективного параллельного32выполнения цикла путем помещения оператора присваивания X(I) в упорядоченную критическую секцию.Она будет обеспечивать доступ только одной нити в один и тот же момент явным или неявнымзамковым (lock) механизмом. В данном случае требуется выполнять итерации в таком порядке, чтобыудовлетворить требования рекурсии для вычисления X.Реальная система синхронизации для SEQCALL SETSEQ (SEQ,0)* инициализация, установка SEQ=0С$DIR DO_PARALLEL (ORDRED)DO I = 1,NA(I) = EXP(SIN(B(I))) * EXP(COS(B(I)))C(I) = (D(I) + E(I)) / F(I) * A(I)CALL WAITSEQ (SEQ,I-1)* ждать, пока SEQ будет равно I-1X(I) = S * X(I-1) + C(I)CALL POSTSEQ (SEQ,I)* установить SEQ в IZ(I) = X(I) * Y(I) + EXP(Z(I))ENDDOСемантика (для случая четырех процессоров): Инициализируются вычисления первых четырех итераций в заданном порядке на четырехпараллельных процессорах. Все четыре процессора вычисляют свои A(I),C(I) одновременно. Первый процессор выполнит для I=1 присваивание X(1), в то время как другие ждут. Первый процессор для I=1 вычисляет Z(1), в то время как X(2) вычисляется вторым процессоромдля I=2. Первый процессор начинает вычислять новую итерацию для I=5, в то время как другие трипроцессора проходят сквозь критическую секцию также упорядочено.Теперь, если работа по выполнению цикла хорошо сбалансирована, первый процессор для I=5достигает точки WAITSEQ как раз тогда, когда четвертый процессор для I=4 закончит POSTSEQ.

С этойточки все процессоры работают без простоя, пока они не достигнут последние четыре итерации цикла.55. Статический и динамический способы образования параллельных процессов."Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам. Этиправила описываются программой, которую интерпретирует процессор." /Цикритзис Д./.Вычислительный процесс можно рассматривать как последовательность команд ЭВМ, котораяработает с данными ей ресурсами. (Задача, задание, процесс, нить, TASK).

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

Эти процессымогут работать параллельно с главной и также порождать другие процессы.Другим способом порождения процессов является статический способ, когда производитсяодновременная инициализация на всех процессорах одинаковых процессов (SPMD – Single ProgramMultiple Data). Эти процессы опрашивают состояние решающего поля и настраиваются на выполнениесвоей части вычислений.(Они могут узнать: сколько их порождено, свои уникальные, внутренние имена, ит.д.)Процессы, работающие на равных правах (не вызовы процедур и не процессы, связанные понятиями"главная-подчиненная"), иногда называемые сопроцессами, могут выполняться параллельно и при этомобщаться друг с другом - не часто (слабо связанные процессы).3356. Требования к системам программирования методом передачи сообщений.57. Система программирования MPI.Главные цели создания системы параллельного программирования: Создать интерфейс прикладного программирования для МРР систем; Обеспечить возможность эффективных коммуникаций для коммуникации точка-точка,коллективных операций, группы процессов. Допускать удобное сопряжение с языками 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 задается: адрес буфера в памяти; количество принимаемых элементов; тип данных каждого элемента; номер процесса-отправителя в его группе; тег сообщения; коммуникатор; ссылка на объект-статус, содержащий необходимую информацию о состоянии ирезультате операции.Имеется возможность указать "любой отправитель" и "любой тег".Имеется три режима коммуникаций - стандартный, режим готовности и синхронный.34В стандартном режиме последовательность выдачи операций send и receive произвольна, операция sendзавершается тогда, когда сообщение изъято из буфера и он уже может использоваться процессом.В режиме готовности операция send может быть выдана только после выдачи соответствующей операцииreceive, иначе программа считается ошибочной и результат ее работы неопределен.

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

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

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