Ветвление рекурсивной функции с использованием OpenMP на верхнем уровне

Question

Контекст:

Предположим, что у меня есть функция f с нефиксированным ветвления фактора b. Исполнение начинается с глубины 0 и останавливается на заданной фиксированной глубине. Я хочу распараллелить выполнение f таким образом, что, когда глубина равна 0, каждая ветвь глубины 1 и все ее выполнение на глубинах более 1 будут перемещаться и выполняться на отдельный поток (на тот же поток).

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

#include <stdio.h> 
#include "omp.h" 


int b = 6; 
int maxDepth = 4; 

void f(int depth) { 
    if (depth == maxDepth) 
     return; 
    { 
     int i; 
     for (i = 0; i < depth; i++) printf(" "); 
    } 
    printf("D %d TID %d\n", depth, omp_get_thread_num()); 
    if (!depth) { 
     int i; 
     #pragma omp parallel for private(i) 
     for (i = 0; i < b; i++) { 
      f(depth+1); 
     } 
    } 
    else { 
     int i; 
     for (i = 0; i < b; i++) { 
      f(depth+1); 
     } 
    } 
} 

int main() { 
    omp_set_num_threads(4); 
    f(0); 
    printf("\n"); 

    return 0; 
} 

Что касается приведенной выше коды, как я должен установить приватность (shared, private) переменные с помощью прагм, чтобы какие переменные мне следует применять, и почему?

Answer 1

Вместо директивы #pragma omp for, попробуйте использовать задачи. В самых последних стандартах OpenMP существует новая директива цикла, которая используется для создания задачи: #pragma omp taskloop.

Другой способ достижения той же цели, чтобы разделить ваши функции f() надвое:

void f(int depth) { 
    int i; 
    #pragma omp parallel private(i) 
    { 
     //#pragma omp for or ... 
     #pragma omp single 
     #pragma omp taskloop 
     for (i = 0; i < b; i++) { 
     f_nontopmost(depth+1); 
     } 
     // taskloop will implicitly wait for all created tasks 
     // at the end 
    } 
} 

void f_nontopmost(int depth) { 
    if (depth == maxDepth) 
     return; 

    int i; 
    // since we are in parallel section, we can still create tasks 
    #pragma omp taskloop 
    for (i = 0; i < b; i++) { 
     f(depth+1); 
    } 
}