c++ - 过早结束 OpenMP

Question

我在使用 OpenMP for 在 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;
}

在没有 parallel 子句的情况下运行此例程时，一切正常(即例程每次调用时返回 true)。但是，当我使用并行 for 时，它有时会返回 false。我无法弄清楚，为什么会发生这种情况，从我的角度来看，消除此错误的唯一方法是在解决方案设置为 true 后过早地结束整个并行 block 。但是，如果我研究得当，就没有办法提前结束并行 block 。你能给我推荐一个替代方案吗？

编辑:根据要求添加最小功能示例:

#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

您的代码中有许多竞争条件，包括循环本身和 solve 函数。在并行执行的代码中，您不得写入共享数据(s、solution、sudokuSolution)，尤其是全局变量(solutionFound).您将不得不回到您的学习 Material ，了解数据竞赛以及防范它们的方法。

有了一些经验，很容易发现循环本身的问题。在被调用的函数中更难发现——这就是为什么在你的问题中给出一个完整的例子如此重要。尝试定义您的接口(interface)，以便将可变的共享数据传递给函数。从概念上讲，您必须为每个线程准备一份棋盘拷贝才能并行执行回溯。

一旦解决了写入板的问题，就可以使用原子写入、临界区或缩减来“共享”解决方案。但是您必须同时考虑 sudokuSolution[row][col] 和 solution。从逻辑上讲，我假设 sudokuSolution[row][col] != 0 == solution。