在不平衡树上拆分 OpenMP 线程

Question

我正在尝试使用 OpenMP 并行执行树操作，例如对树中所有叶子中的数字求和。我遇到的问题是我处理的树是不平衡的（children 的数量不同，然后分支的大小也不同）。

我目前有处理这些树的递归函数。我想要实现的是：

1) 在第一个可能的机会拆分线程，假设它是一个有 2 children

的节点

2) 继续从两个生成的线程中拆分至少 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) 一旦 for 循环在一个子树中结束，其他仍在更大子树中进行循环的工作接管现在空闲的线程以更快地完成它们的工作

这样我希望线程永远不会超过必要的数量，但只要所有 for 循环中未完成的任务总和多于创建的线程，它们就会一直工作。

从文档看来，parallel for uses only threads already created in parallel region.是否可以使其按描述工作，或者我是否需要更改实现以首先列出来自各个分支的任务，然后运行并行循环遍历该列表？

Answer 1

郑重声明，我将根据 High Performance Mark 的评论（我也同意该评论）写下这个问题的答案。即使树不平衡，此处使用 OpenMP 任务也会增加并行性的灵活性，支持递归并为所有线程生成足够的工作（尽管您应该使用 Vampir, Paraver and/or 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*/
}

在不平衡树上拆分 OpenMP 线程

Splitting OpenMP threads on unbalanced tree

c

multithreading

openmp