不平衡嵌套formp中的循环

Question

我一直在尝试使用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.4秒在2个线程等).

注意事项:

• 外循环需要按顺序完成(取决于前一步)(据我所知,OpenMP处理好内部循环,因此在每一步都不会创建/销毁线程,对吗？)

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

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

• 在最内层循环之外有一些条件操作,因此崩溃不是一种选择(似乎不会增加性能)

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

Answer 1

不幸的是,这种令人尴尬的并行算法是如何实现高性能并行性的一个令人尴尬的坏例子.因为我的水晶球告诉我,除此之外i,temp它也是一个共享的自动变量,我会在本文的其余部分假设它.它还告诉我你有一个预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只是写入,但在内部循环的每次迭代中都可能发生完全缓存失效.

通常,对共享变量的访问受到原子语句和关键部分等显式同步构造的保护,在这种情况下,很可能会出现性能下降.