途中でOpenMPを終了する

Question

OpenMPを使用してC++でルーチンを作成する際に問題があります。

int sudokuSolution [9][9]; 

bool solvep(int s[9][9], int row, int col) {  
    bool solution = false; 
    #pragma omp parallel for 
     for (int val = 1; val < 10; val++) { 
      if (isPossible(s,row,col,val)) { 
       s[row][col] = val; 
       if (solve(s, row + col/9, (col + 1) % 9)) { 
        sudokuSolution[row][col] = val; 
        solution = true; 
       } 
      } 
     } 
    return solution; 
} 

並列句なし、このルーチンを実行し、すべてが正常に動作します（つまり、リターンtrueそれが呼ばれていますたび）：次のようにルーチンのコードがあります。しかし、私がparallel forを使うと、falseを返すことがあります。私は解明できませんでしたが、なぜこれが起こっているのか、このバグを取り除く唯一の方法は、解決策がtrueに設定された後、全面的なブロックを早く終了させる私の見解からです。しかし、私が研究を適切に行った場合、並列ブロックを早期に終了する方法はありません。あなたは私に代替案を提案してもらえますか？あなたは||演算子を使用してすべてのスレッド上の解の値をreduceでき

#include <omp.h> 
#include <iostream> 
#include <list> 
#include <chrono> 

using namespace std; 

bool solutionFound = false; 
int sudoku [9][9] = { 5,7,0,9,0,0,0,0,8, 
         0,0,0,0,0,5,0,3,9, 
         0,0,0,0,0,0,2,0,4, 
         0,0,0,0,9,0,6,8,0, 
         0,0,0,8,0,2,0,0,0, 
         0,5,2,0,7,0,0,0,0, 
         6,0,5,0,0,0,0,0,0, 
         7,9,0,4,0,0,0,0,0, 
         2,0,0,0,0,9,0,7,6}; 

int sudokuSolution [9][9]; 

bool isPossible(int s[9][9], int row, int col, int val) { 
    for(int i = 0; i < 9; i++) { 
     if (s[row][i] == val) 
      return false; 
     if (s[i][col] == val) 
      return false; 
     if (s[row/3 * 3 + i/3][col/3 * 3 + i % 3] == val) 
      return false; 
    }  
    return true; 
} 

bool solve(int s[9][9], int row, int col) { 
    while(s[row][col] != 0) { 
     col = (col + 1) % 9; 
     row = row + col/8; 
     if(row == 9)   
      return true; 
    } 

    for (int val = 1; val < 10; val++) { 
     if (isPossible(s,row,col,val)){ 
      sudokuSolution[row][col] = val; 
      s[row][col] = val; 
      if (solve(s, row + col/9, (col + 1) % 9)) 
       return true; 
      sudokuSolution[row][col] = 0; 
      s[row][col] = 0; 
     } 
    } 
    return false; 
} 


bool solvep(int sa[9][9], int row, int col) { 
    int s [9][9]; 
    for(int i = 0; i < 9; i++) 
     for(int j = 0; j < 9; j++) 
      s[i][j] = sa[i][j]; 
    while(s[row][col] != 0) { 
     col = (col + 1) % 9; 
     row = row + col/8; 
     if(row == 9)   
      return true; 
    } 
    bool solution = false; 
    #pragma omp parallel for 
     for (int val = 1; val < 10; val++) { 
      if(!solutionFound) { 
       if (isPossible(s,row,col,val)){ 
        s[row][col] = val; 
        if (solve(s, row + col/9, (col + 1) % 9)) { 
         sudokuSolution[row][col] = val; 
         solutionFound = true; 
         solution = true; 
        } 
       } 
      } 
     } 
    return solution; 
} 

int main() { 
    for (int k = 0; k < 100; k++) {  
     for(int i = 0; i < 9; i++) 
      for(int j = 0; j < 9; j++) 
       sudokuSolution[i][j] = sudoku[i][j]; 
     solutionFound = false;  
     solvep(sudokuSolution,0,0); 
     bool calcResult = solvep(sudoku,0,0); 
     cout << calcResult; 
    } 
    return 0; 
} 

Answer 1

：

EDIT：要求されたとして、最小限の機能の例を追加するに

int sudokuSolution [9][9]; 

bool solvep(int s[9][9], int row, int col) {  
    bool solution = false; 
    #pragma omp parallel for reduction(||:solution) 
     for (int val = 1; val < 10; val++) { 
      if (isPossible(s,row,col,val)) { 
       s[row][col] = val; 
       if (solve(s, row + col/9, (col + 1) % 9)) { 
        sudokuSolution[row][col] = val; 
        solution = true; 
       } else { 
        solution = false; 
       } 
      } else { 
       solution = false; 
      } 
     } 
    return solution; 
} 

Answer 2

あなたはあなたのコード内の多くの競合状態を持っています、ループ自体とsolveの両方の機能です。並列に実行されるコードでは、共有データ（s、solution、sudokuSolution）、特にグローバル変数（solutionFound）に書き込むべきではありません。あなたは学習教材に戻り、データ競争とそれらを守る方法に追いつく必要があります。

いくつかの経験をすると、ループ自体で問題を見つけるのは簡単です。呼び出される関数にスポットするのはずっと難しいので、あなたの質問に完全な例を与えることが重要です。変更可能な共有データが関数に渡されないように、インタフェースを定義してください。概念的には、各スレッドがバックトラックを並行して実行するためにボードのコピーを持たなければなりません。

ボードに書き込む際の問題を修正したら、アトミック書き込み、クリティカルリージョン、または削減を使用してソリューションを「共有」できます。しかし、sudokuSolution[row][col]とsolutionの両方を考慮する必要があります。論理的には私はsudokuSolution[row][col] != 0 == solutionと思います。