ПОД конспект (1184369), страница 20
Текст из файла (страница 20)
Оценить возможность параллельного выполнения цикла: 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.
Язык Фортран-DVM.DVM-модель выполнения параллельной программы охватывает параллелизм по данным и параллелизмзадачи (см. также проект [ИСП РАН/Java-DVM]). В рамках DVM-модели программист (в рамкахпространства глобальных имен - единое адресное пространство) определяет:распределение элементов массивов по процессорам;распределение витков циклов по процессорам;организацию эффективного доступа к данным, расположенным на иных процессорах;организацию эффективного выполнения редукционных операций (например, sum, min, max элементов распределенного массива).Язык Фортран-DVM: Фортран-77, со вставкой специальных комментариев.Компиляция для однопроцессорных (последовательных) платформ: спецкомментарии прозрачныдля стандартных компиляторов;Компиляция для многопроцессорных платформ: собственный Фортран-DVM компиляторрасширяет спецкомментарии в конструкции с обращениями к библиотеке run-time support.Язык Си-DVM: стандартный Си, с библиотекой специальных макросов (с "пустым" определениеммакросов), реализующих DVM-модель.Компиляция для однопроцессорных (последовательных) платформ: спецмакросы прозрачны длястандартных компиляторов, так как они имеют пустое определение;Компиляция для многопроцессорных платформ: собственный Си-DVM компилятор расширяетспецмакросы в конструкции с обращениями к библиотеке run-time support.Имеются средства трассировки (последовательного и параллельного исполнения одной и той жепрограммы), сравнения трасс, измерения параметров эффективности (распараллеливания) исполненияпрограмм.Компиляция программ на языках Фортран/Си-DVM поддержана на платформы:обычные (последовательные) ЭВМ со стандартным языком Фортран-77/Си (последовательнаяотладка и т.п.);параллельные ЭВМ с MPI + Фортран/Си (в том числе: МВС-100);параллельные ЭВМ с PVM + Фортран/Си (в том числе: HP Convex SPP-1000);параллельные ЭВМ с GNS или ОС Router + Фортран/Си (в том числе: МВС-100).51Язык Fortran DVM (FDVM) представляет собой язык Фортран 77 [5], расширенный спецификациямипараллелизма.
Эти спецификации оформлены в виде специальных комментариев, которые называютсядирективами. Директивы FDVM можно условно разделить на три подмножества: Распределение данных Распределение вычислений Спецификация удаленных данныхМодель параллелизма FDVM базируется на специальной форме параллелизма по данным: однапрограмма – множество потоков данных (ОПМД). В этой модели одна и та же программа выполняется накаждом процессоре, но каждый процессор выполняет свое подмножество операторов в соответствии сраспределением данных.В модели FDVM пользователь вначале определяет многомерный массив виртуальных процессоров, насекции которого будут распределяться данные и вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
