c++ - OpenMP - 二叉树

Question

我正在尝试运行一个简单的并行运行程序。我想将它基于二叉树。基于处理器的数量，我想将工作分配给所有处理器，以便程序并行运行。使用递归，我正在检查是否还有 1 或 2 个处理器，如果是，我正在使用 OpenMP sections 来运行它。但是，它使用的核心越多，算法就越慢，我不明白为什么。我尽量编写不言自明的代码。

void fun1(int tab[], int pocz, int kon, int threadsLeft)
{
    if (threadsLeft == 2)
    {
        #pragma omp parallel num_threads(2)
        {
            #pragma omp sections nowait
            {
                #pragma omp section
                {
                    for (int i = pocz; i < kon/2; i++)
                    {
                        tab[i] = 1;
                    }

                }
                #pragma omp section
                {
                    for(int i = kon/2 + 1; i < kon; i++)
                    {
                        tab[i] = 0;
                    }
                }
            }
        }
    }
    else if (threadsLeft == 1)
    {
        #pragma omp parallel num_threads(1)
        {
            #pragma omp sections nowait
            {
                #pragma omp section
                {
                    for (int i = pocz; i < kon; i++)
                    {
                        tab[i] = 2;
                    }
                }
            }
        }
    }
    else
    {
        fun1(tab, pocz, kon/2, threadsLeft/2);
        fun1(tab, kon - kon/2, kon, threadsLeft - threadsLeft / 2);
    }
}

int main()
{
    int allThreads = omp_get_num_threads();
    int N = 200000000;
    int* tab = new int[N];
    for (int i = 0; i < N; i++)
    {
        tab[i] = 0;
    }
    fun1(tab, 0, N, allThreads);
}

Answer 1

在我看来，您有两个问题。

第一个问题是，在您的主函数中，在并行区域之外，omp_get_num_threads() 应该始终返回 1。因此，在并行区域中调用它以访问您的线程数您当前拥有的平行区域。

第二个问题是你有一个递归问题，它有助于任务并行化。 OpenMP sections 最好与常数 a-priori 已知的部分一起使用。 OpenMP tasks 旨在处理递归问题，其中您想要生成的tasks 的数量不一定是已知的。例如，看看这个 basic tutorial .请注意，您的编译器必须支持 OpenMP 3.0 才能正常工作。

将两者放在一起，您的新 #pragma omp tasks 代码应如下所示:

void fun1(int tab[], int pocz, int kon, int threadsLeft)
{
    if (threadsLeft <= 1) {
        for (int i = pocz; i < kon; i++)
            tab[i] = 2; // should make this constant something else to be more helpful
    }
    else
    {
        #pragma omp task
        fun1(tab, pocz, kon/2, threadsLeft/2);
        #pragma omp task
        fun1(tab, kon - kon/2, kon, threadsLeft - threadsLeft/2);
        #pragma omp taskwait
    }
}

int main()
{

    int N = 200000000;
    int* tab = new int[N];
    for (int i = 0; i < N; i++)
        tab[i] = 0;

    #pragma omp parallel
    // Only the first thread will spawn other threads
    #pragma omp single nowait
    {
        int allThreads = omp_get_num_threads();
        fun1(tab, 0, N, allThreads);
    }

}

公平警告:我自己还没有测试过这段代码，所以请对它持保留态度。