使用 openMP Task 时的意外行为 [英] Unexpected behavior when using openMP Task

问题描述

我正在尝试编写一个用于解决数独的蛮力算法的并行版本.

I'm trying to write a parallel version of a brute-force algorithm for solving Sudoku.

串行算法如下，伪代码:

The serial algorithm is the following, in pseudo-code:

solve(matrix, x, y):
    for i in [0,9]:
        //If test number fits rules
        if(valid(matrix, x, y, i):
            matrix[y,x] = i
            //Try next cell recursively
            if(solve(matrix, nextEmptyX, nextEmptyY)) return true
            //test number not the solution, backtrack.
            matrix[y][x] = 0
 return false;

如果我在这个伪代码中犯了错误，我深表歉意，但我认为它是正确的.无论哪种方式，我的串行算法都有效.

I apologize if I made a mistake in this pseudo-code, but I think it's correct. Either way, my serial algorithm works.

问题是当我试图像这样并行化它

The problem is when I try to paralelize it like this

solve(matrix, x, y):
    for i in [0,9]:
        if(valid(matrix, x, y, i):
            val = 0
            #pragma omp task firstprivate(x, y, i, matrix, val)
                copy_matrix = copyOf(matrix)
                copy_matrix[y][x] = i
                val = solve(copy_matrix, nextEmptyX, nextEmptyY)
                if(val) print_matrix
            if(val) return true
            matrix[y][x] = 0
#pragma omp taskwait 
return false;

在我看来，这段代码应该尝试新任务中每个单元格的每个暂定值，并且至少有一个任务应该有正确的解决方案.但是当我运行它时，它并没有测试 (y,x) 的每个组合(它实际上似乎只测试了矩阵的第一行，并没有找到结果.

In my mind this code should try each tentative value for each cell in a new task, and at least one task should have the correct solution. But when I run it, it doesn't test every combination of (y,x) (it actually seems to only test the first row of the matrix and it doesn't find the result.

我是这样打电话的:

#pragma omp parallel sections
    {
            #pragma omp section
            solve(matrix, 0, 0);
    }

通过设置 omp_set_num_threads(1)

如果我只更改 OMP 注释，则算法有效.

If I change nothing but remove the OMP annotations, the algorithm works.

有人能看出问题吗?

我刚刚意识到有时执行会跳过任务块，我不知道为什么会发生这种情况，但似乎是导致问题的原因.

I just realized that sometimes the execution skips over the task block, I don't know why that is happening but it seems to be causing the problem.

推荐答案

在 C 中，#pragma omp 仅用于下一行.

In C, #pragma omp is only for the following line.

缩进表明你应该有

solve(matrix, x, y):
    for i in [0,9]:
        if(valid(matrix, x, y, i):
            val = 0
            #pragma omp task firstprivate(x, y, i, matrix, val)
              {
                copy_matrix = copyOf(matrix)
                copy_matrix[y][x] = i
                val = solve(copy_matrix, nextEmptyX, nextEmptyY)
                if(val) print_matrix
              }
            if(val) return true
            matrix[y][x] = 0
#pragma omp taskwait 
return false;

不确定这是否足以解决您的问题.

Not sure this is enough to solve your issue though.

这篇关于使用 openMP Task 时的意外行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！