c - 带有任务的OpenMP递归错误无效分支到/来自OpenMP结构化块

Question

我在c中有一个解码迷宫的代码但是我想用openmp任务来做 - 每次有多个开放路径来选择新任务时应该创建并检查它是否导致了目标。

迷宫被定义为字符矩阵。

这是找到路径的函数。当我尝试编译它时，我收到以下错误：在函数'find_path'中：错误：与OpenMP结构块无关的分支

int find_path(int x, int y)
{
    // If x,y is outside maze, return false.
    if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return FALSE;
    // If x,y is the goal, return true.
    if ( maze[y][x] == 'G' ) return TRUE;
    // If x,y is not open, return false.
    if ( maze[y][x] != '.' && maze[y][x] != 'S' ) return FALSE;

    // Mark x,y part of solution path.
    maze[y][x] = '+';

    #pragma omp parallel num_threads(4)
    #pragma omp single nowait
    {       
        // If find_path North of x,y is true, return true.
        #pragma omp task firstprivate(x,y)
        if ( find_path(x, y - 1) == TRUE ) return TRUE;

        // If find_path East of x,y is true, return true.
        #pragma omp task firstprivate(x,y)
        if ( find_path(x + 1, y) == TRUE ) return TRUE;

        // If find_path South of x,y is true, return true.
        #pragma omp task firstprivate(x,y)
        if ( find_path(x, y + 1) == TRUE ) return TRUE;

        // If find_path West of x,y is true, return true.
        #pragma omp task firstprivate(x,y)
        if ( find_path(x - 1, y) == TRUE ) return TRUE;
        #pragma omp taskwait
    }   

    // Unmark x,y as part of solution path.
    maze[y][x] = 'x';

    return FALSE;
}

现在我真的不明白这个错误来自哪里？

Answer 1

对于并行部分，您可以执行以下操作：

• 在每个任务中准备4个整数（或布尔真的，但这是C），每个搜索方向一个。
• 让每个子任务在其中一个int中设置其返回值。
• 在taskwait之后，如果所有的int仍然包含false，则返回false。

就像是：

int n = 0, e = 0, s = 0, w = 0;
#pragma omp parallel num_threads(4)
#pragma omp single
{
    #pragma omp task firstprivate(x,y) depend(out: n)
    n = find_path(x, y - 1);

    #pragma omp task firstprivate(x,y) depend(out: e)
    e = find_path(x + 1, y);

    #pragma omp task firstprivate(x,y) depend(out: s)
    s = find_path(x, y + 1);

    #pragma omp task firstprivate(x,y) depend(out: w)
    w = find_path(x - 1, y);
}
// Any one non-zero means a path exists
return (n + e + s + w) > 0;

作为旁注，单个在结尾处有一个隐含的屏障，现在删除它，然后用“taskwait”将它放回去。让我们保持简单并使用隐式taskwait。

这将为您提供解决方案，但尚未提供路径。

---

但是你有一个更糟糕的问题，那就是这个程序永远不会结束。您正在为所有块的所有邻居及其邻居创建任务，依此类推，而不检查您是否已访问该块。

以这个1D 3区块迷宫为例：

[S][ ][G]

从块0开始，为1创建一个任务，为0和2创建一些任务，为1创建一些，为0和2创建一些，等等。因为你永远不会检查你是否访问了一个块，你将继续创建任务并没有完成任何工作。

这超出了你的问题的范围，但我建议你研究“并行回溯”。