如何将 openMP 应用于 C++ 函数以验证数独谜题解决方案的所有行？

Question

我正在设计一个程序，该程序将测试是否为该程序提供了有效的数独谜题解决方案。我最初是用 C++ 设计的，但现在我想尝试使其并行化。该程序编译正常，没有错误。

首先，我必须想出一种方法来处理在结构化块中使用 return 语句。我只是决定制作一个初始化为 true 的 bool 数组。但是这个函数的输出是错误的，我知道我提交的解决方案是正确的。我是 openMP 的新手，想知道是否有人可以帮助我？

我感觉问题出在我的变量 a 被设置回 0 并且可能还有我的其他变量 nextSudokuNum 设置回 1.

bool test_rows(int sudoku[9][9])
{
   int i, j, a;
   int nextSudokuNum = 1;
   bool rowReturn[9];

#pragma omp parallel for private(i)
   for(i = 0; i < 9; i++)
   {
      rowReturn[i] = true;
   }

#pragma omp parallel for private(i,j) \
   reduction(+: a, nextSudokuNum)
   for(i = 0; i < 9; i++)
   {
      for(j = 0; j < 9; j++)
      {
         a = 0;
         while(sudoku[i][a] != nextSudokuNum) {
            a++;
            if(a > 9) {
               rowReturn[i] = false;
            }
         }

         nextSudokuNum++;
      }
      nextSudokuNum = 1;
   }

   for(i = 0; i < 9; i++)
   {
      if(rowReturn[i] == false) {
         cout << "Invalid Sudoku Solution(Next Valid Sudoku Number Not Found)" << endl;
         cout << "Check row " << (i+1) << endl;
         return false;
      }
   }

   cout << "Valid sudoku rows(Returning true)" << endl;
   return true;
}

Answer 1

免责声明：

首先，不要并行化非常小的循环或几乎瞬时执行的循环。创建线程的开销将主导您通过并行执行循环的内部语句获得的好处。因此，除非您要并行化的每次迭代都执行数以亿计的 FLOP，否则代码的串行版本将运行比代码的并行版本快。

因此，并行化（可能的）任务的更好计划是在更高级别并行化。也就是说，假设您正在从其他地方的一个函数调用 test_rows(sudoku)、test_columns(sudoku) 和 test_box(sudoku)。您可以做的是使用 OpenMP sections 并行调用这三个串行函数，其中调用这三个函数中的每一个都是单独的 OpenMP section。这只会受益于使用 CPU 的 3 个内核，但大概您是在笔记本电脑上执行此操作，所以您可能只有 2 个或 4 个内核。

现在解决你的实际问题：

您没有在 j 上并行化，而只是在 i 上并行化。因此，你可以看到你的变量 nextSudokuNum 并没有减少；对于每个 i 迭代，nextSudokuNum 是独立的。因此，它应该在循环内初始化，并在 #pragma omp parallel 子句中制作 private。

同样，您也没有对 a 进行缩减。对于 i 的每次迭代，a 都会在内部进行设置、比较和递增。同样，它应该是一个私有变量。

因此，您的新代码应如下所示：

   #pragma omp parallel for private(i,j,a,nextSudokuNum)
   for(i = 0; i < 9; i++)
   {
      // all private variables must be set internal to parallel region before being used
      nextSudokuNum = 1;

      for(j = 0; j < 9; j++)
      {
         a = 0;
         while(sudoku[i][a] != nextSudokuNum) {
            a++;
            if(a > 9) {
               rowReturn[i] = false;
            }
         }

         nextSudokuNum++;
      }
   }

如何将 openMP 应用于 C++ 函数以验证数独谜题解决方案的所有行？

How to apply openMP to a C++ function to validate all rows of a sudoku puzzle solution?

c++

parallels

openmp

sudoku