1

我一直在尝试使用 OpenMP 并行化具有不平衡嵌套 for 循环的算法。我不能发布原始代码，因为它是一个闻所未闻的政府的秘密项目，但这里有一个玩具示例：

for (i = 0; i < 100; i++) {
    #pragma omp parallel for private(j, k)
    for (j = 0; j < 1000000; j++) {
        for (k = 0; k < 2; k++) {
            temp = i * j * k;      /* dummy operation (don't mind the race) */
        }
        if (i % 2 == 0) temp = 0;  /* so I can't use openmp collapse */
    }
}

目前，此示例在多线程中运行速度较慢（单线程约 1 秒，2线程约 2.4 秒等）。

注意事项：

  • 外部 for 循环需要按顺序完成（取决于上一步）（据我所知，OpenMP 可以很好地处理内部循环，因此不会在每个步骤中创建/销毁线程，对吗？）

  • 示例中给出了典型的索引号(100, 1000000, 2)

  • 虚拟操作仅包含几个操作

  • 在最里面的循环之外有一些条件操作，所以折叠不是一种选择（看起来它无论如何都不会提高性能）

看起来像一个令人尴尬的并行算法，但过去两天我似乎无法获得任何加速。这里最好的策略是什么？

4

2 回答 2

5

不幸的是，这种令人尴尬的并行算法是如何实现高性能并行的一个令人尴尬的坏例子。而且由于我的水晶球告诉我，除此之外i,temp也是一个共享的自动变量，我将在本文的其余部分假设它。它还告诉我你有一个 pre-Nehalem CPU...

这里有两个减速源——代码转换和缓存一致性。

实现并行区域的方式是将它们的代码提取到单独的函数中。共享局部变量被提取到结构中，然后在执行并行区域的团队中的线程之间共享。在 OpenMP 转换下，您的代码示例将变得与此类似：

typedef struct {
    int i;
    int temp;
} main_omp_fn_0_shared_vars;

void main_omp_fn_0 (void *data) {
    main_omp_fn_0_shared_vars *vars = data;

    // compute values of j_min and j_max for this thread

    for (j = j_min; j < j_max; j++) {
        for (k = 0; k < 2; k++) {
            vars->temp = vars->i * j * k;
        if (vars->i % 2 == 0) vars->temp = 0;
    }
}

int main (void) {
    int i, temp;
    main_omp_fn_0_shared_vars vars;

    for (i = 0; i < 100; i++)
    {
        vars.i = i;
        vars.temp = temp;

        // This is how GCC implements parallel regions with libgomp

        // Start main_omp_fn_0 in the other threads
        GOMP_parallel_start(main_omp_fn_0, &vars, 0);

        // Start main_omp_fn_0 in the main thread
        main_omp_fn_0(&vars);

        // Wait for other threads to finish (implicit barrier)
        GOMP_parallel_end();

        i = vars.i;
        temp = vars.temp;
    }
}

您需要为访问支付少量费用temp，i因为它们的中间值不能存储在寄存器中，而是每次都加载和存储。

另一个退化的来源是缓存一致性协议。从在多个 CPU 内核上执行的多个线程访问相同的内存位置会导致大量缓存失效事件。更糟糕的是，vars.i很vars.temp可能最终会出现在同一个缓存行中，虽然vars.i只是读取和vars.temp写入，但内部循环的每次迭代都可能发生完全缓存失效。

通常，对共享变量的访问受到显式同步结构（如原子语句和临界区）的保护，在这种情况下，性能下降是可以预料的。

于 2012-06-29T09:28:51.857 回答
2

想想开销：

由于您的外循环需要创建 x 线程来执行内循环中的工作，销毁它们，然后再次创建它们......等等 100 次。

您必须等到内部循环中最长的任务完成其工作，然后才能执行外部循环中的下一步，因此本质上这是一个同步开销。这些任务看起来并不规则，但是如果要执行的工作很小，那么您可以摆脱这种加速。

您需要在这里创建线程并分配私有变量。

如果内部循环内的工作量很小，则并行化该循环的好处可能不一定超过上述并行化开销的成本，因此您最终会减慢速度。

于 2012-06-29T00:28:26.507 回答