ПОД (пособие) (1184372), страница 50
Текст из файла (страница 50)
(каждый виток цикла выполняется наотдельном процессоре)Если const > 0 (пусть =1) то при параллельное выполнение цикла на ЭВМ класса МКМД бездополнительных мер по синхронизации работы процессоров невозможно. Например, пустьN=3 и два процессора вычисляют параллельно эти итерации, тогда, первый процессорвычисляет А2 по В2, С2, А3, а второй, А3 по В2, С2, А4 . При отсутствии синхронизацииможет случиться ситуация, при которой второй процессор завершит свою работу до началаработы первого. Тогда первый процессор для вычислений будет использовать А3, котороеобновил второй процессор, что неверно, ибо здесь нужно “старое” значение А3.
Однако,этот цикл выполняется параллельно на ЭВМ ОКМД (SIMD) так как там этот цикл можетбыть выполнен такими командами:1. Считать Вi в сумматоры каждого из n АЛУ.2. Сложить Сi со своим содержимом сумматора.3. Разделить содержимое каждого i-сумматора на Аi+1.4. Записать содержимое i- сумматоров в Аi.Из за того, что выборка из памяти и запись в память производится синхронно(одновременно), то работа цикла – корректна.Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполненияочередной итерации цикла необходимы результаты работы предыдущей (рекурсия). Однакоизвестны приемы преобразования такого рода циклов к виду, допускающие параллельноевыполнение.Языки параллельного программированияСтандарты OpenMP.1. Введение.
Что такое OpenMP?Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMPсистемах (SSMP,ccNUMA, etc.) в модели общей памяти (shared memory model). В стандартOpenMP входят спецификации набора директив компилятора, процедур и переменныхсреды.Кто разрабатывает стандарт?Разработкой стандарта занимается организация OpenMP ARB (ARchitecture Board), вкоторую вошли представители крупнейших компаний - разработчиков SMP-архитектур ипрограммного обеспечения. Спецификации для языков Fortran и C/C++ появилисьсоответственно в октябре 1997 года и октябре 1998 года.
Открыт список рассылки дляпубличного обсуждения OpenMP (omp@openmp.org).Зачем нужен новый стандарт?До появления OpenMP не былопрограммирования на SMP-системах.подходящего164стандартадляэффективногоНаиболее гибким, переносимым и общепринятым интерфейсом параллельногопрограммирования является MPI (интерфейс передачи сообщений). Однако модельпередачи сообщений 1) недостаточно эффективна на SMP-системах; 2) относительносложна в освоении, так как требует мышления в "невычислительных" терминах.POSIX-интерфейс для организации нитей (Pthreads) поддерживается широко (практическина всех UNIX-системах), однако по многим причинам не подходит для практическогопараллельного программирования:нет поддержки Fortran-а,слишком низкий уровень,нет поддержки параллелизма по данным,механизм нитей изначально разрабатывался не для целей организации параллелизма.OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (илианалогичными библиотеками нитей).Многие поставщики SMP-архитектур (Sun,HP,SGI) в своих компиляторах поддерживаютспецдирективы для распараллеливания циклов.
Однако эти наборы директив, как правило,1) весьма ограничены; 2) несовместимы между собой; в результате чего разработчикамприходится распараллеливать приложение отдельно для каждой платформы. OpenMPявляется во многом обобщением и расширением упомянутых наборов директив.Какие преимущества OpenMP дает разработчику?1. За счет идеи "инкрементального распараллеливания" OpenMP идеально подходит дляразработчиков, желающих быстро распараллелить свои вычислительные программы сбольшими параллельными циклами. Разработчик не создает новую параллельнуюпрограмму, а просто последовательно добавляет в текст последовательной программыOpenMP-директивы.2.
При этом, OpenMP - достаточно гибкий механизм, предоставляющий разработчикубольшие возможности контроля над поведением параллельного приложения.3. Предполагается, что OpenMP-программа на однопроцессорной платформе может бытьиспользована в качестве последовательной программы, т.е. нет необходимостиподдерживать последовательную и параллельную версии. Директивы OpenMP простоигнорируются последовательным компилятором, а для вызова процедур OpenMP могутбыть подставлены заглушки (stubs), текст которых приведен в спецификациях.4. Одним из достоинств OpenMP его разработчики считают поддержку так называемых"orphan" (оторванных) директив, то есть директивы синхронизации и распределения работымогут не входить непосредственно в лексический контекст параллельной области.Как это работает?Согласно терминологии POSIX threads, любой UNIX-процесс состоит несколько нитейуправления, которые имеют общее адресное пространство, но разные потоки команд ираздельные стэки.
В простейшем случае, процесс состоит из одной нити. Нити иногданазывают также потоками, легковесными процессами, LWP (light-weight processes).В OpenMP используется терминология и модель программирования, близкая к Pthreads(динамически порождаемые нити, общие и разделяемые данные, механизм "замков" для165синхронизации). Предполагается наиболее вероятным, что OpenMP будет реализован набазе Pthreads.Как это выглядит?Простой пример: вычисление числа "Пи". В последовательную программу вставлены двестрочки, и она распараллелена!program compute_piparameter (n = 1000)integer idouble precision w,x,sum,pi,f,af(a) = 4.d0/(1.d0+a*a)w = 1.0d0/nsum = 0.0d0;!$OMP PARALLEL DO PRIVATE(x), SHARED(w)!$OMP& REDUCTION(+:sum)do i=1,nx = w*(i-0.5d0)sum = sum + f(x)enddopi = w*sumprint *,'pi = ',pistopend2.
ДирективыДирективы OpenMP с точки зрения Фортрана являются комментариями и начинаются скомбинации символов "!$OMP". Директивы можно разделить на 3 категории: определениепараллельной секции, разделение работы, синхронизация. Каждая директива может иметьнесколько дополнительных атрибутов - клауз. Отдельно специфицируются клаузы дляназначения классов переменных, которые могут быть атрибутами различных директив.Порождение нитейPARALLEL ... END PARALLELОпределяет параллельную область программы.
При входе в эту область порождаются новые(N-1), образуется "команда" из N нитей, а порождающая нить получает номер 0 истановится основной нитью команды (т.н. "master thread"). При выходе из параллельнойобласти основная нить дожидается завершения остальных нитей, и продолжает выполнениев одном экземпляре. Предполагается, что в SMP-системе нити будут распределены поразличным процессорам (однако это, как правило, находится в ведении операционнойсистемы).Каким образом между порожденными нитями распределяется работа - определяетсядирективами DO,SECTIONS и SINGLE.
Возможно также явное управление распределениемработы (а-ля MPI) с помощью функций, возвращающих номер текущей нити и общее числонитей. По умолчанию (вне этих директив), код внутри PARALLEL исполняется всеминитями одинаково.Вместе с PARALLEL может использоваться клауза IF(условие) - й параллельная работаинициируется только при выполнении указанного в ней условия.166Параллельные области могут динамически вложенными. По умолчанию (если вложенныйпараллелизм не разрешен явно), внутренняя параллельная область исполняется однойнитью.Разделение работы (work-sharing constructs)Параллельные циклыDO ...
[ENDDO]Определяет параллельный цикл.Клауза SCHEDULE определяет способ распределения итераций по нитям:STATIC,m - статически, блоками по m итерацийDYNAMIC,m - динамически, блоками по m (каждая нить берет на выполнение первый ещеневзятый блок итераций)GUIDED,m - размер блока итераций уменьшается экспоненциально до величины mRUNTIME - выбирается во время выполнения .По умолчанию, в конце цикла происходит неявная синхронизация; эту синхронизациюможно запретить с помощью ENDDO NOWAIT.Параллельные секцииSECTIONS ... END SECTIONSНе-итеративная параллельная конструкция. Определяет набор независимых секций кода(т.н., "конечный" параллелизм). Секции отделяются друг от друга директивой SECTION.Примечание.
Если внутри PARALLEL содержится только одна конструкция DO или толькоодна конструкия SECTIONS, то можно использовать укороченную запись: PARALLEL DOили PARALLEL SECTIONS.Исполнение одной нитьюSINGLE ... END SINGLEОпределяет блок кода, который будет исполнен только одной нитью (первой, котораядойдет до этого блока).Явное управление распределением работыС помощью функций OMP_GET_THREAD_NUM() и OMP_GET_NUM_THREADS нитьможет узнать свой номер и общее число нитей, а затем выполнять свою часть работы взависимости от своего номера (этот подход широко используется в программах на базеинтерфейса MPI).Директивы синхронизацииMASTER ... END MASTERОпределяет блок кода, который будет выполнен только master-ом (нулевой нитью).CRITICAL ...
END CRITICALОпределяет критическую секцию, то есть блок кода, который не должен выполнятьсяодновременно двумя или более нитямиBARRIERОпределяет точку барьерной синхронизации, в которой каждая нить дожидается всехостальных.ATOMIC167Определяет переменную в левой части оператора "атомарного" присваивания, котораядолжна корректно обновляться несколькими нитями.ORDERED ... END ORDEREDОпределяет блок внутри тела цикла, который должен выполняться в том порядке, в которомитерации идут в последовательном цикле. Может использоваться для упорядочения выводаот параллельных нитей.FLUSHЯвно определяет точку, в которой реализация должна обеспечить одинаковый вид памятидля всех нитей.
Неявно FLUSH присутствует в следующих директивах: BARRIER,CRITICAL, END CRITICAL, END DO, END PARALLEL, END SECTIONS, END SINGLE,ORDERED, END ORDERED.В целях синхронизации можно также пользоваться механизмом замков (locks).3. Классы переменныхВ OpenMP переменные в параллельных областях программы разделяются на два основныхкласса:SHARED (общие; под именем A все нити видят одну переменную) иPRIVATE (приватные; под именем A каждая нить видит свою переменную).Отдельные правила определяют поведение переменных при входе и выходе изпараллельной области или параллельного цикла: REDUCTION, FIRSTPRIVATE,LASTPRIVATE, COPYIN.По умолчанию, все COMMON-блоки, а также переменные, порожденные вне параллельнойобласти, при входе в эту область остаются общими (SHARED).
Исключение составляютпеременные - счетчики итераций в цикле, по очевидным причинам. Переменные,порожденные внутри параллельной области, являются приватными (PRIVATE). Явноназначить класс переменных по умолчанию можно с помощью клаузы DEFAULT.SHAREDПрименяется к переменным, которые необходимо сделать общими.PRIVATEПрименяется к переменным, которые необходимо сделать приватными.
При входе впараллельную область для каждой нити создается отдельный экземпляр переменной,который не имеет никакой связи с оригинальной переменной вне параллельной области.THREADPRIVATEПрименяется к COMMON-блокам, которые необходимо сделать приватными. Директивадолжна применяться после каждой декларации COMMON-блока.FIRSTPRIVATEПриватные копии переменной при входе в параллельную область инициализируютсязначением оригинальной переменной.LASTPRIVATEПо окончании параллельно цикла или блока параллельных секций, нить, которая выполнилапоследнюю итерацию цикла или последнюю секцию блока, обновляет значениеоригинальной переменной.168REDUCTION(+:A)Обозначает переменную, с которой в цикле производится reduction-операция (например,суммирование). При выходе из цикла, данная операция производится над копиямипеременной во всех нитях, и результат присваивается оригинальной переменной.COPYINПрименяется к COMMON-блокам, которые помечены как THREADPRIVATE.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
