Recursive task creation results in segmentation fault in OpenMP

Question

I am trying to implement a nqueens solver with OpenMP, my serial code works fine but when I try to do task parallelism on that, I get segmentation fault or empty rows/cols.

Here is my implementation:

#define N 8
bool SOLUTION_EXISTS = false; // THIS IS GLOBAL

bool solve_NQueens(int board[N][N], int col) 
{ 

    if (col == N) 
    { 
        #pragma omp critical
            print_solution(board); 
        SOLUTION_EXISTS = true;
        return true; 
    } 

    for (int i = 0; i < N; i++) 
    {  
        if (can_be_placed(board, i, col) ) 
        { 
            #pragma omp taskgroup
            {   
                #pragma omp task private(col) shared(i) firstprivate(board)
                {
                    board[i][col] = 1; 
                    SOLUTION_EXISTS = solve_NQueens(board, col + 1) || SOLUTION_EXISTS; 
                    board[i][col] = 0; 
                }
            }    
        } 
    } 
    return SOLUTION_EXISTS; 
}

And the first call to this function is:

#pragma omp parallel
{
    #pragma omp single
    {
        solve_NQueens(board, 0);
    }
}

When I make col private, it gives a segmentation fault. If I do not put any variable scope, ambiguous and wrong solutions are printed.

And I am using gcc 4.8.5

Answer 1

Solution

There is a segmentation fault because you use private(col). Thus, col is not copied from your function and not even initialized. Use firstprivate(col) to make a proper copy of col.

Advise

omp taskgroup will make your code run in sequential since there is an implicit barrier at the end of the scope. It is probably better to avoid it (eg. by using an omp taskwait at the end of the loop and changing a bit the rest of the code). If you want to change that, please note that i must be copied using a firstprivate rather than shared.

Moreover, avoid using global variables like SOLUTION_EXISTS in a parallel code. This generally cause a lot of issues from vicious bugs to slow codes. And if you still need/want to do it, the variables used in multiple threads must be protected using for example omp atomic or omp critical directives.