Ответы 190 страниц (1184228), страница 36

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

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

DO i=2,N A(I) =(B(i)+C(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 со своим содержимом сумматора.

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-системах.

Наиболее гибким, переносимым и общепринятым интерфейсом параллельного программирования является 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 (динамически порождаемые нити, общие и разделяемые данные, механизм "замков" для синхронизации). Предполагается наиболее вероятным, что OpenMP будет реализован на базе Pthreads.

Как это выглядит?

Простой пример: вычисление числа "Пи". В последовательную программу вставлены две строчки, и она распараллелена!

program compute_pi

parameter (n = 1000)

integer i

double precision w,x,sum,pi,f,a

f(a) = 4.d0/(1.d0+a*a)

w = 1.0d0/n

sum = 0.0d0;

!$OMP PARALLEL DO PRIVATE(x), SHARED(w)

!$OMP& REDUCTION(+:sum)

do i=1,n

x = w*(i-0.5d0)

sum = sum + f(x)

enddo

pi = w*sum

print *,'pi = ',pi

stop

end

2. Директивы

Директивы OpenMP с точки зрения Фортрана являются комментариями и начинаются с комбинации символов "!$OMP". Директивы можно разделить на 3 категории: определение параллельной секции, разделение работы, синхронизация. Каждая директива может иметь несколько дополнительных атрибутов - клауз. Отдельно специфицируются клаузы для назначения классов переменных, которые могут быть атрибутами различных директив.

Порождение нитей

PARALLEL ... END PARALLEL

Определяет параллельную область программы. При входе в эту область порождаются новые (N-1), образуется "команда" из N нитей, а порождающая нить получает номер 0 и становится основной нитью команды (т.н. "master thread"). При выходе из параллельной области основная нить дожидается завершения остальных нитей, и продолжает выполнение в одном экземпляре. Предполагается, что в SMP-системе нити будут распределены по различным процессорам (однако это, как правило, находится в ведении операционной системы).

Каким образом между порожденными нитями распределяется работа - определяется директивами DO,SECTIONS и SINGLE. Возможно также явное управление распределением работы (а-ля MPI) с помощью функций, возвращающих номер текущей нити и общее число нитей. По умолчанию (вне этих директив), код внутри PARALLEL исполняется всеми нитями одинаково.

Вместе с PARALLEL может использоваться клауза IF(условие) - й параллельная работа инициируется только при выполнении указанного в ней условия.

Параллельные области могут динамически вложенными. По умолчанию (если вложенный параллелизм не разрешен явно), внутренняя параллельная область исполняется одной нитью.

Разделение работы (work-sharing constructs)

Параллельные циклы

DO ... [ENDDO]

Определяет параллельный цикл.

Клауза SCHEDULE определяет способ распределения итераций по нитям:

STATIC,m - статически, блоками по m итераций

DYNAMIC,m - динамически, блоками по m (каждая нить берет на выполнение первый еще невзятый блок итераций)

GUIDED,m - размер блока итераций уменьшается экспоненциально до величины m

RUNTIME - выбирается во время выполнения .

По умолчанию, в конце цикла происходит неявная синхронизация; эту синхронизацию можно запретить с помощью 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

Явно определяет точку, в которой реализация должна обеспечить одинаковый вид памяти для всех нитей. Неявно 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

По окончании параллельно цикла или блока параллельных секций, нить, которая выполнила последнюю итерацию цикла или последнюю секцию блока, обновляет значение оригинальной переменной.

REDUCTION(+:A)

Обозначает переменную, с которой в цикле производится reduction-операция (например, суммирование). При выходе из цикла, данная операция производится над копиями переменной во всех нитях, и результат присваивается оригинальной переменной.

COPYIN

Применяется к COMMON-блокам, которые помечены как THREADPRIVATE. При входе в параллельную область приватные копии этих данных инициализируются оригинальными значениями.

4. Runtime-процедуры и переменные среды

В целях создания переносимой среды запуска параллельных программ, в OpenMP определен ряд переменных среды, контролирующих поведение приложения.

В OpenMP предусмотрен также набор библиотечных процедур, которые позволяют:

во время исполнения контролировать и запрашивать различные параметры, определяющие поведение приложения (такие как число нитей и процессоров, возможность вложенного параллелизма); процедуры назначения параметров имеют приоритет над соотвествующими переменными среды.

использовать синхронизацию на базе замков (locks).

Язык Фортран-DVM.

1.2. DVM–подход к разработке параллельных программ

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

Список файлов ответов (шпаргалок)