c++ - 如何优化 n-queens OpenMP 并行程序?
问题描述
我正在使用 OpenMP 并行化 n-queens 问题,但我的顺序程序同样快。我一直在尝试使用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;
}
解决方案
超过 95%的程序执行时间都花在了在控制台打印字符串上,并且这个操作被放在了一个临界区,这样一次只有一个线程可以执行它。IO 操作和临界区的开销随着使用的线程数而增长。因此,顺序执行时间优于并行执行时间。
其实,更准确的说,慢的不是打印,而是隐式执行 a和字符串格式化导致的与控制台的同步。因此,要解决这个问题,您可以并行准备一个线程本地字符串(对此有好处)。然后可以将本地字符串附加到一个大的全局字符串中,并且可以在主线程中顺序打印其内容(以防止由并行 IO 引起的任何额外开销)和定时部分之外。std::endl
std::flush
std::ostringstream
除此之外,您有 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
并仅使用一个原子更新。
推荐阅读
- typescript - 如何在 TypeScript 构建中包含整个文件夹?
- angular - TS2564 属性 mapViewEl 没有初始化器
- python-3.x - 绘制多个同心三角形和极坐标图,圆圈内的圆圈
- assembly - NASM 简单引导加载程序不会使用 INT 13H 加载扇区
- node.js - 复制失败:尝试在 DigitalOcean Droplet 上的 Docker 中复制 package.json 文件时的状态
- flask - discord-oauth 和烧瓶(夸脱)set-cookie 失败
- c# - UWP: 0x80131040: 定位程序集的清单定义与程序集引用不匹配
- database - 如何使用 pandas 在此 Dataframe 中找到唯一值?
- python - 检查文本文件中的单词是否存在于第二个文本文件中太慢了
- cytoscape.js - 在 Cytoscape.js 中的节点内动态显示另一个图形