c - OpenMP : Creating threads, 并行性，循环障碍

Question

我正在使用 OpenMP 并尝试使用大小为 n 的表获取算法前缀和的跨度 log(n)。对于表格的每个单元格，我都有表格所有先前值的总和。

在我得到的解决方案中，有一个循环我无法并行化，我正在使用循环中的 n 个线程的数量来处理数组 T 的每个单元格(所以线程号 i 在 T[i] 上工作)。

编辑:这里是顺序算法，用于对包含 n 个单元格的表 T 执行此操作。

prefix_sum(int ** T, int n)
{
    for(i = 2; i <= n; i *= 2) // this loop cannot be parallelized
    {
        for (l=1; l <= n/i; l++) // this loop can be parallelized
        {
            T[l*i - 1] += T[l*i - i/2 - 1];
        }
    }

        for(i = n/2; i >= 2; i /= 2) // this loop cannot be parallelized
        {
            for (l = 1; l < n/i; l++) // this loop can be parallelized
            {
                T[i*l + i/2 - 1] += T[i*l - 1];
            }
        }
    }

    return T;
}

我想避免像这样对每个循环进行编码:

#pragma omp single
{
    for (i=2; i <= n; i*=2)
    {
        #pragma omp parallel num_threads(n)
        {
            if ((omp_get_thread_num() % i) == (i - 1))
            {
                T[omp_get_thread_num()] += T[omp_get_thread_num() - i/2];
            }
        }
    }
}

因为 openMP 规范通知为每个 #pragma omp parallel 创建线程组，我丢失了 log(n) 的跨度。在这段代码中，我有一个 log^2(n) 的跨度来创建线程。因此，我尝试像这样进行每个循环:

omp_set_num_threads(8); //this is a test code with 8 threads

#pragma omp parallel
{
    for (i = 0; i < 8; ++i)
    {
        printf("iteration : %d\n", i);

        #pragma omp barrier
    }
}

for 循环的每一步都必须按顺序执行，因此我们的想法是将它们与 n 个线程并行化，并让所有线程在循环的每一步结束时使用屏障等待。

但似乎障碍正在阻止并行性。执行显示:

iteration : 0
iteration : 0
iteration : 0
iteration : 0
iteration : 0
iteration : 0
iteration : 0
iteration : 0
iteration : 1
iteration : 2
iteration : 3
iteration : 4
iteration : 5
iteration : 6
iteration : 7
^C <- the program loops infinitely...

似乎只有一个线程在第一个屏障之后执行循环。根据 openMP 规范，遇到的工作共享区域和屏障区域的顺序对于团队中的每个线程都必须相同，并且此程序遵守此限制。

所以我想知道是否有人知道如何让线程在循环的每一步都等待其他线程。

Answer 1

在您的代码中，循环迭代器 i 是无意中共享的；

#pragma omp parallel

应该是

#pragma omp parallel private(i)

现场演示:http://melpon.org/wandbox/permlink/nE74kARjqoBjVWbr