Параллельный цикл с уменьшением и манипуляцией массивами

Question

Я новичок в openMP, и я стараюсь оптимизировать цикл. Результат не так, как ожидалось, петли for работают неправильно (из-за зависимости). Я не понимаю, как получить идеальный параллельный цикл с примерами ниже:

#pragma omp parallel for default(shared) reduction(+...) 
    for(i = rest - 1; i >= 0; i--) { 
     scounts[i] += N; 
    } 

    #pragma omp parallel for private(i) 
    for(i = 1; i < p; i++) { 
     disp[i] = disp[i-1] + scounts[i-1]; 
    } 

Я попробовал эти 2 директивы Pragma без Succes. Каков наилучший способ действовать в этих случаях?

Answer 1

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

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

type sum = 0; //replace type with int, float, double... 
for(i = 1; i < p; i++) { 
    sum += scounts[i-1]; 
    disp[i] = disp[0] + sum; 
} 

Это совокупная сумма (ака prefix sum). OpenMP не предоставляет простые конструкции для выполнения суммы префикса. Вы должны сделать это за два прохода. Вот как вы это делаете (я предположил, тип disp и scounts является int, но вы можете заменить его float или любой другой):

int *suma; 
#pragma omp parallel 
{ 
    int ithread = omp_get_thread_num(); 
    int nthreads = omp_get_num_threads(); 
    #pragma omp single 
    { 
     suma = malloc(nthreads * sizeof *suma); 
     suma[0] = 0; 
    } 
    int sum = 0; 
    #pragma omp for schedule(static) 
    for (int i=1; i<p; i++) { 
     sum += scounts[i-1]; 
     disp[i] = disp[0] + sum; 
    } 
    suma[omp_get_thread_num()+1] = sum; 
    #pragma omp barrier 
    int offset = 0; 
    for(int i=0; i<(ithread+1); i++) { 
     offset += suma[i]; 
    } 
    #pragma omp for schedule(static) 
    for(int i=1; i<p; i++) { 
     disp[i] += offset; 
    } 
} 
free(suma); 

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

Answer 2

Пожалуйста, используйте #pragma непосредственно:

#pragma omp parallel ... 

вместо #pragma в комментарии:

// #pragma omp parallel ...