Учебник по OpenMP
Опубликовано: 01.09.2018
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:
рис. 1 модель памяти в OpenMP
Для использования библиотеки OpenMP вам необходимо подключить заголовочный файл "omp.h", в а также добавить опцию сборки -fopenmp (для компилятора gcc) или установить соответствующий флажок в настройках проекта (для Visual Studio). После запуска программы создается единственный процесс, который начинается выполняться как и обычная последовательная программа. Встретив параллельную область (задаваемую директивой #pragma omp parallel) процесс порождает ряд потоков (их число можно задать явно, однако по умолчанию будет создано столько потоков, сколько в вашей системе вычислительных ядер). Границы параллельной области выделяются фигурными скобками, в конце области потоки уничтожаются. Схематично этот процесс изображен на рисунке 2:
рис.2 директива omp parallel
Черными линиями на рисунке показано время жизни потоков, а красными — их порождение. Видно, что все потоки создаются одним (главным) потоком, который существует все время работы процесса. Такой поток в OpenMP называется master, все остальные потоки многократно создаются и уничтожаются. Стоит отметить, что директивы parallel могут быть вложенными, при этом в зависимости от настроек (изменяются функцией omp_set_nested) могут создаваться вложенные потоки.
OpenMP может использоваться на кластерной архитектуре, но не самостоятельно, т.к. загрузить весь кластер она не может (для этого нужно создавать процессы, использовать инструменты типа MPI ). Однако, если узел кластера многоядерный — то использование OpenMP может существенно поднять эффективность. Такое приложение будет являться «гибридным», в этой статье я не буду вдаваться в тему, тем более что по ней написано много хороших материалов [9].
Синхронизация — критические секции, atomic, barrier
Все переменные, созданные до директивы parallel являются общими для всех потоков. Переменные, созданные внутри потока являются локальными (приватными) и доступны только текущему потоку. При изменении общей переменной одновременно несколькими потоками возникает состояние гонок (мы не можем гарантировать какой-либо конкретный порядок записи и, следовательно, результат) — это проблема и допускать такое нельзя. Такая же проблема возникает когда один поток пытается читать переменную в то время, как другой ее изменяет. Ситуацию поясняет следующий пример:
#include "omp.h" #include <iostream> int main() { int value = 123; #pragma omp parallel { value++; #pragma omp critical { std::cout << value++ << std::endl; } } }Программа описывает переменную value, общую для всех потоков. Каждый поток увеличивает значение переменной, а затем выводит полученное значение на экран. Я запустил ее на двухъядерном компьютере, получил следующие результаты:
Проблема гонки потоков OpenMP
Видно, что чаще всего сначала каждый из потоков увеличит значение переменной, а затем они по-очереди выведут результаты (при этом каждый из них еще раз увеличивает значение), но в некоторых случаях порядок выполнения будет другим. Нас же в этом примере сейчас интересует, при попытке одновременного увеличения значения value программа может вести себя как угодно — увеличить только один раз или вовсе завершиться аварийно.
Для решения проблемы существует директива critical, пример ее использования также показан выше. Разделяемым ресурсом в этом примере является не только память (размещенные в ней переменные), но и консоль (в которую потоки выводят результаты). В примере гонки возникают при инкременте переменной, но не при выводе на экран, т.к. операции с cout помещены в критическую секцию. В критической секции в один момент времени может находиться только один поток, остальные ожидают ее освобождения. Правилом хорошего тона считается, если критическая секция содержит обращения только к одному разделяемому ресурсу (в примере секция не только выводит данные на экран, но и выполняет инкремент — это не очень хорошо, в общем случае).
Для ряда операций более эффективно использовать директиву atomic, чем критическую секцию. Она ведет себя также, но работает чуть быстрее. Применять ее можно для операций префиксного/постфиксного инкремента/декремента и операции типа X BINOP = EXPR, где BINOP представляет собой не перегруженный оператор +, *, -, /, &, ^, |, <<, >>. Пример использования такой директивы:
#include "omp.h" #include <iostream> int main() { int value = 123; #pragma omp parallel { #pragma omp atomic value++; #pragma omp critical (cout) { std::cout << value << std::endl; } } }Тут же показана возможность именования критических секций — очень рекомендую ей пользоваться всегда. Дело в том, что все безымянные секции рассматриваются как одна (очень большая) и если вы не дадите им явно имена, то только в одной из этих секций в один момент времени будет один поток. Остальные будут ждать. Имя секции должно подсказывать программисту к какому виду ресурса она относится — в приведенном примере таким ресурсом является поток вывода на экран (cout).
Несмотря на то, что каждая операция над общими данными в последнем примере размещена в критической секции или является атомарной, в нем есть проблема, т.к. порядок выполнения этих операций по прежнему не определен. Запустив программу раз 20 мне удалось получить на экране не только "125 125", но и "124 125". Если мы хотим чтобы сначала каждый поток увеличил значение, а затем они вывели их на экран — можем использовать директиву barrier:
#pragma omp parallel { #pragma omp atomic value++; #pragma omp barrier #pragma omp critical (cout) { std::cout << value << std::endl; } }Поток, завершив свою часть вычислений доходит до директивы barrier и ждет пока все потоки дойдут до этой же точки. Дождавшись последнего, потоки продолжают выполнение. Теперь в программе нет никаких проблем с синхронизацией, но обратите внимание, что все потоки выполняют одну и туже работу (описанную внутри параллельной области), пусть и параллельно. При таком раскладе программа не начнет работать быстрее, нам необходимо распределить между потоками решаемые задачи , сделать это можно различными способами…
Разделение задач между потоками
Параллельный цикл
Самый популярный способ распределения задач в OpenMP — параллельный цикл. Не секрет, что программы почти всю свою жизнь проводят выполняя циклы, при этом если между итерациями цикла нет зависимостей — то цикл называется векторизуемым (его итерации можно поделить между потоками и выполнить независимо друг от друга). В статье « Библиотека OpenMP. Параллельный цикл » [5] я поверхностно описал эту конструкцию на примерах вычисления суммы элементов массива и численного интегрирования, не буду повторяться — рекомендую вам пройти по ссылке, т.к. дальше описаны более «интересные» аспекты параллельного цикла.
Параллельный цикл позволяет задать опцию schedule, изменяющую алгоритм распределения итераций между потоками. Всего поддерживается 3 таких алгоритма. Далее полагаем, что у нас p потоков выполняют n итераций:
Опции планирования:
schedule(static) — статическое планирование. При использовании такой опции итерации цикла будут поровну (приблизительно) поделены между потоками. Нулевой поток получит первые \(\frac{n}{p}\) итераций, первый — вторые и т.д.; 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 или у вас есть вопросы по решению конкретных задач — загляните на наш форум. Если же у вас возникли вопросы по тексту статьи — пишите в комментариях.