c++ - 如何优化 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 对此很有帮助)。然后可以将本地字符串附加到一个大的全局字符串，并且可以在主线程中按顺序打印其内容(以防止并行 IO 造成的任何额外开销)和定时部分之外。

除此之外，您有 11 个任务并在代码中为此创建了 30 个线程，而您的内核可能少于 30 个(甚至 30 个硬件线程)。创建太多线程代价高昂(主要是由于线程抢占/调度)。此外，在程序中指定线程数通常是一种不好的做法。为此，请使用可移植环境变量 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 上执行线程局部缩减，并且只使用每个任务一个原子更新。