ПОД (пособие) (1184372), страница 39
Текст из файла (страница 39)
В сеточных методах это может бытьчетный или нечетный номер строки (столбца) сетки или неравенство нулю элементовматрицы.Операции приведения122Операции приведения применяются ко всем элементам массива (или его сечения), арезультатом является одно единственное значение, например, сумма элементов массива илимаксимальное значение его элементов.Операции сдвигаДля эффективной реализации некоторых параллельных алгоритмов требуютсяоперации сдвига массивов.
Примерами служат алгоритмы обработки изображений,конечно-разностные алгоритмы и некоторые другие.Операции сканированияОперации сканирования еще называются префиксными/суффиксными операциями.Префиксная операция, например, суммирование выполняется следующим образом.Элементы массива суммируются последовательно, а результат очередного суммированиязаносится в очередную ячейку нового, результирующего массива, причем номер этойячейки совпадает с числом просуммированных элементов исходного массива.Операции пересылки данныхЭто, например, операции пересылки данных между массивами разной формы (тоесть имеющими разную размерность и разную протяженность по каждому измерению) инекоторые другие.При программировании на основе параллелизма данных часто используютсяспециализированные языки - CM FORTRAN, C*, FORTRAN+, MPP FORTRAN, ViennaFORTRAN, а также HIGH PERFORMANCE FORTRAN (HPF).
HPF основан на языкепрограммирования ФОРТРАН 90, что связано с наличием в последнем удобных операцийнад массивами (см., например, М.Меткалф и Дж.Рид Описание языка программированияФОРТРАН 90, М."Мир", 1995).Параллелизм задачСтиль программирования, основанный на параллелизме задач подразумевает, чтовычислительная задача разбивается на несколько относительно самостоятельных подзадач икаждый процессор загружается своей собственной подзадачей. Компьютер при этомпредставляет собой MIMD - машину. Аббревиатура MIMD обозначает в известнойклассификации архитектур ЭВМ (см. в тексте классификацю Флинна – прим.
А.Е.)компьютер, выполняющий одновременно множество различных операций над множеством,вообще говоря, различных и разнотипных данных. Для каждой подзадачи пишется своясобственная программа на обычном языке программирования, обычно это ФОРТРАН илиС. Чем больше подзадач, тем большее число процессоров можно использовать, тем большейэффективности можно добиться. Важно то, что все эти программы должны обмениватьсярезультатами своей работы, практически такой обмен осуществляется вызовом процедурспециализированной библиотеки.
Программист при этом может контролироватьраспределение данных между процессорами и подзадачами и обмен данными. Очевидно,что в этом случае требуется определенная работа для того, чтобы обеспечить эффективноесовместное выполнение различных программ.
По сравнению с подходом, основанным напараллелизме данных, данный подход более трудоемкий, с ним связаны следующиепроблемы:повышенная трудоемкость разработки программы и ее отладки;на программиста ложится вся ответственность за равномерную загрузку процессоровпараллельного компьютера;программисту приходится минимизировать обмен данными между задачами, так какпересылка данных - наиболее "времяемкий" процесс;повышенная опасность возникновения тупиковых ситуаций, когда отправленная однойпрограммой посылка с данными не приходит к месту назначения.Привлекательными особенностями данного подхода являются большая гибкость ибольшая свобода, предоставляемая программисту в разработке программы, эффективноиспользующей ресурсы параллельного компьютера и, как следствие, возможность123достижения максимального быстродействия. Примерами специализированных библиотекявляются библиотеки MPI (Message Passing Interface) и PVM (Parallel Virtual Machines).
Этибиблиотеки являются свободно распространяемыми и существуют в исходных кодах.Библиотека MPI разработана в Аргоннской Национальной Лаборатории (США), а PVM разработка Окриджской Национальной Лаборатории, университетов штата Теннеси иЭмори (Атланта).Разделение последовательных программ на параллельные нити.Как, с точки зрения OpenMP, пользователь должен представлять свою параллельнуюпрограмму? Весь текст программы разбит на последовательные и параллельные области(см. рис.1). В начальный момент времени порождается нить-мастер или "основная" нить,которая начинает выполнение программы со стартовой точки. Здесь следует сразу сказать,почему вместо традиционных для параллельного программирования процессов появилсяновый термин - нити (threads, легковесные процессы).
Технология OpenMP опирается напонятие общей памяти, поэтому она, в значительной степени, ориентирована на SMPкомпьютеры. На подобных архитектурах возможна эффективная поддержка нитей,исполняющихся на различных процессорах, что позволяет избежать значительныхнакладных расходов на поддержку классических UNIX-процессов.Основная нить и только она исполняет все последовательные области программы.
Привходе в параллельную область порождаются дополнительные нити. После порождениякаждая нить получает свой уникальный номер, причем нить-мастер всегда имеет номер 0.Все нити исполняют один и тот же код, соответствующий параллельной области. Привыходе из параллельной области основная нить дожидается завершения остальных нитей, идальнейшее выполнение программы продолжает только она.В параллельной области все переменные программы разделяются на два класса: общие(SHARED) и локальные (PRIVATE). Общая переменная всегда существует лишь в одномэкземпляре для всей программы и доступна всем нитям под одним и тем же именем.Объявление же локальной переменной вызывает порождение своего экземпляра даннойпеременной для каждой нити.
Изменение нитью значения своей локальной переменной,естественно, никак не влияет на изменение значения этой же локальной переменной вдругих нитях.124По сути, только что рассмотренные два понятия: области и классы переменных, иопределяют идею написания параллельной программы в рамках OpenMP: некоторыефрагменты текста программы объявляется параллельными областями; именно эти области итолько они исполняются набором нитей, которые могут работать как с общими, так и слокальными переменными. Все остальное - это конкретизация деталей и описаниеособенностей реализации данной идеи на практике.Рассмотрим базовые положения и основные конструкции OpenMP.
Все директивы OpenMPрасполагаются в комментариях и начинаются с одной из следующих комбинаций: !$OMP,C$OMP или *$OMP (напомним, что строка, начинающаяся с одного из символов '!', 'C' или'*' по правилам языка Фортран считается комментарием). В дальнейшем изложении приописании конкретных директив для сокращения записи мы иногда будем опускать этипрефиксы, хотя в реальных программах они, конечно же, всегда должны присутствовать.Все переменные окружения и функции, относящиеся к OpenMP, начинаются с префиксаOMP_ .Описание параллельных областей. Для определения параллельных областей программыиспользуется пара директив!$OMP PARALLEL< параллельный код программы >!$OMP END PARALLELДля выполнения кода, расположенного между данными директивами, дополнительнопорождается OMP_NUM_THREADS-1 нитей, где OMP_NUM_THREADS - это переменнаяокружения, значение которой пользователь, вообще говоря, может изменять.
Процесс,выполнивший данную директиву (нить-мастер), всегда получает номер 0. Все нитиисполняют код, заключенный между данными директивами. После END PARALLELавтоматически происходит неявная синхронизация всех нитей, и как только все нитидоходят до этой точки, нить-мастер продолжает выполнение последующей частипрограммы, а остальные нити уничтожаются.Параллельные секции могут быть вложенными одна в другую. По умолчанию вложеннаяпараллельная секция исполняется одной нитью. Необходимую стратегию обработкивложенных секций определяет переменная OMP_NESTED, значение которой можноизменить с помощью функции OMP_SET_NESTED.Если значение переменной OMP_DYNAMIC установлено в 1, то с помощью функцииOMP_SET_NUM_THREADS пользователь может изменить значение переменнойOMP_NUM_THREADS, а значит и число порождаемых при входе в параллельную секциюнитей.ЗначениепеременнойOMP_DYNAMICконтролируетсяфункциейOMP_SET_DYNAMIC.Необходимость порождения нитей и параллельного исполнения кода параллельной секциипользователь может определять динамически с помощью дополнительной опции IF вдирективе:!$OMP PARALLEL IF( <условие> )Если <условие> не выполнено, то директива не срабатывает и продолжается обработкапрограммы в прежнем режиме.Мы уже говорили о том, что все порожденные нити исполняют один и тот же код.
Теперьнужно обсудить вопрос, как разумным образом распределить между ними работу. OpenMPпредлагает несколько вариантов. Можно программировать на самом низком уровне,125распределяяработуспомощьюфункцийOMP_GET_THREAD_NUMиOMP_GET_NUM_THREADS, возвращающих номер нити и общее количествопорожденных нитей соответственно. Например, если написать фрагмент вида:IF( OMP_GET_THREAD_NUM() .EQ. 3 ) THEN< код для нити с номером 3 >ELSE< код для всех остальных нитей >ENDIF ,то часть программы между директивами IF:ELSE будет выполнена только нитью с номером3, а часть между ELSE:ENDIF - всеми остальными. Как и прежде, этот код будет выполненвсеми нитями, однако функция OMP_GET_THREAD_NUM() возвратит значение 3 толькодля нити с номером 3, поэтому и выполнение данного участка кода для третьей нити и всехостальных будет идти по-разному.Если в параллельной секции встретился оператор цикла, то, согласно общему правилу, онбудет выполнен всеми нитями, т.е.
каждая нить выполнит все итерации данного цикла. Дляраспределения итераций цикла между различными нитями можно использовать директиву!$OMP DO [опция [[,] опция]:]!$OMP END DO ,которая относится к идущему следом за данной директивой оператору DO.Опция SCHEDULE определяет конкретный способ распределения итераций данного циклапо нитям:STATIC [,m] - блочно-циклическое распределение итераций: первый блок из m итерацийвыполняет первая нить, второй блок - вторая и т.д. до последней нити, затем распределениеснова начинается с первой нити; по умолчанию значение m равно 1;DYNAMIC [,m] - динамическое распределение итераций с фиксированным размером блока:сначала все нити получают порции из m итераций, а затем каждая нить, заканчивающаясвою работу, получает следующую порцию опять-таки из m итераций;GUIDED [,m] - динамическое распределение итераций блоками уменьшающегося размера;аналогично распределению DYNAMIC, но размер выделяемых блоков все времяуменьшается, что в ряде случаев позволяет аккуратнее сбалансировать загрузку нитей;RUNTIME - способ распределения итераций цикла выбирается во время работы программыв зависимости от значения переменной OMP_SCHEDULE.Выбранный способ распределения итераций указывается в скобках после опцииSCHEDULE, например:!$OMP DO SCHEDULE (DYNAMIC, 10)В данном примере будет использоваться динамическое распределение итераций блоками по10 итераций.В конце параллельного цикла происходит неявная барьерная синхронизация параллельноработающих нитей: их дальнейшее выполнение происходит только тогда, когда все онидостигнут данной точки.
Если в подобной задержке нет необходимости, то директива ENDDO NOWAIT позволяет нитям уже дошедшим до конца цикла продолжить выполнение безсинхронизации с остальными. Если директива END DO в явном виде и не указана, то вконце параллельного цикла синхронизация все равно будет выполнена. Рассмотримследующий пример, расположенный в параллельной секции программы:!$OMP DO SCHEDULE (STATIC, 2)DO i = 1, n126DO j = 1, mA( i, j) = ( B( i, j-1) + B( i-1, j) ) / 2.0END DOEND DO!$OMP END DOВ данном примере внешний цикл объявлен параллельным, причем будет использованоблочно-циклическое распределение итераций по две итерации в блоке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
