代码之家 › 专栏 › 技术社区 › xTaylorFerg

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

parallels sudoku openmp c++

3

xTaylorFerg · 技术社区 · 8 年前

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

首先,我必须找到一种方法来处理在结构化块中使用return语句。我刚刚决定创建一个初始化为true的布尔数组。然而,这个函数的输出是错误的,我知道我提交的解决方案是正确的。我是openMP的新手,想知道是否有人能帮我吗?

我觉得问题出在我的变量上一回到 0 也许还有我的另一个变量 下一个SudokuNum 回到 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;
}

1 回复 | 直到 8 年前

1

0

NoseKnowsAll Ori Lentz 8 年前

免责声明:

首先,不要将非常小的循环或几乎立即执行的循环并行化。创建线程的开销将支配通过并行执行循环的内部语句而获得的好处。因此,除非您正在并行化的每个迭代执行成千上万的FLOP,否则代码的串行版本将比代码的并行版本运行得更快。

因此,一个更好的并行化(可能)任务的计划是在更高的级别上进行并行化。也就是说,大概你在打电话 test_rows(sudoku) , test_columns(sudoku) 和 test_box(sudoku) 从一个函数到另一个函数。您可以使用OpenMP并行调用这三个串行函数 sections 其中调用这三个函数中的每一个都是一个单独的OpenMP section 。这只会从使用3个CPU核中受益,但想必你是在笔记本电脑上这样做的,所以你可能只有2或4个。

现在谈谈你的实际问题:

你没有在 j ,但只是结束 i 。因此,您可以看到您的变量 nextSudokuNum 没有减少;每 我 迭代, 下一个SudokuNum 是独立的。因此,它应该在循环内初始化并 private 在 #pragma omp parallel 条款

同样地,您也没有在 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++;
      }
   }