Простая прикладная программа OpenMP на основе задач

Question

Следующая небольшая программа (online version) пытается вычислить площадь 64 на 64 квадрата путем рекурсивного деления на четыре квадрата, пока наименьший квадрат не имеет единичной длины (вряд ли оптимальной). Но по какой-то причине программа зависает. Что я делаю неправильно?

#include <iostream> 

unsigned compute(unsigned length) 
{ 
    if(length == 1) return length * length; 

    unsigned a[4] , area = 0 , len = length/2; 

    for(unsigned i = 0; i < 4; ++i) 
    { 
     #pragma omp task 
     { 
      a[i] = compute(len); 
     } 

     #pragma omp single 
     { 
      area += a[i]; 
     } 
    } 

    return area; 
} 

int main() 
{ 
    unsigned area , length = 64; 

    #pragma omp parallel 
    { 
     area = compute(length); 
    } 

    std::cout << area << std::endl; 
} 

Answer 1

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

В любом случае ваш код недействителен. После вашего блока задач a[i] еще не назначен, поэтому вы не можете сразу его использовать! Вы должны дождаться завершения задачи. Конечно, вы не должны делать этого внутри цикла, иначе задача не будет использовать какой-либо параллелизм. Решение состоит в том, чтобы сделать это в конце цикла. Также необходимо указать a как разделяемый для выхода, чтобы стать видимым:

for(unsigned i = 0; i < 4; ++i) 
{ 
    #pragma omp task shared(a) 
    { 
     a[i] = compute(len); 
    } 
} 
#pragma omp taskwait 
for(unsigned i = 0; i < 4; ++i) 
{ 
    area += a[i]; 
} 

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

#pragma omp parallel 
#pragma omp single 
{ 
    area = compute(length); 
} 

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

Answer 2

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

unsigned tp_area = 0; 
#pragma omp threadprivate(tp_area) 

void compute (unsigned length) 
{ 
    if (length == 1) 
    { 
     tp_area += 1; 
     return; 
    } 

    unsigned len = length/2; 

    for (unsigned i = 0; i < 4; ++i) 
    { 
#pragma omp task 
     { 
     compute (len); 
     } 
    } 
} 

int main() 
{ 
    unsigned area, length = 64; 

#pragma omp parallel 
    { 
#pragma omp single 
    { 
     compute (length); 
    } 
#pragma omp atomic 
    area += tp_area; 
    } 

    std::cout << area << std::endl; 
}