Разделение потоков OpenMP на неуравновешенном дереве

Question

Я пытаюсь сделать древовидные операции, например, суммировать числа во всех листах в дереве параллельно с использованием OpenMP. Проблема, с которой я сталкиваюсь, заключается в том, что дерево, над которым я работаю, является неуравновешенным (число детей меняется, а затем, как большие ветви меняются).

В настоящее время у меня есть рекурсивные функции, работающие над этими деревьями. То, что я пытаюсь достичь этого:

1) Разделить нити в первой возможности, скажем, это узел с 2 детьми

2) Continue расщеплению с обоих полученных нитей на уровне, по крайней мере 2-3 так все нити на работе

это будет выглядеть следующим образом:

if (node->depth <= 3) { 
    #pragma omp parallel 
    { 
     #pragma omp schedule(dynamic) 
     for (int i = 0; i < node->children_no; i++) { 
      int local_sum; 

      local_sum = sum_numbers(node->children[i]) 
      #pragma omp critical 
      { 
       global_sum += local_sum; 
      } 
     } 
    } 
} else { 
    /*run the for loop without parallel region*/ 
} 

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

1) Каждый поток создания новой команды не может принимать больше потоков, чем max_threads

2) После того, как цикл закончен в одном поддереве остальные по-прежнему работает на петлях в больших поддеревях берут на себя теперь бездействующие потоки, чтобы быстрее закончить свою работу.

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

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

Answer 1

Только для записи я напишу ответ на этот вопрос на основе комментария High Performance Mark (комментарий, к которому я тоже согласен). Использование здесь задач OpenMP добавит гибкости в параллелизм, даже если дерево будет неуравновешенным, поддержка рекурсивности и нерегулярность работы для всех потоков (несмотря на то, что вы должны исследовать это с помощью таких инструментов, как , Paraver и/или HPCToolkit).

Полученный код может выглядеть

if (node->depth <= 3) { 
    #pragma omp parallel shared (global_sum) 
    { 
     for (int i = 0; i < node->children_no; i++) { 
      int local_sum; 

      #pragma omp single 
      #pragma omp task 
      { 
       local_sum = sum_numbers(node->children[i]) 

       #pragma omp critical 
       global_sum += local_sum; 
      } 
     } 
    } 
} else { 
    /*run the for loop without parallel region*/ 
}