c++ - 优化openmp的依赖循环

Question

我有一个问题，我想用 openmp 并行化两个 for 循环。

如何使用 openmp 优化此循环:

void test(float** m,tab* t,int n){

    int i,j;
    float gain;
    for (i = 1; i < n; i++)
    {
        for (j = i + 1;] j < n; j++)
        {
            if (i != j)
            {
                gain=m[t[(i+n-1)%n]][t[j]] + m[t[i]][t[(j+1)%n]] - m[t[(i+n -1)%n]][t[i]] - m[t[j]][t[(j+1)%n]] 
                if (gain< 0)
                {
                    swapTab(t,i,j);
                }
            }
        }
    }
}

谢谢。

Answer 1

正如 Oli Charlesworth 指出的那样，矩阵中元素的遍历顺序很重要，因此简单地在最外层循环周围使用并行 for 指令是行不通的。

你确实有一个选择就是用一些空间换取时间。复制数组 T(将其命名为 T')。在迭代 1 中，您将替换您的行:

swapTab(t,i,j)

类似的东西

 T'[j][i] = T[i][j]

(我不是一个 C++ 程序员，所以请忽略语法中的缺陷。)

在第二次迭代中，您首先需要将 T' 复制回 T，然后继续。不要这样做——设置指向 T 和 T' 的指针(也许是 Tnew、Told)并切换指针，使 Told 始终指向要读取的数组，Tnew 始终指向要写入的数组。