0

これは、return 1;実際return 0;にはバックトラッキングアルゴリズムを使用した数独ソルバーであるため、並列化しようとしていますが、完全な結果を得ることができません。（私の実装が間違っている場合は修正してください）実際に何が起こりますか？誰か助けてくれませんか?!

これは私が参照しているサイトです。私は彼らのやり方に従っていました: http://www.thinkingparallel.com/2007/06/29/breaking-out-of-loops-in-openmp/#reply 

int solver (int row, int col)
{
   int i;
   boolean flag = FALSE;
   if (outBoard[row][col] == 0)
   {
      #pragma omp parallel num_threads(2)
      #pragma omp parallel for //it works if i remove this line
      for (i = 1; i < 10; i++)
      {
         if (checkExist(row, col, i)) //if not, assign number i to the empty cell
            outBoard[row][col] = i;

         #pragma omp flush (flag)
         if (!flag)
         {
            if (row == 8 && col == 8)
            {
               //return 1;
               flag = TRUE;
               #pragma omp flush (flag)
            }
            else if (row == 8)
            {
               if (solver(0, col+1))
               {
                  //return 1;
                  flag = TRUE;
                  #pragma omp flush (flag)
               }
            }
            else if (solver(row+1, col))
            {
               //return 1;
               flag = TRUE;
               #pragma omp flush (flag)
            }
         }
      }


         if (flag) { return 1; }

         if (i == 10) 
         { 
            if (outBoard[row][col] !=  inBoardA[row][col]) 
            outBoard[row][col] = 0;
        return 0; 
          } 

     } 
     else 
      { 
        if (row == 8 && col == 8) 
         { 
        return 1; 
          } 
         else if (row == 8) 
         {    
            if (solver(0,col+1)) return 1; 
          } 
          else 
          { 
            if (solver(row+1,col)) return 1; 
           } 

     return 0;
    }
}

5 0 0 0 0 3 7 0 0
7 4 6 1 0 2 3 0 0
0 3 8 0 9 7 5 0 2
9 7 0 4 0 0 2 0 0
0 0 2 0 0 0 4 0 0
0 0 4 0 0 5 0 1 9
4 0 3 2 7 0 9 8 0
0 0 5 3 0 9 6 7 4
0 0 7 5 0 0 0 0 3
Sudoku solved :
5 2 9 8 0 3 7 4 1
7 4 6 1 5 2 3 9 0
1 3 8 0 9 7 5 6 2
9 7 0 4 1 0 2 3 6
0 1 2 9 6 0 4 5 8
3 6 4 7 8 5 0 1 9
4 0 3 2 7 6 9 8 5
2 8 5 3 0 9 6 7 4
6 9 7 5 4 8 1 2 3

//return 1;は元のシリアル コードです。はreturnでは許可されていないparallel forため、以前は#pragma opm flush削除していましたが、結果は完全ではなく、数独に空のグリッドがいくつか残っていました。

答えてくれてありがとう:>

4

1 に答える 1

0

まず、solverは再帰的に呼び出されるため、再帰の各レベルでスレッドの数が 2 倍になります。それはあなたが意図したことではないと思います。 編集:これは、ネストされた並列処理が有効になっている場合にのみ当てはまり、omp_set_nested()デフォルトでは有効になっていません。したがって、の最初の呼び出しのみsolverが fork します。

#pragma omp parallel num_threads(2)
#pragma omp parallel for

あなたのコードでは、ある並列領域を別の領域内に作成しようとすると、外部でparallel既に 2 つのスレッドが作成されているため、後続のループが 2 回実行されます。これは

#pragma omp parallel num_threads(2)
#pragma omp for

または同等のもの#pragma omp parallel for num_threads(2)。

次に、このコード:

if (checkExist(row,col,i))//if not, assign number i to the empty cell
    outBoard[row][col] = i;

両方のスレッドが同じセルに異なる値を並行して書き込む競合状態を作成します。作業するスレッドごとにボードの個別のコピーを作成することをお勧めします。

別のコード部分、

if (outBoard[row][col] != inBoardA[row][col]) 
    outBoard[row][col] = 0;

は並列領域の外にあるように見えますが、ネストされた呼び出しでは、solver最も外側の によって作成された異なるスレッドでも並列に実行されsolverます。

Final(e) (18.09) とにかく、コードをデバッグ/変更して正しく並行して実行できたとしても (私自身がやったように-誰かが興味を持っている場合はコードを提供しようとします。私は疑います)、結果として、このコードを並列実行してもあまり利点が得られないでしょう。私が考える理由は以下の通りです。

想像してみてくださいsolver9 つの可能なセル値を繰り返し、9 つの実行分岐を作成します。OpenMP を使用して 2 つのスレッドを作成すると、何らかの方法でスレッド間で最上位の分岐が分散されます。たとえば、あるスレッドで 5 つの分岐が実行され、別のスレッドで 4 つの分岐が実行され、各スレッドで分岐が 1 つずつ連続して実行されます。数独の初期状態が有効な場合、1 つの分岐のみが正解につながります。他の分岐は、解に矛盾が生じると短くなります。そのため、実行に時間がかかるものもあれば、実行に時間がかかるものもあり、正しい解につながる分岐が最も長く実行されます。どのブランチの実行にどのくらいの時間がかかるかを予測できないため、スレッド間でワークロードを合理的にバランスさせる方法はありません。OpenMP 動的スケジューリングを使用している場合でも、1 つのスレッドが最長の分岐を実行している間に、

スレッドを作成し、それらの間でデータを同期すると、かなりのオーバーヘッドが発生するため ( solver0.01 ～ 10 ミリ秒の順次実行時間と比較して)、入力に応じて、並列実行時間が順次よりも多少長くなったり短くなったりします。

いずれにせよ、逐次ソルバーの実行時間が 10 ミリ秒未満の場合、なぜ並列化する必要があるのでしょうか。

于 2012-09-14T09:36:02.470 に答える