如何优化 n-queens OpenMP 并行程序？

Question

我正在使用 OpenMP 并行化 n 皇后问题，但我的顺序程序同样快。我一直在尝试使用 num_threads，但我认为我的做法不正确。

有人可以看看我的代码并告诉我我做错了什么或给我一些指示吗？谢谢。

这是我的并行程序：

// Parallel version of the N-Queens problem.


#include <iostream>  
#include <omp.h>
#include <time.h>
#include <sys/time.h>

// Timing execution
double startTime, endTime;

// Number of solutions found
int numofSol = 0;

// Board size and number of queens
#define N 11

void placeQ(int queens[], int row, int column) {
    
    for(int i = 0; i < row; i++) {
        // Vertical
        if (queens[i] == column) {
            return;
        }
        
        // Two queens in the same diagonal
        if (abs(queens[i] - column) == (row-  i))  {
            return;
        }
    }
    
    // Set the queen
    queens[row] = column;
    
    if(row == N-1) {
        
        #pragma omp atomic 
            numofSol++;  //Placed the final queen, found a solution
        
        #pragma omp critical
        {
            std::cout << "The number of solutions found is: " << numofSol << std::endl; 
            for (int row = 0; row < N; row++) {
                for (int column = 0; column < N; column++) {
                    if (queens[row] == column) {
                        std::cout << "X";
                    }
                    else {
                        std::cout << "|";
                    }
                }
                std::cout  << "\n"  << std::endl; 
            }
        }
    }
    
    else {
        
        // Increment row
        for(int i = 0; i < N; i++) {
            placeQ(queens, row + 1, i);
        }
    }
} // End of placeQ()

void solve() {
    #pragma omp parallel num_threads(30)
    #pragma omp single
    {
        for(int i = 0; i < N; i++) {
            // New task added for first row and each column recursion.
            #pragma omp task
            { 
                placeQ(new int[N], 0, i);
            }
        }
    }
} // end of solve()

int main(int argc, char*argv[]) {

    startTime = omp_get_wtime();   
    solve();
    endTime = omp_get_wtime();
  
    // Print board size, number of solutions, and execution time. 
    std::cout << "Board Size: " << N << std::endl; 
    std::cout << "Number of solutions: " << numofSol << std::endl; 
    std::cout << "Execution time: " << endTime - startTime << " seconds." << std::endl; 
    
    return 0;
}

Answer 1

您的程序执行时间的 95% 多于 用于在控制台中打印 字符串，并且此操作被放入一个 临界区 以便一次只能有一个线程执行此操作。 IO 操作和临界区的开销随着使用的线程数的增加而增加。因此，顺序执行时间优于并行执行时间。

其实更准确地说，不是打印慢，而是与控制台的同步 std::endl 隐式执行了一个std::flush，以及 字符串格式 。因此，要解决此问题，您可以 并行准备一个线程本地字符串 （std::ostringstream 对此有好处）。然后可以将本地字符串附加到一个大的全局字符串，并且可以在主线程中按顺序打印其内容（以防止并行 IOs 造成的任何额外开销）和定时部分之外。

除此之外，您有 11 个任务并在代码中为此创建了 30 个线程，而您的内核可能少于 30 个（甚至 30 个硬件线程）。创建太多线程的成本很高（主要是由于 thread-preemption/scheduling）。此外，在程序中指定线程数通常是一种不好的做法。为此，请使用可移植环境变量OMP_NUM_THREADS。

下面是考虑到上述评论的代码：

// Parallel version of the N-Queens problem.

#include <iostream>  
#include <omp.h>
#include <time.h>
#include <sys/time.h>
#include <sstream>

// Timing execution
double startTime, endTime;

// Number of solutions found
int numofSol = 0;

std::ostringstream globalOss;

// Board size and number of queens
#define N 11

void placeQ(int queens[], int row, int column) {
    
    for(int i = 0; i < row; i++) {
        // Vertical
        if (queens[i] == column) {
            return;
        }
        
        // Two queens in the same diagonal
        if (abs(queens[i] - column) == (row-  i))  {
            return;
        }
    }
    
    // Set the queen
    queens[row] = column;
    
    if(row == N-1) {
        
        #pragma omp atomic 
            numofSol++;  //Placed the final queen, found a solution
        
        std::ostringstream oss;
        oss << "The number of solutions found is: " << numofSol << std::endl; 
        for (int row = 0; row < N; row++) {
            for (int column = 0; column < N; column++) {
                if (queens[row] == column) {
                    oss << "X";
                }
                else {
                    oss << "|";
                }
            }
            oss  << std::endl << std::endl; 
        }

        #pragma omp critical
        globalOss << oss.str();
    }
    
    else {
        
        // Increment row
        for(int i = 0; i < N; i++) {
            placeQ(queens, row + 1, i);
        }
    }
} // End of placeQ()

void solve() {
    #pragma omp parallel //num_threads(30)
    #pragma omp single
    {
        for(int i = 0; i < N; i++) {
            // New task added for first row and each column recursion.
            #pragma omp task
            { 
                placeQ(new int[N], 0, i);
            }
        }
    }
} // end of solve()

int main(int argc, char*argv[]) {

    startTime = omp_get_wtime();   
    solve();
    endTime = omp_get_wtime();

    std::cout << globalOss.str();
  
    // Print board size, number of solutions, and execution time. 
    std::cout << "Board Size: " << N << std::endl; 
    std::cout << "Number of solutions: " << numofSol << std::endl; 
    std::cout << "Execution time: " << endTime - startTime << " seconds." << std::endl; 
    
    return 0;
}

以下是我机器上的最终执行时间：

Time of the reference implementation (30 threads): 0.114309 s

Optimized implementation:
1 thread: 0.018634 s (x1.00)
2 thread: 0.009978 s (x1.87)
3 thread: 0.006840 s (x2.72)
4 thread: 0.005766 s (x3.23)
5 thread: 0.004941 s (x3.77)
6 thread: 0.003963 s (x4.70)

如果您想要更快的并行代码，您可以：

向 OpenMP 提供一些 更多任务（以改进工作 负载平衡），但不要太多（由于每个任务的开销）；
减少（隐式）分配的数量；
在 numofSol 上执行线程局部缩减，并且每个任务仅使用 一个原子更新。

如何优化 n-queens OpenMP 并行程序？

How to optimize a n-queens OpenMP parallel program?

c++

parallel-processing

performance

openmp

n-queens