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;
        }
    }
}

プライベート行 (および列) 変数に依存する配列にのみ書き込みを行っており、行はピボットよりも大きいことが保証されているため、何も上書きしていないことはコンパイラーにとって明らかなはずです。

私はコンパイルしていて-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

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 に答える
2

同じ自動並列化の問題が icc 12.1 にあります。そこで、この新しいバージョンを実験に使用しました。

関数のパラメーター リストに出力行列を追加し、3 番目のループの本体をこれに変更します。

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

「FLOW依存」の問題を修正しました。つまり、「-fno-alias」は関数パラメーターのみに影響を与えますが、単一のパラメーターの内容はエイリアスされている疑いがあります。このオプションがすべてに影響しない理由はわかりません。マトリックスのさまざまな部分は実際には互いにエイリアス化されていないため、この追加パラメーターを関数に残して、このパラメーターを介して同じマトリックスを渡すことができます。

興味深いことに、'matrix' について不平を言う一方で、コンパイラは 'vector' について何も言わず、実際にはエイリアシングの問題があります: この行vector[row] -= vector[pivot] * tmp;は誤ったエイリアシングにつながる可能性があります (1 つのスレッドで に書き込むと、すべてのスレッドで使用されるvector[row]を格納するキャッシュ ラインに触れる可能性があります)。vector[pivot]

このコードの問題は「FLOW 依存」だけではありません。修正された後も、「計算作業が不十分」であるため、コンパイラは 2 番目と 3 番目のループの並列化を拒否します。だから私はそれにいくつかの余分な仕事を与えようとしました：

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

そして、このすべての後、2 番目のループがようやく並列化されましたが、速度が向上したかどうかはわかりません。

更新：コンピューターに「余分な仕事」を与えるより良い代替手段を見つけました。オプション-par-threshold50がそのトリックを行います。

于 2012-05-03T16:27:57.037 に答える
1

私のアイデアをテストするための icc へのアクセス権はありませんが、コンパイラがエイリアシングを恐れているのではないかと思います: 行列は float**: float の配列を指すポインターの配列として定義されています。これらのポインターはすべて同じ float 配列を指す可能性があるため、これを並列化することは非常に危険です。これは意味がありませんが、コンパイラは知ることができません。

于 2012-04-28T09:09:14.020 に答える