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

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

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

!$OMP SECTIONS

< фрагмент 1>

!$OMP SECTIONS

< фрагмент 2>

!$OMP SECTIONS

< фрагмент 3>

!$OMP END SECTIONS

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

Если в параллельной секции какой-то участок кода должен быть выполнен лишь один раз (такая ситуация иногда возникает, например, при работе с общими переменными), то его нужно поставить между директивами SINGLE : END SINGLE. Такой участок кода будет выполнен нитью, первой дошедшей до данной точки программы.

Одно из базовых понятий OpenMP - классы переменных. Все переменные, используемые в параллельной секции, могут быть либо общими, либо локальными. Общие переменные описываются директивой SHARED, а локальные директивой PRIVATE. Каждая общая переменная существует лишь в одном экземпляре и доступна для каждой нити под одним и тем же именем. Для каждой локальной переменной в каждой нити существует отдельный экземпляр данной переменной, доступный только этой нити. Предположим, что следующий фрагмент расположен в параллельной секции:

I = OMP_GET_THREAD_NUM()

PRINT *, I

Если переменная I в данной параллельной секции была описана как локальная, то на выходе будет получен весь набор чисел от 0 до OMP_NUM_THREADS-1, идущих, вообще говоря, в произвольном порядке, но каждое число встретиться только один раз. Если же переменная I была объявлена общей, то единственное, что можно сказать с уверенностью - мы получим последовательность из OMP_NUM_THREADS чисел, лежащих в диапазоне от 0 до OMP_NUM_THREADS-1 каждое. Сколько и каких именно чисел будет в последовательности заранее сказать нельзя. В предельном случае, это может быть даже набор из OMP_NUM_THREADS одинаковых чисел I0. Предположим, что все процессы, кроме процесса I0, выполнили первый оператор, но затем их выполнение по какой-то причине было прервано. В это время процесс с номером I0 присвоил это значение переменной I, а поскольку данная переменная является общей, то одно и тоже значение затем и будет выведено каждой нитью.

Целый набор директив в OpenMP предназначен для синхронизации работы нитей. Самый распространенный способ синхронизации - барьер. Он оформляется с помощью директивы

!$OMP BARRIER .

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

Пара директив MASTER : END MASTER выделяет участок кода, который будет выполнен только нитью-мастером. Остальные нити пропускают данный участок и продолжают работу с выполнения оператора, расположенного следом за директивой END MASTER.

С помощью директив

!$OMP CRITICAL [ (<имя_критической_секции>) ]

...

!$OMP END CRITICAL [ (< имя_ критической_секции >) ],

оформляется критическая секция программы. В каждый момент времени в критической секции может находиться не более одной нити. Если критическая секция уже выполняется какой-либо нитью P0, то все другие нити, выполнившие директиву для секции с данным именем, будут заблокированы, пока нить P0 не закончит выполнение данной критической секции. Как только P0 выполнит директиву END CRITICAL, одна из заблокированных на входе нитей войдет в секцию. Если на входе в критическую секцию стояло несколько нитей, то случайным образом выбирается одна из них, а остальные заблокированные нити продолжают ожидание. Все неименованные критические секции условно ассоциируются с одним и тем же именем.

Частым случаем использования критических секций на практике является обновление общих переменных. Например, если переменная SUM является общей и оператор вида SUM=SUM+Expr находится в параллельной секции программы, то при одновременном выполнении данного оператора несколькими нитями можно получить некорректный результат. Чтобы избежать такой ситуации можно воспользоваться механизмом критических секций или специально предусмотренной для таких случаев директивой ATOMIC:

!$OMP ATOMIC

SUM=SUM+Expr .

Данная директива относится к идущему непосредственно за ней оператору, гарантируя корректную работу с общей переменной, стоящей в левой части оператора присваивания.

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

!$OMP FLUSH [ список_переменных ].

Выполнение данной директивы предполагает, что значения всех переменных, временно хранящиеся в регистрах, будут занесены в основную память, все изменения переменных, сделанные нитями во время их работы, станут видимы остальным нитям, если какая-то информация хранится в буферах вывода, то буферы будут сброшены и т.п. Поскольку выполнение данной директивы в полном объеме может повлечь значительных накладных расходов, а в данный момент нужна гарантия согласованного представления не всех, а лишь отдельных переменных, то эти переменные можно явно перечислить в директиве списком.

Ограничения на распараллеливание циклов.

Ограничения на используемые операторы в векторизуемых циклах

Существенным ограничением на конструкции, которые могут применяться в векторизуемых циклах, является использование только операторов присваивания и арифметических выражений. Никакие команды перехода (условные ветвления, вызовы подпрограмм и функций, циклические операторы или безусловные переходы) не могут быть использованы в теле векторизуемого цикла.

Индексные выражения не должны иметь индекс в индексе А(В(С))

Из перечисленных запретов существует только два исключения. Первое - использование встроенных (INTRINSIC) в транслятор арифметических функций. Большинство таких функций реализуются в библиотеках языка, а некоторые транслируются в последовательности машинных команд. Обычно каждая функция имеет две реализации - скалярную и векторную. Про встроенные функции транслятор "знает" все, чтобы сгенерировать векторный код. Примером может служить функция cos(x). Скалярная реализация может брать свой аргумент в определенном регистре (например, r0) и возвращать значение в том же регистре сохраняя прежними значения остальных регистров. Векторный выриант может брать аргумент в векторном регистре (например, v0) и там же оставлять результат. Поэтому транслятору достаточно вычислить массив аргументов в заданном регистре, вызвать библиотечную функцию и далее работать с полученным массивом значений.

Важное замечание для любителей Си. В этом языке все математические функции внешние - они описываются в файле math.h и содержаться в дополнительной (!) библиотеке libm.a - и они не векторизуются (чаще всего). В ФОРТРАНе большое число функций (в т.ч. и комплексного аргумента) встроены. Разработчики программного обеспечения для векторных ЭВМ обычно расширяют стандартный набор функций, что позволяет использовать их в векторизуемых циклах.

Второе исключение - использование условного оператора присваивания

if( x(i) .lt. 0.0 ) z(i) = 0.0

Все арифметические операции (в т.ч. и само присваивание) будут выполняться не над всем векторным регистром, а только над теми его элементами, для которых было справедливо вычисленное логическое выражение (маскируемые операции). Команда сравнения устанавливает маску для каждого элемента вектора: "истина", если элемент вектора меньше нуля, и "ложь", если элемент больше или равен нулю. Команда присваивания не затронет те элементы массива z, для которых маска равна "ложь". Векторный процессор будет исполнять команды для вычисления арифметического выражения и команду присваивания, даже если не будет ни одного значения маски "истина". Это важное примечание. Команды исполнения по маске всегда будут занимать процессорное время.

Синхронизация параллельных процессов. Барьеры.

Основным механизмом синхронизации параллельных процессов, взаимодействующих с помощью передачи сообщений, является барьер. Барьер - это точка параллельной программы, в которой процесс ждёт все остальные процессы, с которыми он синхронизирует свою работу. Лишь только после того, как все процессы, синхронизирующие свою работу, достигли барьера, они продолжают дальнейшие вычисления. Если по какой-то причине хотя бы один из этих процессов не достигает барьера, то остальные процессы "зависают" в этой точке программы, а программа в целом уже никогда не сможет завершиться нормально.

Барьеры – весьма своеобразное средство синхронизации. Идея его в том, чтобы в определенной точке ожидания собралось заданное число потоков управления. Только после этого они смогут продолжить выполнение. (Поговорка "семеро одного не ждут" к барьерам не применима.)

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

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

Критические секции. Двоичные и общие семафоры.

Важным понятием синхронизации процессов является понятие "критическая секция" программы. Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением.

Простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.

Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 2.4 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.

Если все процессы написаны с использованием вышеописанных соглашений, то взаимное исключение гарантируется. Следует заметить, что операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к нежелаемым последствиям. Во избежание таких ситуаций в системе команд машины желательно иметь единую команду "проверка-установка", или же реализовывать системными средствами соответствующие программные примитивы, которые бы запрещали прерывания на протяжении всей операции проверки и установки.

Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения таких ситуаций может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 2.5 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

Общий семафор - это целочисленная переменная, над которой разре­шены только две неделимые операции P и V. Аргументом у этих операций является семафор. Определять семантику этих операций можно только для семафоров - положительных чисел, или включать и отрицательный диапа­зон. Операции могут быть определены так:

P(S) - декремент и анализ семафора

S := S-1

IF (S < 0) THEN <блокировка текущего процесса>

ENDIF

V(S) - инкремент семафора

S := S+1

IF S <= 0 THEN <запустить блокированный процесс>

ENDIF

P и V операции неделимы: в каждый момент только один процесс может выполнять Р или V операцию над данным семафором. Если семафор используется как счетчик ресурсов, то:

S >= 1 - есть некоторое количество (S) доступных ресурсов,

S = 0 - нет доступного ресурса,

S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.

Вводится, также, операция инициализации семафора (присвоение начального значения). Общий семафор - избыточный, т.к. его можно реализовать через двоичные семафоры, которые принимают только два значения 0,1.

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

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