Как оформляются в программе результаты параллельного выполнения потоков

Начнем знакомство непосредственно с использованием технологии OpenMP и рассмотрим в этой заметке некоторые базовые конструкции.

При использовании OpenMP мы добавляем в программу два вида конструкций: функции исполняющей среды OpenMP и специальные директивы #pragma.

Функции

Функции OpenMP носят скорее вспомогательный характер, так как реализация параллельности осуществляется за счет использования директив. Однако в ряде случаев они весьма полезны и даже необходимы. Функции можно разделить на три категории: функции исполняющей среды, функции блокировки/синхронизации и функции работы с таймерами. Все эти функции имеют имена, начинающиеся с omp_, и определены в заголовочном файле omp.h. К рассмотрению функций мы вернемся в следующих заметках.

Директивы

Конструкция #pragma в языке Си/Си++ используется для задания дополнительных указаний компилятору. С помощью этих конструкций можно указать как осуществлять выравнивание данных в структурах, запретить выдавать определенные предупреждения и так далее. Форма записи:

Параллельное программирование на Python

#pragma директивы

Использование специальной ключевой директивы «omp» указывает на то, что команды относятся к OpenMP. Таким образом директивы #pragma для работы с OpenMP имеют следующий формат:

#pragma omp [раздел [ [,] раздел]. ]

Как и любые другие директивы pragma, они игнорируются теми компиляторами, которые не поддерживают данную технологию. При этом программа компилируется без ошибок как последовательная. Это особенность позволяет создавать хорошо переносимый код на базе технологии OpenMP. Код содержащий директивы OpenMP может быть скомпилирован Си/Си++ компилятором, который ничего не знает об этой технологии. Код будет выполнятся как последовательный, но это лучше, чем делать две ветки кода или расставлять множество #ifdef.
OpenMP поддерживает директивы private, parallel, for, section, sections, single, master, critical, flush, ordered и atomic и ряд других, которые определяют механизмы разделения работы или конструкции синхронизации.

Директива parallel

Самой главной можно пожалуй назвать директиву parallel. Она создает параллельный регион для следующего за ней структурированного блока, например:

#pragma omp parallel [другие директивы] структурированный блок

Директива parallel указывает, что структурный блок кода должен быть выполнен параллельно в несколько потоков. Каждый из созданных потоков выполнит одинаковый код содержащийся в блоке, но не одинаковый набор команд. В разных потоках могут выполняться различные ветви или обрабатываться различные данные, что зависит от таких операторов как if-else или использования директив распределения работы.

Чтобы продемонстрировать запуск нескольких потоков, распечатаем в распараллеливаемом блоке текст:

#pragma omp parallel

На 4-х ядерной машине мы можем ожидать увидеть следующей вывод

OpenMP Test OpenMP Test OpenMP Test OpenMP Test

Но на практике я получил следующий вывод:

Многопоточность | Потоки | thread | Многопоточное программирование | Уроки | C++ #1

OpenMP TestOpenMP Test OpenMP Test OpenMP Test

Это объясняется совместным использованием одного ресурса из нескольких потоков. В данном случае мы выводим на одну консоль текст в четырех потоках, которые никак не договариваются между собой о последовательности вывода. Здесь мы наблюдаем возникновение состояния гонки (race condition).

Состояние гонки — ошибка проектирования или реализации многозадачной системы, при которой работа системы зависит от того, в каком порядке выполняются части кода. Эта разновидность ошибки являются наиболее распространенной при параллельном программировании и весьма коварна. Воспроизведение и локализация этой ошибки часто бывает затруднена в силу непостоянства своего проявления (смотри также термин Гейзенбаг).

Директива for

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

void VSqrt(double *src, double *dst, ptrdiff_t n)

Если мы напишем:

#pragma omp parallel

то мы вместо ускорения впустую проделаем массу лишней работы. Мы извлечем корень из всех элементов массива в каждом потоке. Для того, чтобы распараллелить цикл нам необходимо использовать директиву разделения работы «for». Директива #pragma omp for сообщает, что при выполнении цикла for в параллельном регионе итерации цикла должны быть распределены между потоками группы:

#pragma omp parallel

Теперь каждый создаваемый поток будет обрабатывать только отданную ему часть массива. Например, если у нас 8000 элементов, то на машине с четырьмя ядрами работа может быть распределена следующим образом. В первом потоке переменная i принимает значения от 0 до 1999. Во втором от 2000 до 3999. В третьем от 4000 до 5999. В четвертом от 6000 до 7999. Теоретически мы получаем ускорение в 4 раза.

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

Можно использовать сокращенную запись, комбинируя несколько директив в одну управляющую строку. Приведенный выше код будет эквивалентен:

#pragma omp parallel for for (ptrdiff_t i = 0; i < n; i++) dst[i] = sqrt(src[i]);

Директивы private и shared

Относительно параллельных регионов данные могут быть общими (shared) или частными (private). Частные данные принадлежат потоку и могут быть модифицированы только им. Общие данные доступны всем потокам. В рассматриваемом ранее примере массив представлял общие данные. Если переменная объявлена вне параллельного региона, то по умолчанию она считается общей, а если внутри то частной. Предположим, что для вычисления квадратного корня нам необходимо использовать промежуточную переменную value:

double value; #pragma omp parallel for for (ptrdiff_t i = 0; i

В приведенном коде переменная value объявлена вне параллельного региона, задаваемого директивами «#pragma omp parallel for», а значит является общей (shared). В результате переменная value начнет использоваться всеми потоками одновременно, что приведет к ошибке состояния гонки и на выходе мы получим мусор.

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

#pragma omp parallel for for (ptrdiff_t i = 0; i

Второй — воспользоваться директивой private. Теперь каждый поток будет работать со своей переменной value:

double value; #pragma omp parallel for private(value) for (ptrdiff_t i = 0; i

Помимо директивы private, существует директива shared. Но эту директиву обычно не используют, так как и без нее все переменные объявленные вне параллельного региона будут общими. Директиву можно использовать для повышения наглядности кода.

OpenMP и C++.

Последние годы связаны с резким изменением направления развития процессоров — появления многоядерных и многопоточных процессоров.

Последние 10 лет прошли под знаком беспрецедентного роста процессорных ядер.

Накоплен бесценный опыт на многоядерных машинах. Рассмотрим некоторые подходы к ускорению на кластерах.

Первую скрипку играет OpenMP, но он работает на одном узле, т. к. OpenMP использует общую память.

• SendRecv;
• Shmem;
• Односторонние сообщения MPI.

Прилагаются примеры 3-х случаев. Но, для начала рассмотрим, как работает OpenMP.

Реализация многопоточности без лишних усилий.

Среди специалистов, занимающихся параллельными вычислениями, популярна шутка «Параллельные вычисления — технология будущего… и так будет всегда». Эта шутка не теряет актуальность уже несколько десятилетий. Аналогичные настроения были распространены в сообществе разработчиков архитектур компьютеров, обеспокоенном тем, что скоро будет достигнут предел тактовой частоты процессоров, однако частоты процессоров продолжают повышаться, хотя гораздо медленнее, чем раньше. Сплав оптимизма специалистов по параллельным вычислениям и пессимизма архитекторов систем способствовал появлению революционных многоядерных процессоров.

Главные производители процессоров сместили акцент с повышения тактовых частот на реализацию параллелизма в самих процессорах за счет использования многоядерной архитектуры. Идея проста: интегрировать в один процессор более одного ядра. Система, включающая процессор с двумя ядрами, по сути, не отличается от двухпроцессорного компьютера, а система с четырехядерным процессором — от четырехпроцессорного. Этот подход позволяет избежать многих технологических проблем, связанных с повышением тактовых частот, и создавать при этом более производительные процессоры.

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

Подробно описать OpenMP в одной статье просто немыслимо, так как это очень объемный и мощный API. Рассматривайте эту статью как введение, где демонстрируется применение различных средств OpenMP для быстрого написания многопоточных программ. Если вам понадобится дополнительная информация по этой тематике, мы рекомендуем обратиться к спецификации, доступной на сайте OpenMP, — она на удивление легко читается.

Параллельная обработка в OpenMP.

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

Конструкции OpenMP.

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

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

#pragma omp [раздел [ [,] раздел]. ]

OpenMP поддерживает директивы parallel, for, parallel for, section, sections, single, master, critical, flush, ordered и atomic, которые определяют или механизмы разделения работы или конструкции синхронизации. В этой статье мы обсудим большинство директив.

Реализация параллельной обработки.

Хотя директив OpenMP много, все они сразу нам не понадобятся. Самая важная и распространенная директива — parallel. Она создает параллельный регион для следующего за ней структурированного блока, например:

#pragma omp parallel [раздел[ [,] раздел]. ] структурированный блок

Эта директива сообщает компилятору, что структурированный блок кода должен быть выполнен параллельно, в нескольких потоках. Каждый поток будет выполнять один и тот же поток команд, но не один и тот же набор команд — все зависит от операторов, управляющих логикой программы, таких как if-else.

В качестве примера рассмотрим классическую программу «Hello World»:

#pragma omp parallel

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

Hello World Hello World

Тем не менее, результат мог бы оказаться и таким:

HellHell oo WorWlodrl d

Давайте взглянем на более серьезный пример, который определяет средние значения двух соседних элементов массива и записывает результаты в другой массив. В этом примере используется новая для вас OpenMP-конструкция #pragma omp for , которая относится к директивам разделения работы (work- sharing directive). Такие директивы применяются не для параллельного выполнения кода, а для логического распределения группы потоков, чтобы реализовать указанные конструкции управляющей логики. Директива #pragma omp for сообщает, что при выполнении цикла for в параллельном регионе итерации цикла должны быть распределены между потоками группы:

#pragma omp parallel < #pragma omp for for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2; >

Если бы этот код выполнялся на четырехпроцессорном компьютере, а у переменной size было бы значение 100, то выполнение итераций 1—25 могло бы быть поручено первому процессору, 26— 50 — второму, 51—75 — третьему, а 76—99 — четвертому. Это характерно для политики планирования, называемой статической. Политики планирования мы обсудим позднее.

Следует отметить, что в конце параллельного региона выполняется барьерная синхронизация (barrier synchronization). Иначе говоря, достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу.

Так как циклы являются самыми распространенными конструкциями, где выполнение кода можно распараллелить, OpenMP поддерживает сокращенный способ записи комбинации директив #pragma omp parallel и #pragma omp for :

#pragma omp parallel for for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2;

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

for(int i = 1; i

Распараллелить цикл 1 проблематично потому, что для выполнения итерации i нужно знать результат итерации i-1, т. е. итерация i зависит от итерации i-1. Распараллелить цикл 2 тоже проблематично, но по другой причине. В этом цикле вы можете вычислить значение x[i] до x[i-1] , однако, сделав так, вы больше не сможете вычислить значение x[i-1]. Наблюдается зависимость итерации i-1 от итерации i.

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

Общие и частные данные.

Разрабатывая параллельные программы, вы должны понимать, какие данные являются общими (shared), а какие частными (private), — от этого зависит не только производительность, но и корректная работа программы. В OpenMP это различие очевидно, к тому же вы можете настроить его вручную.

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

Директивы pragma для синхронизации.

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

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

Неявная барьерная синхронизация выполняется также в конце каждого блока #pragma omp for , #pragma omp single и #pragma omp sections. Чтобы отключить неявную барьерную синхронизацию в каком-либо из этих трех блоков разделения работы, укажите раздел nowait:

#pragma omp parallel < #pragma omp for nowait for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2; >

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

Второй тип — явная барьерная синхронизация. В некоторых ситуациях ее целесообразно выполнять наряду с неявной. Для этого включите в код директиву #pragma omp barrier.

Подпрограммы исполняющей среды OpenMP.

Помимо уже описанных директив OpenMP поддерживает ряд полезных подпрограмм. Они делятся на три обширных категории: функции исполняющей среды, блокировки/синхронизации и работы с таймерами (последние в этой статье не рассматриваются). Все эти функции имеют имена, начинающиеся с omp_, и определены в заголовочном файле omp.h.

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

Методы синхронизации/блокировки.

OpenMP включает и функции, предназначенные для синхронизации кода. В OpenMP два типа блокировок: простые и вкладываемые (nestable); блокировки обоих типов могут находиться в одном из трех состояний — неинициализированном, заблокированном и разблокированном.

Простые блокировки (omp_lock_t) не могут быть установлены более одного раза, даже тем же потоком. Вкладываемые блокировки (omp_nest_lock_t) идентичны простым с тем исключением, что, когда поток пытается установить уже принадлежащую ему вкладываемую блокировку, он не блокируется. Кроме того, OpenMP ведет учет ссылок на вкладываемые блокировки и следит за тем, сколько раз они были установлены.

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

Когда использовать OpenMP.

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

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

Приложение должно быть кроссплатформенным. OpenMP — кроссплатформенный и широко поддерживаемый API. А так как он реализован на основе директив pragma, приложение можно скомпилировать даже при помощи компилятора, не поддерживающего стандарт OpenMP.

Выполнение циклов нужно распараллелить. Весь свой потенциал OpenMP демонстрирует при организации параллельного выполнения циклов. Если в приложении есть длительные циклы без зависимостей, OpenMP — идеальное решение.

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

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

Простейшая модельная программа.

Рассказывать о составе и назначении программного обеспечения суперкомпьютеров лучше всего на конкретном примере. Выберем модельную программу, спланируем «на бумаге» ее параллельную реализацию, а затем – посмотрим, какого рода программное обеспечение нам потребуется, чтобы выполнить эту параллельную реализацию на суперкомпьютере вообще, и на кластере рабочих станций – в частности.

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

Для упрощения наших модельных рассмотрений исключим из алгоритма вычисление отклонений – будем просто выполнять фиксированное число итераций. Вот текст последовательной (для одного процессора) реализации этой вычислительной процедуры:

#include /***/ #define MX 640 #define MY 480 #define NITER 10000 #define STEPITER 100 static float f[MX][MY]; static float df[MX][MY]; /***/ int main( int argc, char **argv ) < int i, j, n, m; FILE *fp; /***/ printf( «Solving heat conduction task on %d by %d gridn», MX, MY ); fflush( stdout ); /* Initial conditions: */ for ( i = 0; i < MX; i++ ) < for ( j = 0; j < MY; j++ ) < f[i][j] = df[i][j] = 0.0; if ( (i == 0) || (j == 0) ) f[i][j] = 1.0; else if ( (i == (MX-1)) || (j == (MY-1)) ) f[i][j] = 0.5; >> /* Iteration loop: */ for ( n = 0; n < NITER; n++ ) < if ( !(n%STEPITER) ) printf( «Iteration %dn», n ); /* Step of calculation starts here: */ for ( i = 1; i < (MX-1); i++ ) < for ( j = 1; j < (MY-1); j++ ) < df[i][j] = ( f[i][j+1] + f[i][j-1] + f[i-1][j] + f[i+1][j] ) * 0.25 — f[i][j]; >> for ( i = 1; i < (MX-1); i++ ) < for ( j = 1; j < (MY-1); j++ ) < f[i][j] += df[i][j]; >> > /* Calculation is done, F array is a result: */ fp = fopen( «progrev.dat», «w» ); for ( i = 1; i

Примеры.

SendRecv
compile_for_cpu.sh

dimension.h
itstep.cpp
progrev.cpp
run_cpu.sh

Shmem
compile_for_cpu.sh
shmem1.h
dimension.h
itstep.cpp
progrev.cpp
run_cpu.sh Односторонние сообщения MPI
compile_for_cpu.sh

Источник: www.kiam.ru

Учебник по OpenMP

OpenMP — это библиотека для параллельного программирования вычислительных систем с общей памятью (дальше кратко описано что это за системы). Официально поддерживается Си, С++ и Фортран, однако можно найти реализации для некоторых других языков, например Паскаль [1] и Java [2]. Все примеры в этом «учебнике» написаны на С++.

Библиотека активно развивается, в настоящий момент актуальный стандарт версии 4.5 (выпущен в 2015 году), однако уже идет разработка версии 5.0. В тоже время, компилятор Microsoft C++ поддерживает только версию 2.0, а gcc — версию 4.0.

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

Этой библиотеке посвящено множество книг и статей. Наиболее популярными являются книги Антонова [3] и Гергеля [4], мной также был написан ряд статей (поверхностных) по этой теме [5,6], и ряд примеров программ на нашем форуме [7]. На мой взгляд, у этих книг есть ряд недостатков (которые я, конечно, исправляю):

• в книгах стараются описать все возможности OpenMP, значительная часть которых является атавизмом. В старых версия библиотеки это было нужно, но сейчас использование этих возможностей делает ваш код опаснее и повышает порог вхождения (другой программист потратит много времени чтобы разобраться в нем). Я кратко описал некоторые из таких возможностей в заметке «Лишние возможности OpenMP» [8] и в «учебнике» про них ничего нет. За счет этого мой учебник получился короче и не загружает читателя устаревшей информацией;
• в книгах мало «реальных» примеров — поиск минимума/максимума не в счет. Я предлагаю своим читателям обратиться за такими примерами на форум. На форуме можно взять исходный код программ, которые отлажены и работают, при этом к каждой программе прилагается подробный разбор решения и подхода к распараллеливанию. Иногда можно найти несколько реализаций. Примеры будут дополняться.

Вычислительные системы. Идеология OpenMP

Существует множество разновидностей параллельных вычислительных систем — многоядерные/многопроцессорные компьютеры, кластеры, системы на видеокартах, программируемые интегральные схемы и т.д. Библиотека OpenMP подходит только для программирования систем с общей памятью, при этом используется параллелизм потоков. Потоки создаются в рамках единственного процесса и имеют свою собственную память. Кроме того, все потоки имеют доступ к памяти процесса. Схематично это показано на рисунке 1:

Для использования библиотеки OpenMP вам необходимо подключить заголовочный файл «omp.h» , в а также добавить опцию сборки -fopenmp (для компилятора gcc) или установить соответствующий флажок в настройках проекта (для Visual Studio). После запуска программы создается единственный процесс, который начинается выполняться как и обычная последовательная программа. Встретив параллельную область (задаваемую директивой #pragma omp parallel ) процесс порождает ряд потоков (их число можно задать явно, однако по умолчанию будет создано столько потоков, сколько в вашей системе вычислительных ядер). Границы параллельной области выделяются фигурными скобками, в конце области потоки уничтожаются. Схематично этот процесс изображен на рисунке 2:

Черными линиями на рисунке показано время жизни потоков, а красными — их порождение. Видно, что все потоки создаются одним (главным) потоком, который существует все время работы процесса. Такой поток в OpenMP называется master , все остальные потоки многократно создаются и уничтожаются. Стоит отметить, что директивы parallel могут быть вложенными, при этом в зависимости от настроек (изменяются функцией omp_set_nested ) могут создаваться вложенные потоки.

OpenMP может использоваться на кластерной архитектуре, но не самостоятельно, т.к. загрузить весь кластер она не может (для этого нужно создавать процессы, использовать инструменты типа MPI). Однако, если узел кластера многоядерный — то использование OpenMP может существенно поднять эффективность. Такое приложение будет являться «гибридным», в этой статье я не буду вдаваться в тему, тем более что по ней написано много хороших материалов [9].

Синхронизация — критические секции, atomic, barrier

Все переменные, созданные до директивы parallel являются общими для всех потоков. Переменные, созданные внутри потока являются локальными (приватными) и доступны только текущему потоку. При изменении общей переменной одновременно несколькими потоками возникает состояние гонок (мы не можем гарантировать какой-либо конкретный порядок записи и, следовательно, результат) — это проблема и допускать такое нельзя. Такая же проблема возникает когда один поток пытается читать переменную в то время, как другой ее изменяет. Ситуацию поясняет следующий пример:

#include «omp.h» #include int main() < int value = 123; #pragma omp parallel < value++; #pragma omp critical < std::cout > >

Программа описывает переменную value , общую для всех потоков. Каждый поток увеличивает значение переменной, а затем выводит полученное значение на экран. Я запустил ее на двухъядерном компьютере, получил следующие результаты:

Видно, что чаще всего сначала каждый из потоков увеличит значение переменной, а затем они по-очереди выведут результаты (при этом каждый из них еще раз увеличивает значение), но в некоторых случаях порядок выполнения будет другим. Нас же в этом примере сейчас интересует, при попытке одновременного увеличения значения value программа может вести себя как угодно — увеличить только один раз или вовсе завершиться аварийно.

Для решения проблемы существует директива critical , пример ее использования также показан выше. Разделяемым ресурсом в этом примере является не только память (размещенные в ней переменные), но и консоль (в которую потоки выводят результаты). В примере гонки возникают при инкременте переменной, но не при выводе на экран, т.к. операции с cout помещены в критическую секцию. В критической секции в один момент времени может находиться только один поток, остальные ожидают ее освобождения. Правилом хорошего тона считается, если критическая секция содержит обращения только к одному разделяемому ресурсу (в примере секция не только выводит данные на экран, но и выполняет инкремент — это не очень хорошо, в общем случае).

Для ряда операций более эффективно использовать директиву atomic , чем критическую секцию. Она ведет себя также, но работает чуть быстрее. Применять ее можно для операций префиксного/постфиксного инкремента/декремента и операции типа X BINOP = EXPR , где BINOP представляет собой не перегруженный оператор +, *, -, /, . Пример использования такой директивы:

#include «omp.h» #include int main() < int value = 123; #pragma omp parallel < #pragma omp atomic value++; #pragma omp critical (cout) < std::cout > >

Тут же показана возможность именования критических секций — очень рекомендую ей пользоваться всегда. Дело в том, что все безымянные секции рассматриваются как одна (очень большая) и если вы не дадите им явно имена, то только в одной из этих секций в один момент времени будет один поток. Остальные будут ждать. Имя секции должно подсказывать программисту к какому виду ресурса она относится — в приведенном примере таким ресурсом является поток вывода на экран ( cout ).

Несмотря на то, что каждая операция над общими данными в последнем примере размещена в критической секции или является атомарной, в нем есть проблема, т.к. порядок выполнения этих операций по прежнему не определен. Запустив программу раз 20 мне удалось получить на экране не только «125 125» , но и «124 125» . Если мы хотим чтобы сначала каждый поток увеличил значение, а затем они вывели их на экран — можем использовать директиву barrier :

#pragma omp parallel < #pragma omp atomic value++; #pragma omp barrier #pragma omp critical (cout) < std::cout >

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

Разделение задач между потоками

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

Самый популярный способ распределения задач в OpenMP — параллельный цикл. Не секрет, что программы почти всю свою жизнь проводят выполняя циклы, при этом если между итерациями цикла нет зависимостей — то цикл называется векторизуемым (его итерации можно поделить между потоками и выполнить независимо друг от друга). В статье «Библиотека OpenMP. Параллельный цикл» [5] я поверхностно описал эту конструкцию на примерах вычисления суммы элементов массива и численного интегрирования, не буду повторяться — рекомендую вам пройти по ссылке, т.к. дальше описаны более «интересные» аспекты параллельного цикла.

Параллельный цикл позволяет задать опцию schedule , изменяющую алгоритм распределения итераций между потоками. Всего поддерживается 3 таких алгоритма. Далее полагаем, что у нас p потоков выполняют n итераций:

• schedule(static) — статическое планирование. При использовании такой опции итерации цикла будут поровну (приблизительно) поделены между потоками. Нулевой поток получит первые (frac

  ) итераций, первый — вторые и т.д.;

• schedule(static, 10) — блочно-циклическое распределение итераций. Каждый поток получает заданное число итераций в начале цикла, затем (если остались итерации) процедура распределения продолжается. Планирование выполняется один раз, при этом каждый поток «узнает» итерации которые должен выполнить;
• schedule(dinamic), schedule(dynamic, 10) — динамическое планирование. По умолчанию параметр опции равен 1. Каждый поток получает заданное число итераций, выполняет их и запрашивает новую порцию. В отличии от статического планирования, выполняется многократно (во время выполнения программы). Конкретное распределение итераций между потоками зависит от темпов работы потоков и трудоемкости итераций;
• schedule(guided), schedule(guided, 10) — разновидность динамического планирования с изменяемым при каждом последующем распределении числе итераций. Распределение начинается с некоторого начального размера, зависящего от реализации библиотеки до значения, задаваемого в опции (по умолчанию 1). Размер выделяемой порции зависит от количества еще нераспределенных итераций

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

В статье про параллельный цикл также описаны опции nowait и reduction . Первая из них очень редко даст ощутимый выигрыш, а вторую я рекомендую использовать как можно чаще (вместо критических секций). В той статье reduction использовалась во всех примерах и за счет этого удалось избежать явного использования критических секций, однако это удается не всегда и поэтому стоит знать что у нее внутри. Итак, параллельно вычислить сумму элементов массива можно так:

int sum_arr(int *a, const int n) < int sum = 0; #pragma omp parallel reduction (+: sum) < #pragma omp for for (int i = 0; i < n; ++i) sum += a[i]; >return sum; >

Выглядит это красиво, но на самом деле в каждом потоке создается локальная переменная для хранения суммы части массива (вычисление которой назначено текущему потоку), ей присваивается значение 0 (т.к. редукция с оператором + ). Каждый поток вычисляет сумму, но необходимо ведь сложить все эти значение чтобы получить окончательный результат? — Делается это с помощью критической секции или атомарной операции примерно следующим образом:

int sum_arr(int *a, const int n) < int sum = 0; #pragma omp parallel < int local_sum = 0; #pragma omp for for (int i = 0; i < n; ++i) local_sum += a[i]; #pragma omp atomic sum += local_sum; >return sum; >

Такой подход используется постоянно, поэтому я рекомендую внимательно рассмотреть этот код. Чуть более сложным примером является параллельный поиск максимума/минимума [9]. В качестве задачи для проверки усвоения материала предлагаю попробовать построить гистограмму (например для изображения).

Параллельные задачи (parallel tasks)

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

Получится вложенный параллелизм. Если (теоретически) наш код запущен на 8 ядрах — то фактически будет создано 64 потока. Ну а если кому-нибудь придет в голову идея делать параллельно еще что-нибудь?

Иногда такую ситуацию нелегко обнаружить, например, на нашем форуме можно найти параллельную реализацию решения СЛАУ методом Крамера, при этом параллельно вычисляется n определителей. Функция вычисления определителя вызывает функцию сведения матрицы к треугольному виду, которая может быть распараллелена.

Проблема параллельного цикла в том, что число создаваемых потоков зависит от того какие функции распараллелены и как они друга друга вызывают. Очень сложно все это отслеживать и, тем более, поддерживать. Решение проблемы — параллельные задачи, которые не создают поток, а лишь выполняют добавление задачи в очередь, освободившийся поток выбирает задачу из пула. Я описывал этот механизм в статье
«Параллельные задачи (tasks) OpenMP» и не буду повторяться (рекомендую прочитать материал по ссылке — в статье рассматривается возможность распараллеливания рекурсивных функций с помощью механизма задач). Отмечу лишь то, что в параллельные задачи были предложены в стандарте OpenMP 3.0 (в 2008 году) поэтому их поддержка отсутствует в Microsoft C++. Кроме того, в свежем стандарте OpenMP 4.5 была предложена конструкция taskloop , за счет которой использовать параллельные задачи для распараллеливания циклов теперь также удобно как и параллельный цикл.

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

Механизм параллельных секций видится мне достаточно низкоуровневым. Тем не менее, он полезен в ряде случаев. Как было отмечено выше, параллельный цикл можно применять только в случаях, если итерации цикла не зависят друг от друга, т.е. тут нельзя:

for (int i = 1; i < n; ++i) a[i] = a[i-1]+1;

Если же у нас в программе появляется несколько фрагментов, не зависящих друг от друга, но имеющий зависимости внутри себя — то их распараллеливают с помощью механизма параллельных секций:

#pragma omp parallel < #pragma omp sections < #pragma omp section < for (int i = 1; i < n; ++i) a[i] = a[i-1]+1; >#pragma omp section < for (int i = 1; i < n; ++i) b[i] = b[i-1]+1; >> >

Пример не самый лучший, т.к. я до сих пор не встречал реальной задачи где это нужно. Очень важно — не пытайтесь распараллелить рекурсивные функции с помощью секций (используйте для этого задачи). Возможно в будущем (особенно если Microsoft реализует стандарт OpenMP 3.0) я перемещу этот раздел в Лишние возможности OpenMP.

Заключение и дополнительная литература

Тут учебнику конец… Если хотите посмотреть больше примеров исходников с OpenMP или у вас есть вопросы по решению конкретных задач — загляните на наш форум. Если же у вас возникли вопросы по тексту статьи — пишите в комментариях.

1. Поддержка OpenMP в Lazarus/Freepascal: https://wiki.lazarus.freepascal.org/OpenMP_support
2. OpenMP для Java:
3. Антонов А.С. Технологии параллельного программирования MPI и OpenMP: Учеб. пособие. Предисл.: В.А.Садовничий. – М.: Издательство Московского университета, 2012.-344 с.-(Серия “Суперкомпьютерное образование”). ISBN 978-5-211-06343-3.
4. Гергель В.П. Высокопроизводительные вычисления дл многоядерных многопроцессорных систем. Учебное пособие – Нижний Новгород; Изд-во ННГУ им. Н.И.Лобачевского, 2010
5. Библиотека OpenMP. Параллельный цикл: https://pro-prof.com/archives/1150
6. Параллельные задачи (tasks) OpenMP: Параллельные задачи (tasks) OpenMP
7. Форум по программированию с использованием OpenMP: https://pro-prof.com/forums/forum/software-engineering/parallel_programming/openmp_library
8. Лишние возможности OpenMP: href=»https://pro-prof.com/forums/topic/openmp-problems
9. Распараллеливание алгоритма триангуляции матрицы с OpenMP: https://pro-prof.com/forums/topic/matrix-triangulation_cplusplus
10. Профилировка гибридных кластерных приложений MPI+OpenMP: https://habr.com/en/company/intel/blog/266409/
11. OpenMP – Распараллеливание метода Крамера решения СЛАУ: https://pro-prof.com/forums/topic/openmp-cramer-method_cplusplus
12. 32 подводных камня OpenMP при программировании на Си++: https://www.viva64.com/ru/a/0054/
13. OpenMP и статический анализ кода: https://www.viva64.com/ru/a/0055/

Источник: pro-prof.com