2

我在ICC（11.1；旧的，但对此无能为力）中玩了一点自动并行化，我想知道为什么编译器不能并行化内部循环以进行简单的高斯消除：

void makeTriangular(float **matrix, float *vector, int n) {
    for (int pivot = 0; pivot < n - 1; pivot++) {
        // swap row so that the row with the largest value is
        // at pivot position for numerical stability
        int swapPos = findPivot(matrix, pivot, n);
        std::swap(matrix[pivot], matrix[swapPos]);
        std::swap(vector[pivot], vector[swapPos]);
        float pivotVal = matrix[pivot][pivot];
        for (int row = pivot + 1; row < n; row++) { // line 72; should be parallelized
            float tmp = matrix[row][pivot] / pivotVal;  
            for (int col = pivot + 1; col < n; col++) { // line 74
                matrix[row][col] -= matrix[pivot][col] * tmp;
            }
            vector[row] -= vector[pivot] * tmp;
        }
    }
}

我们只写入依赖于私有行（和 col）变量的数组，并且行保证大于枢轴，所以编译器应该很明显我们没有覆盖任何东西。

我正在编译-O3 -fno-alias -parallel -par-report3并获得很多依赖项 ala:assumed FLOW dependence between matrix line 75 and matrix line 73.或者assumed ANTI dependence between matrix line 73 and matrix line 75.仅第 75 行也是如此。编译器有什么问题？显然我可以准确地告诉它如何处理一些编译指示，但我想了解编译器可以单独获得什么。

4

3 回答 3

2

icc 12.1 上存在相同的自动并行化问题。所以我用这个较新的版本进行实验。

将输出矩阵添加到函数的参数列表并将第三个循环的主体更改为此

out[row][col] = matrix[row][col] - matrix[pivot][col] * tmp;

修复了“FLOW 依赖”问题。这意味着，“-fno-alias”只影响函数参数，而单个参数的内容仍然被怀疑是别名。我不知道为什么这个选项不会影响一切。由于矩阵的不同部分并没有真正相互别名，因此您可以将此附加参数留给函数并通过此参数传递相同的矩阵。

有趣的是，在抱怨“矩阵”时，编译器对“向量”只字未提，它确实存在别名问题：这一行vector[row] -= vector[pivot] * tmp;可能会导致错误的别名（在一个线程中写入vector[row]可能会触及缓存线，存储vector[pivot]，每个线程都使用）。

“FLOW 依赖”不是此代码中的唯一问题。修复后，编译器仍然拒绝并行化第二个和第三个循环，因为“计算工作不足”。所以我试着给它一些额外的工作：

float tmp = matrix[row][pivot] * pivotVal;
...
out[row][col] = matrix[row][col] - matrix[pivot][col] *tmp /pivotVal /pivotVal;

毕竟，第二个循环终于并行化了，尽管我不确定它是否获得了任何速度提升。

更新：我找到了一个更好的选择来给计算机“一些额外的工作”。选项-par-threshold50可以解决问题。

于 2012-05-03T16:27:57.037 回答
2

基本上编译器无法确定没有依赖关系，因为名称matrix和名称vector都被读取和写入（即使使用不同的区域）。您可能可以通过以下方式解决此问题（虽然有点脏）：

void makeTriangular(float **matrix, float *vector, int n)
{     
    for (int pivot = 0; pivot < n - 1; pivot++) 
    {         
         // swap row so that the row with the largest value is    
         // at pivot position for numerical stability       
         int swapPos = findPivot(matrix, pivot, n);    
         std::swap(matrix[pivot], matrix[swapPos]);   
         std::swap(vector[pivot], vector[swapPos]);     
         float pivotVal = matrix[pivot][pivot];     
         float **matrixForWriting = matrix;  // COPY THE POINTER
         float *vectorForWriting = vector;   // COPY THE POINTER
         // (then parallelize this next for loop as you were)
         for (int row = pivot + 1; row < n; row++)  { 
              float tmp = matrix[row][pivot] / pivotVal;               
              for (int col = pivot + 1; col < n; col++) {
                  // WRITE TO THE matrixForWriting VERSION
                  matrixForWriting[row][col] = matrix[row][col] - matrix[pivot][col] * tmp; 
              } 
              // WRITE TO THE vectorForWriting VERSION
              vectorForWriting[row] = vector[row] - vector[pivot] * tmp; 
         } 
    }
}

底线只是给你正在写的那些暂时不同的名字来欺骗编译器。我知道它有点脏，我一般不会推荐这种编程。但是如果你确定你没有数据依赖，那就完全没问题了。

事实上，我会在它周围放一些评论，让未来看到此代码的人非常清楚这是一种解决方法，以及您这样做的原因。

编辑：我认为@FPK 基本上触及了答案，@Evgeny Kluev 发布了答案。但是，在@Evgeny Kluev 的回答中，他建议将其设为输入参数，这可能会并行化，但不会给出正确的值，因为其中的条目matrix不会被更新。我认为我上面发布的代码也会给出正确的答案。

于 2012-05-03T19:53:31.630 回答
1

我无法访问 icc 来测试我的想法，但我怀疑编译器担心别名：矩阵定义为浮点**：指向浮点数组的指针数组。所有这些指针都可以指向同一个浮点数组，因此并行化这将是非常危险的。这没有任何意义，但编译器无法知道。

于 2012-04-28T09:09:14.020 回答