具有共享数据的c-OpenMP递归任务导致了巨大的速度减慢

Question

我正在尝试用OpenMP任务实现一个n-queens求解器。然而，游戏板设置在主功能中，我将其赋予一个功能。

到目前为止，我有：

bool solve_NQueens(int board[N][N], int col) 
{ 
    if (col == N) 
    { 
        // #pragma omp critical
        //     print_solution(board);
        #pragma omp critical
            SOLUTION_EXISTS = true;
        return true; 
    } 
    for (int i = 0; i < N; i++) 
    { 
        if (can_be_placed(board, i, col)) 
        {  
            int new_board[N][N];
            board[i][col] = 1; 
            copy(board, new_board);
            #pragma omp task firstprivate(col)
                solve_NQueens(new_board, col + 1); 
            board[i][col] = 0;
        }
    }
    return SOLUTION_EXISTS; 
}

main中对该函数的初始调用是：

    #pragma omp parallel if(omp_get_num_threads() > 1)
    {
        #pragma omp single
        {
            #pragma omp taskgroup
            {
                solve_NQueens(board, 0);
            }
        }
    }

参数：

// these are global
#define N 14
bool SOLUTION_EXISTS = false;
// these are in main
int board[N][N]; 
memset(board, 0, sizeof(board));

编译器：

gcc

线程数：4

在得到结果之前，我使用taskgroup等待所有任务，并且我必须为每个任务复制游戏板(当N设置为14时，这是一项艰巨的工作，因为有356k个解决方案(。

我试着制作firstprivate或private板，在循环内外使用taskwait，在for循环内部使用taskgroup等等。我需要一些建议来优化这个逻辑。

注意：在if子句下的for循环中放入taskgroup也有帮助，但这比预期的要慢得多。

Answer 1

首先，您的代码中存在一个巨大的问题：solve_NQueens可以递归地提交任务，并且在所有任务实际完成之前返回。您需要在return之前放置同步，以便SOLUTION_EXISTS的值有效(使用#pragma omp taskwait或#pragma omp taskgroup(。

在性能方面，存在多个问题。

主要的问题是创建了太多的任务：您在每个递归调用中创建一个任务。虽然创建很少的任务会带来所需的并行性，但对其中大部分任务的创建也会带来很大的开销。这个开销可能比执行尾部调用要高得多。可以实现截止策略来减少开销：一般想法是只为第一次递归调用创建任务。在您的情况下，可以使用#pragma omp task末尾的子句if(col < 3)来完成此操作。请注意，3是一个任意值，您可能需要调整此阈值。

此外，board在任务创建期间被复制(两次((因为它是一个静态数组，OpenMP任务所需的默认变量被隐式复制(。如果代码是使用OpenMP支持编译的，则不需要额外的副本，并且行board[i][col] = 0;是无用的*(否则将忽略pragma，这是而不是true*(。但是，如果您解决了上述问题，那么引入的额外开销应该不是关键的。