СКИПОДы конспект лекций (1127769), страница 20
Текст из файла (страница 20)
Границыизменения переменной цикла T меняются при переходе с одной прямой (гиперплоскости) на другую,поэтому их необходимо перевычислять во внешнем цикле. Число итераций внутреннего цикла, то естьпотенциальная длина векторной операции, меняется с изменением K .
Для приведенного примерадиапазон изменения T сначала возрастает, а потом убывает, причем для начального и конечного значенияK он равен единице. В некоторых случаях для отдельных значений K накладные расходы наорганизацию векторного вычисления могут превысить эффект ускорения от векторного выполнения.Вопрос оценки целесообразности проведения векторизации данным методом должен рассматриваться длякаждого конкретного случая отдельно.66.
Метод параллелепипедов.Идея методазаключаетсяввыявлении зависимых итераций цикла и объединении их впоследовательности - ветви, которые могут быть выполнены независимо друг от друга. П ри этом впространстве итераций определяются области (параллелепипеды), все точки которых принадлежат разнымветвям. Задача максимального распараллеливания заключается в поиске параллелепипеда наибольшегообъема; тогда исходный цикл выполняется наибольшим числом параллельных ветвей, каждая из которыхпредставляет собой исходный цикл, но с другим шагом изменения индекса.Для исходного цикла:DO 7 I = 1,7DO 7 J = 1,37 X(I,J) = X(I-2,J-1)параллельное представление в виде:DO 7 (K,L) = (1,1) (P1,P2)1: PARDO 7 I = K,7,P1DO 7 J = L,3,P27 X(I,J) = X(I-2,J-1)допускается для различных разбиений пространства итераций: пара (P1,P2) может иметь, например,значения (2,1), (2,3) или (7,1).
Таким образом, исходный цикл (7) преобразуется в последовательностьпараллельных ветвей, имеющих циклический вид.В общем виде задача, рассматриваемая методом параллелепипедов, для одномерных циклов состоит вопределении возможности представления цикла:DO L I = 1,rL T(I)(где T(i) - тело цикла) в виде следующей языковой конструкции:DO L K = 1,p1: PARDO L I = K,r,pL T(I)67. Оценить возможность параллельного выполнения цикла: DO i = 2,N A(i) = (B(i) +(i))/A(i+CONST) ENDDOЕсли const = 0, то все итерации цикла независимы и такой цикл может быть выполнен на любоймногопроцессорной ЭВМ, включая Иллиак-4.
(каждый виток цикла выполняется на отдельном процессоре)Если const > 0 (пусть =1) то при параллельное выполнение цикла на ЭВМ класса МКМД бездополнительных мер по синхронизации работы процессоров невозможно. Например, пусть N=3 и двапроцессора вычисляют параллельно эти итерации, тогда, первый процессор вычисляет А2 по В2, С2, А3, авторой, А3 по В2, С2, А4 . При отсутствии синхронизации может случиться ситуация, при которой второйпроцессор завершит свою работу до начала работы первого.
Тогда первый процессор для вычислений будетиспользовать А3, которое обновил второй процессор, что неверно, ибо здесь нужно ―старое‖ значение А3.Однако, этот цикл выполняется параллельно на ЭВМ ОКМД (SIMD) так как там этот цикл может бытьвыполнен такими командами:1. Считать Вi в сумматоры каждого из n АЛУ.2. Сложить Сi со своим содержимом сумматора.483. Разделить содержимое каждого i-сумматора на Аi+1.4. Записать содержимое i- сумматоров в Аi.Из за того, что выборка из памяти и запись в память производится синхронно (одновременно), то работацикла – корректна.Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполнения очередной итерациицикла необходимы результаты работы предыдущей (рекурсия).
Однако известны приемы преобразованиятакого рода циклов к виду, допускающие параллельное выполнение.68. Стандарты OpenMP.Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах(SSMP,ccNUMA, etc.) в модели общей памяти (shared memory model). В стандарт OpenMP входятспецификации набора директив компилятора, процедур и переменных среды.До появления OpenMP не было подходящего стандарта для эффективного программирования на SMPсистемах.Наиболее гибким, переносимым и общепринятым интерфейсом параллельного программирования являетсяMPI (интерфейс передачи сообщений). Однако модель передачи сообщений 1) недостаточно эффективна наSMP-системах; 2) относительно сложна в освоении, так как требует мышления в "невычислительных"терминах.Проект стандарта X3H5 провалился, так как был предложен во время всеобщего интереса к MPP-системам,а также из-за того, что в нем поддерживается только параллелизм на уровне циклов.
OpenMP развиваетмногие идеи X3H5.POSIX-интерфейс для организации нитей (Pthreads) поддерживается широко (практически на всех UNIXсистемах), однако по многим причинам не подходит для практического параллельного программирования: нет поддержки Fortran-а, слишком низкий уровень, нет поддержки параллелизма по данным, механизм нитей изначально разрабатывался не для целей организации параллелизма.OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (или аналогичнымибиблиотеками нитей).Многие поставщики SMP-архитектур (Sun,HP,SGI) в своих компиляторах поддерживают спецдирективыдля распараллеливания циклов.
Однако эти наборы директив, как правило, 1) весьма ограничены; 2)несовместимы между собой; в результате чего разработчикам приходится распараллеливать приложениеотдельно для каждой платформы. OpenMP является во многом обобщением и расширением упомянутыхнаборов директив.Директивы OpenMP с точки зрения Фортрана являются комментариями и начинаются с комбинациисимволов "!$OMP".
Директивы можно разделить на 3 категории: определение параллельной секции,разделение работы, синхронизация. Каждая директива может иметь несколько дополнительных атрибутов клауз. Отдельно специфицируются клаузы для назначения классов переменных, которые могут бытьатрибутами различных директив.Порождение нитейPARALLEL ... END PARALLELОпределяет параллельную область программы.
При входе в эту область порождаются новые (N-1),образуется "команда" из N нитей, а порождающая нить получает номер 0 и становится основной нитьюкоманды (т.н. "master thread"). При выходе из параллельной области основная нить дожидается завершенияостальных нитей, и продолжает выполнение в одном экземпляре. Предполагается, что в SMP-системе нитибудут распределены по различным процессорам (однако это, как правило, находится в веденииоперационной системы).Каким образом между порожденными нитями распределяется работа - определяется директивамиDO,SECTIONS и SINGLE.
Возможно также явное управление распределением работы (а-ля MPI) спомощью функций, возвращающих номер текущей нити и общее число нитей. По умолчанию (вне этихдиректив), код внутри PARALLEL исполняется всеми нитями одинаково.Вместе с PARALLEL может использоваться клауза IF(условие) - й параллельная работа инициируетсятолько при выполнении указанного в ней условия.49Параллельные области могут динамически вложенными. По умолчанию (если вложенный параллелизм неразрешен явно), внутренняя параллельная область исполняется одной нитью.Разделение работы (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Определяет точку барьерной синхронизации, в которой каждая нить дожидается всех остальных.ATOMICОпределяет переменную в левой части оператора "атомарного" присваивания, которая должнакорректно обновляться несколькими нитями.ORDERED ... END ORDEREDОпределяет блок внутри тела цикла, который должен выполняться в том порядке, в которомитерации идут в последовательном цикле.
Может использоваться для упорядочения вывода отпараллельных нитей.FLUSHЯвно определяет точку, в которой реализация должна обеспечить одинаковый вид памяти для всех50нитей. Неявно FLUSH присутствует в следующих директивах: BARRIER, CRITICAL, ENDCRITICAL, END DO, END PARALLEL, END SECTIONS, END SINGLE, ORDERED, ENDORDERED.В целях синхронизации можно также пользоваться механизмом замков (locks).В OpenMP переменные в параллельных областях программы разделяются на два основных класса: SHARED (общие; под именем A все нити видят одну переменную) и PRIVATE (приватные; под именем A каждая нить видит свою переменную).Отдельные правила определяют поведение переменных при входе и выходе из параллельной области илипараллельного цикла: REDUCTION, FIRSTPRIVATE, LASTPRIVATE, COPYIN.В целях создания переносимой среды запуска параллельных программ, в OpenMP определен рядпеременных среды, контролирующих поведение приложения.В OpenMP предусмотрен также набор библиотечных процедур, которые позволяют: во время исполнения контролировать и запрашивать различные параметры, определяющиеповедение приложения (такие как число нитей и процессоров, возможность вложенногопараллелизма); процедуры назначения параметров имеют приоритет над соответствующимипеременными среды. использовать синхронизацию на базе замков (locks).69.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
