Опции директивы for (начиная с версии 2.0) ordered Эта опция, указывает компилятору, что в цикле могут встречаться директивы omp ordered. С помощью таких директив внутри тела цикла определяют блоки, которые должны выполняться именно в том порядке, в котором итерации идут в последовательном цикле; В версии стандарта 3.0 появилась еще одна опция: collapse(n) Указывает, что n последовательных тесно вложенных циклов ассоциируется с данной директивой; для этих циклов образуется общее пространство итераций, которое делится между нитями; если опция collapse не задана, то директива for относится только к одному непосредственно следующему за ней циклу;

Параллельная пузырьковая сортировка Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения обычно используется модификация, известная в литературе как метод чет-нечетной перестановки (odd-even transposition). Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки берутся элементы с четными или нечетными индексами соответственно, их сравнение всегда осуществляется с правыми соседними элементами массива. Таким образом, на всех нечетных итерациях сравниваются пары (a1, a2), (a3, a4),..., (an-1,an) (при четном n), а на четных итерациях обрабатываются элементы (a2, a3), (a4, a5),..., (an-2,an-1). После n-кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным. В параллельной версии используется макрос: #define compare_exchange(x,y) if(x>y){ tmp=x; x=y; y=tmp;}

Параллельная пузырьковая сортировка #define ARRAYSIZE double arrayX[ ARRAYSIZE ] = …; int upperBound; … upperBound = (ARRAYSIZE %2==0? ARRAYSIZE /2-1 : ARRAYSIZE /2); for (i=0; i

Функции доступа/изменения переменной среды OMP_SCHEDULE При помощи вызова функции omp_get_schedule(omp_sched_t* type, int* chunk) (доступна не в каждой реализации) программист может получить текущее значение типа и порции распределения итераций циклов, заданных в переменной среды OMP_SCHEDULE. Значение по умолчанию переменной OMP_SCHEDULE зависит от реализации. Изменить значение переменной среды OMP_SCHEDULE (доступно не в каждой реализации) из программы можно с помощью вызова функции void omp_set_schedule(omp_sched_t type, int chunk); Допустимые значения констант, задающих тип распределения, описаны в файле omp.h. Обычно это выглядит так: typedef enum omp_sched_t { omp_sched_static = 1, omp_sched_dynamic = 2, omp_sched_guided = 3, omp_sched_auto = 4 } omp_sched_t;

Пример программы для изучения способов распределения итераций #include int main(int argc, char *argv[]) { int i; #pragma omp parallel private(i) { #pragma omp for schedule (static) //(static, 1) (static, 2) (dynamic) //(dynamic, 2) (guided) (guided, 2) … for (i=0; i

Результаты работы программы (номер нити, выполнявшей итерацию): Номер итерации staticstatic, 1static, 2dynamicdynamic, 2 guidedguided,

Параллельные секции Директива sections (sections... end sections) используется для задания не итеративного параллелизма. Эта директива определяет набор независимых секций кода, каждая из которых выполняется своей нитью. Необходимость в использовании таких конструкций возникает, если в программе есть объемные вычисления, не охваченные общим заголовком цикла. Синтаксис: #pragma omp sections [опция [[,] опция]...]

Опции директивы sections private(список переменных) firstprivate(список переменных) lastprivate(список переменных) reduction(оператор : список) nowait

Директива section #pragma omp section Перед первым участком кода в блоке sections директива section не обязательна. Не специфицируется как распределяются нити между секциями (первая секция не обязательно будет выполняться нитью номер 0 или нитью номер 1, …). Если количество нитей больше количества секций, то часть нитей (какая именно – заранее не определено) для выполнения данного блока секций не будет задействована. Если количество нитей меньше количества секций, то некоторым (или всем) нитям достанется выполнение более, чем одной секции.

Задачи (tasks) только начиная с версии 3.0 Синтаксис: #pragma omp task [опция [[,] опция]...] Опции: if( скалярное выражение ) private( список переменных ) firstprivate( список переменных ) shared(список переменных) default ( … ) nowait untied Наличие этой опции означает, что в случае откладывания задача может быть продолжена любой нитью из числа нитей, выполняющих данную параллельную область. Если данная опция не указана, то задача может быть продолжена только породившей её нитью.

Ожидание завершения задач Для гарантированного завершения всех запущенных задач в требуемой точке программы используется директива taskwait: Синтаксис: #pragma omp taskwait Нить, выполнившая данную директиву, приостанавливается до тех пор, пока не будут завершены все ранее запущенные данной нитью независимые задачи.

Применимость опций в директивах ОпцииДирективы parallelforsectionssingleparallelparallel for sections ifxxx privatexxxxxx firstprivatexxxxxx lastprivatexxxx copyprivatex copyinxxx sharedx xx defaultxxx reductionxxxxx schedulexx orderedxx nowaitxxx collapsexx

Синхронизация Синхронизация работы нитей в OpenMP может выполняться явно и неявно. Неявная синхронизация выполняется в конце любой параллельной области при условии, что в момент создания этой области не была указана опция nowait. В некоторых случаях программисту может потребоваться явно указать необходимость остановки всех или некоторых нитей программы вплоть до момента наступления ожидаемого события. Барьерная синхронизация Самый распространенный способ синхронизации в OpenMP – барьер. Он оформляется с помощью директивы barrier. Синтаксис: #pragma omp barrier

Директива ordered Синтаксис: #pragma omp ordered Блок операторов, выделяемых этой директивой, обычно относится к самому последнему из нескольких объемлющих друг друга циклов: … #pragma omp parallel for ordered for( … ){ … } for( … ){ … } #pragma ordered for( … ){ … } …

Критические секции Синтаксис: #pragma omp critical [( )] В каждый момент времени в одной критической секции может находиться не более одной нити. Если критическая секция уже выполняется какой-либо нитью, то все другие нити, выполнившие директиву для секции с данным именем, будут заблокированы, пока вошедшая нить не закончит выполнение данной критической секции. Как только работавшая нить выйдет из критической секции, одна из заблокированных на входе нитей войдет в неё. Если на входе в критическую секцию стояло несколько нитей, то случайным образом выбирается одна из них, а остальные заблокированные нити продолжают ожидание. Все неименованные критические секции рассматриваются как одна секция. Все критические секции, имеющие одно и тоже имя, рассматриваются единой секцией, даже если находятся в разных параллельных областях. Побочные входы и выходы из критической секции запрещены.

Пример критической секции int eventCount; #pragma omp parallel { … if( condition ) #pragma omp critical (events) eventCount += 1; … } Критические секции – очень времяемкие директивы. Быстрее можно, например, так: int eventCount; #pragma omp parallel private(eventCount) reduction(+: eventCount) { … if( condition ) eventCount += 1; … } Однако, если внутри параллельных ветвей нужно иметь значения суммарного eventCount, то использовать редукцию не удастся. Тогда можно попробовать еще один вариант – директиву atomic.

Директива atomic Синтаксис: #pragma omp atomic Данная директива относится к идущему непосредственно за ней оператору присваивания, гарантируя корректную работу с общей переменной, стоящей в его левой части. На время выполнения оператора блокируется доступ к данной переменной всем запущенным в данный момент нитям, кроме нити, выполняющей операцию. Атомарной является только работа с переменной в левой части оператора присваивания, при этом вычисления в правой части не обязаны быть атомарными. int eventCount; #pragma omp parallel { … if( condition ) #pragma omp atomic eventCount += 1; … }

Директива flush Синтаксис: #pragma omp flush [(список переменных)] При выполнении данной директивы: значения всех переменных (или переменных из списка, если он задан), временно хранящиеся в регистрах и кэш-памяти текущей нити, будут занесены в основную память; все изменения переменных, сделанные нитью во время работы, станут видимы остальным нитям; если какая-то информация хранится в буферах вывода, то буферы будут сброшены и т.п. Эти операции производятся только с данными вызвавшей директиву нити. Данные, изменявшиеся другими нитями, не затрагиваются. Поскольку выполнение данной директивы в полном объёме может повлечь значительных накладных расходов, а в данный момент может быть нужна гарантия согласованного представления не всех, а лишь отдельных переменных, то эти переменные можно явно перечислить в директиве списком. До полного завершения операции никакие действия с перечисленными в ней переменными не могут начаться.

Блокировки (locks) Один из вариантов синхронизации в OpenMP реализуется через механизм блокировок или замков (locks). В качестве замков используются общие целочисленные переменные (размер должен быть достаточным для хранения адреса). Данные переменные должны использоваться только как параметры примитивов синхронизации. Замок может находиться в одном из трёх состояний: неинициализированный, разблокированный или заблокированный. Разблокированный замок может быть захвачен некоторой нитью. При этом он переходит в заблокированное состояние. Нить, захватившая замок, и только она может его освободить, после чего замок возвращается в разблокированное состояние. Есть два типа замков: простые замки и множественные замки. Множественный замок может многократно захватываться одной нитью перед его освобождением, в то время как простой замок может быть захвачен только однажды. Для множественного замка вводится понятие коэффициента захваченности (nesting count). Изначально он устанавливается в ноль, при каждом следующем захватывании увеличивается на единицу, а при каждом освобождении уменьшается на единицу. Множественный замок считается разблокированным, если его коэффициент захваченности равен нулю.

Инициализация и деинициализация замков Для инициализации простого или множественного замка используются соответственно функции: void omp_init_lock(omp_lock_t *lock); void omp_init_nest_lock(omp_nest_lock_t *lock); После выполнения функции замок переводится в разблокированное состояние и может быть захвачен. Для множественного замка коэффициент захваченности устанавливается в ноль. Функции void omp_destroy_lock(omp_lock_t *lock); void omp_destroy_nest_lock(omp_nest_lock_t *lock); используются для переведения простого или множественного замка в неинициализированное состояние.

Захват замка Для захватывания замка используются функции void omp_set_lock(omp_lock_t *lock); void omp_set_nest_lock(omp_nest_lock_t *lock); Вызвавшая такую функцию нить дожидается освобождения замка, а затем захватывает его. Замок при этом переводится в заблокированное состояние. Если множественный замок уже захвачен данной нитью, то нить не блокируется, а коэффициент захваченности увеличивается на единицу.

Освобождение замка Для освобождения замка используются функции void omp_unset_lock(omp_lock_t *lock); void omp_unset_nest_lock(omp_lock_t *lock); Вызов такой функции освобождает простой замок, если он был захвачен вызвавшей нитью. Для множественного замка уменьшается на единицу коэффициент захваченности. Если коэффициент станет равен нулю, замок освобождается. Если после освобождения замка есть нити, заблокированные на операции, захватывающей данный замок, замок будет сразу же захвачен одной из ожидающих нитей.

Проверка состояния замка Для неблокирующей попытки захвата замка используются функции int omp_test_lock(omp_lock_t *lock); int omp_test_nest_lock(omp_lock_t *lock); Данные функция пробуют захватить указанный замок. Если это удалось, то для простого замка функция возвращает 1, а для множественного замка – новый коэффициент захваченности. Если замок захватить не удалось, в обоих случаях возвращается 0. Использование замков является наиболее гибким механизмом синхронизации, поскольку с помощью замков можно реализовать все остальные варианты синхронизации.

Дополнительные функции и переменные среды OpenMP Функция double omp_get_wtime(void) возвращает текущее значение системного времени. Функция double omp_get_wtick(void) возвращает точность одного тика системных часов.

Максимальная глубина вложенности параллельных областей Переменная OMP_MAX_ACTIVE_LEVELS задаёт максимально допустимое количество вложенных параллельных областей. Значение переменной может быть установлено при помощи вызова функции void omp_set_max_active_levels(int max); Если значение max превышает максимально допустимое в системе, будет установлено максимально допустимое в системе значение. При вызове из параллельной области результат выполнения зависит от реализации. Значение переменной OMP_MAX_ACTIVE_LEVELS может быть получено при помощи вызова функции int omp_get_max_active_levels(void);

Получение текущей глубины вложенности параллельных областей Функция int omp_get_level(void) выдаёт для вызвавшей нити количество вложенных параллельных областей в данном месте кода. При вызове из последовательной области функция возвращает значение 0. Функция int omp_get_active_level(void) возвращает для вызвавшей нити количество вложенных параллельных областей, обрабатываемых более чем одной нитью, в данном месте кода. При вызове из последовательной области возвращает значение 0.

Получение сведений о родительской нити и о группе нитей Функция int omp_get_ancestor_thread_num( int level ) возвращает для уровня вложенности параллельных областей, заданного параметром level, номер нити, породившей данную нить. Если level меньше нуля или больше текущего уровня вложенности, возвращается -1. Если level=0, функция вернёт 0, а если level = omp_get_level(), вызов эквивалентен вызову функции omp_get_thread_num(). Функция int omp_get_team_size( int level ) возвращает для заданного параметром level уровня вложенности параллельных областей количество нитей, порождённых одной родительской нитью. Если level меньше нуля или больше текущего уровня вложенности, возвращается -1. Если level=0, функция вернёт 1, а если level=omp_get_level(), вызов эквивалентен вызову функции omp_get_num_threads().

Управление размером стека нити Переменная среды OMP_STACKSIZE задаёт размер стека для создаваемых из программы нитей. Значение переменной может задаваться в виде size | sizeB | sizeK | sizeM | sizeG, где size – положительное целое число, а буквы B, K, M, G задают соответственно, байты, килобайты, мегабайты и гигабайты (например: 32K или 2M). Если ни одной из этих букв не указано, размер задаётся в килобайтах. Если задан неправильный формат или невозможно выделить запрошенный размер стека, результат будет зависеть от реализации.

Поведение ждущих нитей и предел параллелизма Переменная среды OMP_WAIT_POLICY задаёт поведение ждущих процессов. Если задано значение ACTIVE, то ждущему процессу будут выделяться циклы процессорного времени, а при значении PASSIVE ждущий процесс может быть отправлен в спящий режим, при этом процессор может быть назначен другим процессам. Переменная среды OMP_THREAD_LIMIT задаёт максимальное число нитей, допустимых в программе. Если значение переменной не является положительным целым числом или превышает максимально допустимое в системе число процессов, поведение программы будет зависеть от реализации. Значение переменной может быть получено при помощи процедуры int omp_get_thread_limit(void).

NVIDIA CUDA (Compute Unified Device Architecture) CUDA – это развитие GPGPU (General purpose graphic processor unit – графический процессор общего назначения). CUDA (Compute Unified Device Architecture) представляет собой совокупность аппаратного (графический процессор или GPU) и программного обеспечения, предоставляющего возможность подготовки и исполнения программ с очень высокой степенью параллелизма.

Graphic processor unit GPU есть специализированное вычислительное устройство, которое является сопроцессором к основному процессору компьютера (CPU), обладает собственной памятью и возможностью параллельного выполнения огромного количества (тысячи и десятки тысяч) отдельных нитей (потоков) обработки данных согласно модели ОКМД. Между потоками, выполняемыми на CPU и потоками, выполняемыми графическим процессором, есть принципиальные различия: нити, выполняемые на GPU, обладают крайне низкой «стоимостью» – их создание и управление ими требует минимальных ресурсов (в отличие от потоков CPU) для эффективной утилизации возможностей GPU нужно использовать многие тысячи отдельных нитей (для CPU обычно бывает трудно организовывать более, чем потоков)

Общая структура CUDA GPUCPU Основная память Ядро Чипсет Кэш Глобальная память Кэш УУ Кэш УУ Кэш УУ Кэш УУ … … АЛУ … … …