如何使用 openmp - C 优化 N-queen

Question

我正在学习 OpenMP 并找到以下代码来解决 N-Queens 问题。我想用并行代码做出更快的解决方案，但我不知道该怎么做。每次我尝试一些东西，它只会变得更糟和更慢的解决方案。

这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

#define BOARD_SIZE 15

int board[20],solutions;
 
int main() {
  double start_time, end_time, result_time;
  void queen(int row,int n);

  start_time = omp_get_wtime();

  queen(1, BOARD_SIZE);

  end_time = omp_get_wtime();
    result_time = end_time - start_time;
    printf("Time = %.3f seconds\n", result_time);
  printf("Number of solutions: %d\n", solutions);
  return 0;
}
  
/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row, int column) {
  for(int i=1;i<=row-1;++i) {
    //checking column and diagonal conflicts
    if(board[i]==column)
      return 0;
    else
      if(abs(board[i]-column)==abs(i-row))
      return 0;
  }
  
  return 1; //no conflicts
}
 
//function to check for proper positioning of queen
void queen(int row,int n) {
  for(int column=1;column<=n;++column) {
    if(place(row,column)) {
    board[row]=column; //no conflicts so place queen
    if(row==n) //dead end
      solutions++;
    else //try queen with next position
      queen(row+1,n);
    }
  }
}

如何优化此代码？

Answer 1

我在你的代码中没有看到 omp 指令。
正如 Jerome 所建议的，执行此操作的方法是使用任务。
我刚才编码了这个。下载my textbook and see the chapter with OMP examples (or html version。该解决方案使用 taskloop 和 omp cancel taskloop.
不幸的是，您没有得到任何加速：顺序代码找到第一个解决方案的速度非常快，而并行并不会使其更快。
哦，抱歉，这个用的是C++。我确信 C 的翻译很简单。但是现在 C++ 是一种更好的语言。

Answer 2

为了将您的代码与 OpenMP 并行化，我执行了以下操作：

我在第一次调用函数 queen 之前添加了 #pragma omp parallel 和 #pragma omp single。
为了避免数据竞争，我在 solutions++; 之前添加了 #pragma omp atomic（请注意，我也尝试过使用缩减，但在那种情况下必须同步任务，这使得它成为一个较慢的选项）。
为了进行并行递归调用，我必须创建板的（私有）副本（并将其指针传递给函数 queen）。我使用 #pragma omp task if(row<4) 创建任务。注意if(row<4)用于限制创建的任务数。

在 8 个内核上测得的加速比约为 6 倍。

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

#define BOARD_SIZE 15

int solutions;

int main() {
  double start_time, end_time, result_time;
  int board[BOARD_SIZE+1];
  void queen(int row,int n, int*);

  
    start_time = omp_get_wtime();

    #pragma omp parallel
    #pragma omp single
    queen(1, BOARD_SIZE, board);

    end_time = omp_get_wtime();
        result_time = end_time - start_time;
        printf("Time = %.3f seconds\n", result_time);
    printf("Number of solutions: %d\n", solutions);
  
  return 0;
}
  
/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row, int column, int* board) {
  for(int i=1;i<=row-1;++i) {
    //checking column and diagonal conflicts
    if(board[i]==column)
      return 0;
    else
      if(abs(board[i]-column)==abs(i-row))
      return 0;
  }  
  return 1; //no conflicts
}
 
//function to check for proper positioning of queen
void queen(int row,int n, int* board) {
  for(int column=1;column<=n;++column) {
    if(place(row,column, board)) { 
        if(row==n) //dead end
        {
            #pragma omp atomic
            solutions++;
        }        
        else
        //try queen with next position
        {
            int local_board[BOARD_SIZE+1];
            for(int i=1;i<row;i++) local_board[i]=board[i];  //copy board to local_board
            local_board[row]=column; //no conflicts so place queen            
            #pragma omp task if(row<4)
            queen(row+1,n, local_board);
        }
    }
  }
}

如需更多说明，请注明。

如何使用 openmp - C 优化 N-queen

How to optimize N-queen with openmp - C

c

performance

optimization

openmp

n-queens