2

我在尝试重新编码嵌套的 for 循环以使其并行化时遇到问题：

for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        if(asubsref(struct1,j) > 0)
            asubsref(struct2,j) = asubsref(struct3,j) + 1;
    }
    for(j=0; j<n; j++)
        asubsref(struct1,j) = asubsref(struct2,j) - asubsref(struct3,i);
}

Struct1/struct2 是两个分别具有宽度/高度/int-float 数组的结构。struct3 是一个浮点结构。

到目前为止，我的尝试是将它们变成两个不同的循环，但可惜，它不起作用，因为我会得到很多不正确的结果：

#pragma omp parallel
{
#pragma omp for private(j)
   for(i=0; i<n; i++)
   {
     for(j=0; j<n; j++)
     {
       if(asubsref(struct1,j) > 0)
         asubsref(struct2,j) += 1;
     }
   }
#pragma omp for private(j)
   for(i=0; i<n; i++)
   {
     k = asubsref(struct3,i);
     for (j=0; j<n; j++)
     {
       asubsref(struct1,j) -= k;
     }
   }
}

我不是在寻找答案，而是在寻找一些指导来帮助我思考如何解决这个问题/提示答案等。

4

1 回答 1

4

我在这段代码中看到的是三个数组：

array1: asubsref(seed,0) ... asubsref(seed,n-1)
array2: asubsref(bin,0) ... asubsref(bin,n-1)
array3: asubsref(w,0) ... asubsref(w,n-1)

如果这个假设是正确的并且 asubsref 不会产生任何副作用，则可以推导出以下不变量：

循环执行结束后，array2[j] 增加数字 x，该数字是最大的数字，使得 i 从 0 到 x 的 array3[i] 之和小于 array1[j]。

这是你可以做的。首先，您可以合并两个最里面的循环，因为（在我们的假设下）它们的迭代是独立的：

for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        if(asubsref(seed,j) > 0)
            asubsref(bin,j) = asubsref(bin,j) + 1;
        asubsref(seed,j) = asubsref(seed,j) - asubsref(w,i);
    }
}

然后交换最里面和最外面的循环

for(j=0; j<n; j++)
{
   for(i=0; i<n; i++)
   {
        if(asubsref(seed,j) > 0)
            asubsref(bin,j) = asubsref(bin,j) + 1;
        asubsref(seed,j) = asubsref(seed,j) - asubsref(w,i);
   }
}

现在很明显，以下代码应该可以工作

#pragma omp parallel for (private i)
for(j=0; j<n; j++)
{
   for(i=0; i<n; i++)
   {
        if(asubsref(seed,j) > 0)
            asubsref(bin,j) = asubsref(bin,j) + 1;
        asubsref(seed,j) = asubsref(seed,j) - asubsref(w,i);
   }
}

而拆分循环显然会破坏不变量。

于 2012-05-23T12:38:15.630 回答