#c #openmp #parallel-processing
#c #openmp #параллельная обработка
Вопрос:
РЕШАЕМАЯ: смотрите РЕДАКТИРОВАНИЕ 2 ниже
Я пытаюсь распараллелить алгоритм, который выполняет некоторую операцию над матрицей (давайте для простоты назовем это размытием). Как только эта операция выполнена, она обнаруживает наибольшее изменение между старой и новой матрицей (максимальная абсолютная разница между старой и новой матрицей на элементной основе). Если эта максимальная разница превышает некоторый порог, то выполните еще одну итерацию операции с матрицей.
Итак, моя основная программа имеет следующий цикл:
converged = 0;
for( i = 1; i <= iteration_limit; i ){
max_diff = update( amp;data_grid );
if( max_diff < tol ) {
converged = 1;
break;
}
}
update( amp;data_grid ) затем вызывает фактическую реализацию алгоритма размытия. Затем алгоритм размытия выполняет итерацию по матрице, именно этот цикл я пытаюсь распараллелить:
for( i = 0; i < width; i ) {
for( j = 0; j <= height; j ) {
g->data[ update ][ i ][ j ] =
ONE_QUARTER * (
g->data[ update ][ i 1 ][ j ]
g->data[ update ][ i - 1 ][ j ]
g->data[ update ][ i ][ j 1 ]
g->data[ update ][ i ][ j - 1 ]
);
diff = fabs( g->data[ old ][ i ][ j ] - g->data[ update ][ i ][ j ] );
maxdiff = maxdiff > diff ? maxdiff : diff;
}
}
Я мог бы просто вставить параллельную область внутрь update(amp;data_grid) но это означало бы, что потоки будут создаваться и уничтожаться на каждой итерации, чего я пытаюсь избежать.:
#pragma omp parallel for private(i, j, diff, maxdg) shared(width, height, update, g, dg, chunksize) default(none) schedule(static, chunksize)
У меня есть 2 копии сетки, и я записываю новый ответ в «другой» на каждой итерации, переключая old и update между 0 и 1 .
Редактировать:
Итак, я создал цикл orphaned omp for в соответствии с предложением Джонатана Дурси, но по какой-то причине, похоже, не могу найти максимальное значение между потоками…
Вот мой «внешний» код:
converged = 0;
#pragma omp parallel shared(i, max_iter, g, tol, maxdg, dg) private(converged) default(none)
{
for( i = 1; i <= 40; i ){
maxdg = 0;
dg = grid_update( amp;g );
printf("[%d] dg from a single thread: %fn", omp_get_thread_num(), dg );
#pragma omp critical
{
if (dg > maxdg) maxdg = dg;
}
#pragma omp barrier
#pragma omp flush
printf("[%d] maxdg: %fn", omp_get_thread_num(), maxdg);
if( maxdg < tol ) {
converged = 1;
break;
}
}
}
И результат:
[11] dg from a single thread: 0.000000
[3] dg from a single thread: 0.000000
[4] dg from a single thread: 0.000000
[5] dg from a single thread: 0.000000
[0] dg from a single thread: 0.166667
[6] dg from a single thread: 0.000000
[7] dg from a single thread: 0.000000
[8] dg from a single thread: 0.000000
[9] dg from a single thread: 0.000000
[15] dg from a single thread: 0.000000
[10] dg from a single thread: 0.000000
[1] dg from a single thread: 0.166667
[12] dg from a single thread: 0.000000
[13] dg from a single thread: 0.000000
[14] dg from a single thread: 0.000000
[2] maxdg: 0.000000
[3] maxdg: 0.000000
[0] maxdg: 0.000000
[8] maxdg: 0.000000
[9] maxdg: 0.000000
[4] maxdg: 0.000000
[5] maxdg: 0.000000
[6] maxdg: 0.000000
[7] maxdg: 0.000000
[1] maxdg: 0.000000
[14] maxdg: 0.000000
[11] maxdg: 0.000000
[15] maxdg: 0.000000
[10] maxdg: 0.000000
[12] maxdg: 0.000000
[13] maxdg: 0.000000
ПРАВКА 2:
Допустил несколько ошибок с частными / общими классификаторами и забыл о барьере. Это правильный код:
#pragma omp parallel shared(max_iter, g, tol, maxdg) private(i, dg, converged) default(none)
{
for( i = 1; i <= max_iter; i ){
#pragma omp barrier
maxdg=0;
/*#pragma omp flush */
dg = grid_update( amp;g );
#pragma omp critical
{
if (dg > maxdg) maxdg = dg;
}
#pragma omp barrier
/*#pragma omp flush*/
if( maxdg < tol ) {
converged = 1;
break;
}
}
}
Комментарии:
1. Вы уверены, что ваша реализация OMP действительно уничтожает потоки после параллельной области? Обычно я ожидаю, что он использует threadpool, чтобы избежать этого.
2. Насколько я могу понять, это так, в любом случае, однако я хотел бы знать, как применить потерянные директивы к этой ситуации.
3. Большинство реализаций фактически используют пул потоков, чтобы уменьшить накладные расходы на уничтожение и повторное получение потоков для каждой новой параллельной области. Тем не менее, каждый раз, когда вы входите в параллельную область, все еще возникает изрядная нагрузка — хотя первая область обычно будет самой дорогой (поскольку она создает потоки). Обратите внимание — что это зависит от реализации относительно того, когда потоки действительно впервые получены — это может быть до того, как пользовательский код получит управление, или первая параллельная область, или …
Ответ №1:
Нет проблем с запуском параллельной секции в другой процедуре перед for, конечно, начиная с OpenMP 3.0 (2008) и, возможно, начиная с OpenMP 2.5. С gcc4.4:
outer.c:
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
void update(int n, int iter);
int main(int argc, char **argv) {
int n=10;
#pragma omp parallel num_threads(4) default(none) shared(n)
for (int iter=0; iter<3; iter )
{
#pragma omp single
printf("---iteration %d---n", iter);
update(n, iter);
}
return 0;
}
inner.c:
#include <omp.h>
#include <stdio.h>
void update(int n, int iter) {
int thread = omp_get_thread_num();
#pragma omp for
for (int i=0;i<n;i ) {
int newthread=omp_get_thread_num();
printf("=: doing loop index %d.n",newthread,i);
}
}
Построение:
$ make
gcc44 -g -fopenmp -std=c99 -c -o inner.o inner.c
gcc44 -g -fopenmp -std=c99 -c -o outer.o outer.c
gcc44 -o main outer.o inner.o -fopenmp -lgomp
$ ./main
---iteration 0---
2: doing loop index 6.
2: doing loop index 7.
2: doing loop index 8.
0: doing loop index 0.
0: doing loop index 1.
0: doing loop index 2.
1: doing loop index 3.
1: doing loop index 4.
1: doing loop index 5.
3: doing loop index 9.
---iteration 1---
0: doing loop index 0.
0: doing loop index 1.
0: doing loop index 2.
1: doing loop index 3.
1: doing loop index 4.
1: doing loop index 5.
3: doing loop index 9.
2: doing loop index 6.
2: doing loop index 7.
2: doing loop index 8.
---iteration 2---
0: doing loop index 0.
0: doing loop index 1.
0: doing loop index 2.
3: doing loop index 9.
2: doing loop index 6.
2: doing loop index 7.
2: doing loop index 8.
1: doing loop index 3.
1: doing loop index 4.
1: doing loop index 5.
Но, согласно @jdv-Яну де Ваану, я был бы очень удивлен, если бы в современной реализации OpenMP это привело к значительному повышению производительности по сравнению с параллельным обновлением for, особенно если обновление достаточно дорогое.
Кстати, есть проблемы с простым размещением параллельного for вокруг i-цикла в подпрограмме Гаусса-Зайделя в обновлении; вы можете видеть, что шаги i не являются независимыми, и это приведет к условиям гонки. Вместо этого вам нужно будет сделать что-то вроде Red-Black или итерации Jacobi…
Обновить:
Приведенный пример кода предназначен для итерации G-S, а не Jacobi, но я просто предположу, что это опечатка.
Если ваш вопрос на самом деле касается сокращения, а не осиротевшего цикла for: да, вам, к сожалению, приходится выполнять собственные сокращения min / max в OpenMP, но это довольно просто, вы просто используете обычные приемы.
Обновление 2 — блин, locmax должен быть приватным, а не общим.
outer.c:
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
int update(int n, int iter);
int main(int argc, char **argv) {
int n=10;
int max, locmax;
max = -999;
#pragma omp parallel num_threads(4) default(none) shared(n, max) private(locmax)
for (int iter=0; iter<3; iter )
{
#pragma omp single
printf("---iteration %d---n", iter);
locmax = update(n, iter);
#pragma omp critical
{
if (locmax > max) max=locmax;
}
#pragma omp barrier
#pragma omp flush
#pragma omp single
printf("---iteration %d's max value = %d---n", iter, max);
}
return 0;
}
inner.c:
#include <omp.h>
#include <stdio.h>
int update(int n, int iter) {
int thread = omp_get_thread_num();
int max = -999;
#pragma omp for
for (int i=0;i<n;i ) {
printf("=: doing loop index %d.n",thread,i);
if (i iter>max) max = i iter;
}
return max;
}
и построение:
$ make
gcc44 -g -fopenmp -std=c99 -c -o inner.o inner.c
gcc44 -g -fopenmp -std=c99 -c -o outer.o outer.c
gcc44 -o main outer.o inner.o -fopenmp -lgomp
bash-3.2$ ./main
---iteration 0---
0: doing loop index 0.
0: doing loop index 1.
0: doing loop index 2.
2: doing loop index 6.
2: doing loop index 7.
2: doing loop index 8.
1: doing loop index 3.
1: doing loop index 4.
1: doing loop index 5.
3: doing loop index 9.
---iteration 0's max value = 9---
---iteration 1---
0: doing loop index 0.
0: doing loop index 1.
0: doing loop index 2.
3: doing loop index 9.
2: doing loop index 6.
2: doing loop index 7.
2: doing loop index 8.
1: doing loop index 3.
1: doing loop index 4.
1: doing loop index 5.
---iteration 1's max value = 10---
---iteration 2---
0: doing loop index 0.
0: doing loop index 1.
0: doing loop index 2.
1: doing loop index 3.
1: doing loop index 4.
1: doing loop index 5.
3: doing loop index 9.
2: doing loop index 6.
2: doing loop index 7.
2: doing loop index 8.
---iteration 2's max value = 11---
Комментарии:
1. На самом деле я использую итерацию Jacobi, моя главная проблема в том, как мне найти максимальную разницу между всеми различными потоками в итерации? Я использую C, поэтому, к сожалению, не могу использовать reduce.
2. @Jonathan — Я не верю, что вам нужно указывать оба -fopenmp и -lgomp в последней строке. Опция -fopenmp выполняет несколько действий, включая добавление -lgomp в команду ld, вызывающую проблемы gcc.
3. Скоро будут сокращены минимальные и максимальные значения для C / C — в ближайшей к вам реализации OpenMP версии V3.1. Между тем, не так сложно «создать свой собственный». Здесь есть несколько обсуждений о них в stackoverflow и на openmp.org/forum .
4. @Jonathan Я последовал вашим предложениям, но по какой-то причине все еще не могу найти максимальное значение. Я просто туплю?
5. Вероятно, нет, но вам придется быть более конкретным, чем это. Что не работает? Вы получаете только локальный максимум?