Лучший способ распараллелить рекурсии с использованием OpenMP

Question

Я следующее рекурсивную функцию (ПРИМЕЧАНИЕ: лишен всех незначительных деталей)

int recursion(...) { 

    int minimum = INFINITY; 
    for(int i=0; i<C; i++) { 
     int foo = recursion(...); 

     if (foo < minimum) { 
      minimum = foo; 
     } 
    } 

    return minimum; 
} 

Примечание 2: Это конечное, но не в этом упрощенном примере, поэтому, пожалуйста, проигнорируйте это. Целью этого вопроса является правильное рассмотрение этой проблемы.

Я думал об использовании задач, но я не уверен, как правильно его использовать - как парализовать внутренний цикл.

EDIT 1: Дерево рекурсии плохо сбалансировано. Он используется с динамическим подходом к программированию, поэтому со временем многие значения повторно используются с предыдущих проходов. Меня это очень беспокоит, и я думаю, что это будет большим узким местом.

C находится где-то около 20.

Метрики для лучшего является самым быстрым :)

Он будет работать на 2х Xeon, так что есть много HW власти Availible.

Answer 1

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

Я бы собрал результаты в vector и вычислил минимум снаружи. Вы также можете выполнить минимальное вычисление (критическое/блокирующее) в задаче.

Избегайте нереста задач/выделения памяти для минимума, если вы слишком глубоки в рекурсии, где отношение служебных/рабочих отношений становится слишком плохим. Самое сильное решение - создать две отдельные (параллельные/последовательные) рекурсивные функции. Таким образом, у вас есть нулевая служебная нагрузка после переключения на последовательную функцию - в отличие от проверки глубины рекурсии на порог каждый раз в единой функции.

int recursion(...) { 
    #pragma omp parallel 
    #pragma omp single 
    return recursion_omp(...); 
} 

int recursion_ser(...) { 
    int minimum = INFINITY; 
    for(int i=0; i<C; i++) { 
     int foo = recursion_ser(...); 
     if (foo < minimum) { 
      minimum = foo; 
     } 
    } 
    return minimum; 
} 

int recursion_par(...) { 
    std::vector<int> foos(C); 
    for(int i=0; i<C; i++) { 
     #pragma omp task 
     { 
      if (depth < threshhold) { 
       foos[i] = recursion_par(...); 
      } else { 
       foos[i] = recursion_ser(...); 
      } 
     } 
    } 
    #pragma omp taskwait 
    return *std::min_element(std::begin(foos), std::end(foos)); 
} 

Очевидно, что вы не должны делать никаких гадостей с глобальным/общим состоянием в пределах незначительных деталей.