Распараллеливание циклов в openmp

Содержание

1 1 Вычисление суммы элементов массива
2 2 Вычисление интеграла методом прямоугольников
- 2.1 2.1 Задано количество прямоугольников
- 2.2 2.2 Задана точность интегрирования

OpenMP — библиотека для языков программирования Fortran, C, C++, позволяющая запускать параллельно участки кода на многопроцессорных системах или процессорах с HyperThreading. Встроена в компилятор gcc начиная с версии 4.2. Разрабатывается при активном участии Intel, за что им большое спасибо.

Несколько правил по активации данного режима:

Распараллеливание можно ввести на участок программы, то есть определённый блок будет выполняться несколько раз (задаётся пользователем) или для циклов for. На первом случае мы останавливаться не будем, об этом можно прочитать в презентации OpenMP_talk, затронем лишь распараллеливание циклов.

В данном примере цикл for будет выполнятся в два потока, при этом нельзя заранее определить в какой последовательности значений переменной i будет происходит выполнение тела цикла. Таким образом, необходимо избавится от зависимости от предыдущего шага.

Например, если у вас есть такой цикл:

То его нужно преобразовать к виду:

Очень часто встречается такой случай:

Переменная ave накапливает значения и зависит от итерации. Если вы запустите программу в параллельном режиме, то можете получать различные ответы. Как я понимаю, дело в том, что чтобы прибавить к переменной ave значение A[i], из памяти в регистр процессора копируется значение ave, суммируется, а затем новое значение записывается в участок памяти этой переменной. В промежутке между считыванием и записью другой процесс может записать новое суммированное значение, которое потом будет потеряно и не учтено.

Учёт такого случая называется reduction и объявляется следующим образом для переменных:

После чего для каждой переменной list создаётся локальная копия и инициализируется согласно операции op — +, *, — (странно, а / нет) 0, 1, 0 соответственно. После вычисления эта локальная копия комбинируется с глобальной переменной.

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

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

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

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

Статья ориентирована на тех, кто не знаком с библиотекой OpenMP, но хотел бы познакомиться.

OpenMP — не просто библиотека параллельного программирования, но и стандарт, официально поддерживаемый для языков Си, C++ и Fortran (а неофициально и для других языков, Free Pascal, например [1]). Работает OpenMP только на архитектурах с общей памятью.

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

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

В статье рассмотрены:

Все примеры статьи написаны на С++, использовался компилятор gcc (но можно использовать и другие, отличаться будут только ключи, передаваемые компилятору). Для поддержки OpenMP, gcc должен принять ключ -fopenmp.

1 Вычисление суммы элементов массива

Как отмечалось выше, OpenMP позволяет распараллеливать нашу программу постепенно, а сначала можно написать последовательную программу и отладить, что мы и сделали:

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

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

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

Поток может использовать как локальные переменные, так и разделяемые. Разделяемые переменные (shared) являются общими для всех потоков, очевидно, с ними надо очень осторожно работать (если хоть один поток изменяет значение такой переменной — все остальные должны ждать — это можно организовать средствами OMP). Все константы являются разделяемыми — в нашем примере, разделяемыми являются переменные «a» и «n».

Поток может содержать набор локальных переменных (опции private и firstprivate), для которых порождаются копии в каждом потоке. Для переменных, объявленных в списке private начальное значение не определено, для firstprivate — берется из главного потока. Все переменные, объявленные внутри параллельной области являются локальными (переменная «i» в нашем примере).

Опция reduction, также, задает локальную переменную (sum), а также, операцию, которая будет выполнена над локальными переменными при выходе из параллельной области («+»). Начальное значение локальных переменных, в этом случае, определяется типом операции (для аддитивных операций — ноль, для мультипликативных — единица).

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

Директива for имеет множество опций, подробнее про которые можно прочитать в толстых учебниках. Внутри цикла можно задать опции private и firstprivate, но кроме того, ряд новых. Например schedule определяет способ распределения итераций между потоками, а nowait — убирает неявную барьерную синхронизацию, которая по умолчанию стоит в конце цикла.

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

рис. 1 распараллеливание OMP

Сумма элементов массива считается очень быстро, поэтому чтобы получить результаты, показанные на рисунке, пришлось запустить нашу функцию 10 раз. Большую часть времени работы программы занимает заполнение массива случайными числами, которое выполняется в одном потоке (из за этого результаты чуть смазаны). Однако, не ленивый читатель может без труда распараллелить заполнение массива :).

2 Вычисление интеграла методом прямоугольников

2.1 Задано количество прямоугольников

В статье используется метод левых прямоугольников, суть которого, сводится к тому, что область между графиком интегрируемой функции и осью абсцисс разбивается на заданное количество прямоугольников. Для каждого прямоугольника вычисляется площадь, сумма площадей — и есть результат. Термин «левые прямоугольники» означает, что левый верхний угол каждого прямоугольника лежит непосредственно на интегрируемой функции.

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

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

рис. 2 деградация точности при большом количестве прямоугольников

В качестве аргумента программа на рис. 2 принимает количество прямоугольников, интегрируется функция x * x на интервале [-1, 1], точное значение интеграла 2/3. Чем больше прямоугольников на ограниченном интервале — тем меньше каждый прямоугольник, следовательно, прямоугольники «плотнее прилегают к графику» и точность должна расти. Точность действительно повышается, мы видим это при увеличении количества прямоугольников с 10 до 100, однако, при очень большом их количестве точность резко падает. OpenMP тут оказывается и не причем (обратите внимание, при компиляции не использовался ключ -fopenmp).

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

OpenMP тут вроде бы и не причем, но оказывается так, что на точность может влиять количество работающих потоков и порядок вычисления. Читатель может убедиться в этом, например последовательно вычислив сумму ряда 1/(x * x) сначала при изменении x от 1 до 100000000, а затем, в обратном порядке. Результаты вычислений будут отличаться, и вычисление в обратном порядке дает более точный результат (если не понятно почему и очень интересно — сообщите, я напишу статью по этой теме). OpenMP не гарантирует определенный порядок вычислений, поэтому и может появляться неожиданная погрешность, на это многократно указывается в некоторых источниках [2].

2.2 Задана точность интегрирования

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

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

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

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

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

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

Для использования OpenMP в этом примере достаточно определить заранее количество итераций внутреннего цикла и использовать в нем целочисленный счетчик:

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

В OpenMP имеется множество других полезных инструментов распараллеливания, таких как задачи (tasks), параллельные секции (sections), различные средства синхронизации. Все это не затронуто в статье (но может быть восполнено [2, 3, 4, 5]), т.к. ее целью ставилось показать читателю хоть какой-то пример того, как можно распараллелить свою программу средствами OpenMP. В следующих статьях, возможно, я опишу какие-нибудь другие части этой полезной библиотеки (не забудьте подписаться на рассылку).

# include omp.h >

# include stdio.h >

# include iostream >

# include iomanip >

# include time.h >

void matrixmult ( int **m1, int m1_row, int m1_col, int **m2, int m2_row, int m2_col, int **m3, int m3_row, int m3_col);

void matrixfill ( int **m, int row, int col)

for ( int i = 0 ; i for ( int j = 0 ; j " Enter [ " " ][ " " ] element: " ;

std::cin >> m[i][j];

void print_matr ( int **m, int row, int col)

for ( int i = 0 ; i for ( int j = 0 ; j std::setw ( 3 ) ‘ ‘ ;

std::cout int main ()

int row1 = 0 ;

int col1 = 0 ;

clock_t start, stop;

std::cout " Enter number of rows of the first matrix: " ;

std::cin >> row1;

std::cout " Enter number of columns of the first matrix: " ;

std::cin >> col1;

int **arr1 = new int *[row1];

for ( int i = 0 ; i new int [col1];

matrixfill (arr1, row1, col1);

int row2 = 0 ;

int col2 = 0 ;

std::cout " Enter number of rows of the second matrix: " ;

std::cin >> row2;

std::cout " Enter number of columns of the second matrix: " ;

std::cin >> col2;

int **arr2 = new int *[row2];

for ( int i = 0 ; i new int [col2];

matrixfill (arr2, row2, col2);

int row3 = row1;

int col3 = col2;

int **arr3 = new int *[row3];

for ( int i = 0 ; i new int [col3];

for ( int i = 0 ; i for ( int j = 0 ; j 0 ;

std::cout "
First matrix:
" ;

print_matr (arr1, row1, col1);

std::cout "
Second matrix:
" ;

print_matr (arr2, row2, col2);

start = clock ();

// если число столбцов первой матрицы равно числу строк второй матрицы

if (col1 == row2)

matrixmult (arr1, row1, col1, arr2, row2, col2, arr3, row3, col3);

else

std::cerr " Error! " return 1 ;

std::cout "
Result matrix: " print_matr (arr3, row3, col3);

for ( int i = 0 ; i delete[] arr1[i];

delete[] arr1;

for ( int i = 0 ; i delete[] arr2[i];

delete[] arr2;

for ( int i = 0 ; i delete[] arr3[i];

delete[] arr3;

stop = clock ();

printf ( " Time=%f sec.
" ,(( double )(stop-start)/ 1000.0 ));

return 0 ;

void matrixmult ( int **m1, int m1_row, int m1_col, int **m2, int m2_row, int m2_col, int **m3, int m3_row, int m3_col)

omp_set_num_threads ( 12 );

int temp = 0 ;

int i= 0 , j= 0 , k= 0 ;

# pragma omp parallel

int num = omp_get_thread_num ();

# pragma omp parallel for schedule(static) private(k)

for ( k = 0 ; k pragma omp parallel for schedule(static) private(i)

for ( i = 0 ; i pragma omp parallel for schedule(static) shared(m1, m2, m3) private(j) reduction(+:temp)

for ( j = 0 ; j // printf("[%d]: m[%d][%d] += m1[%d][%d] * m2[%d][%d] = %d * %d = %d
", num, i, k, i, j, j, k, m1[i][j], m2[j][k], m3[i][k]);

Terms
Privacy
Security
Status
Help

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.