使用OpenMP语言优化N皇后问题求解过程
摘要： 随着计算机技术向多处理器以及多核的架构发展,以OpenMP和线程构建模块(thread building blocking, TBB)为代表的多核处理器并行计算平台的应用得到重视。本文主要介绍了多核环境下OpenMp的多线程编程模型，并用OpenMP语言对N皇后算法进行优化，在一定程度上提高了N皇后问题在多核环境下的求解效率。 关键字：OpenMP，多核，并行计算，多线程，N皇后
引言
随着计算机硬件设施的不断更新换代，多核处理器已经成为主流。但是，如果用户的应用软件无法利用多个处理器，就会造成CPU资源的极大浪费。因为在主频、Cache等其他条件完全相同的条件下，没有针对多核优化的程序在多核CPU上运行的速度与它在单核CPU上运行的速度并不会有他打差别。实际上，该程序仅仅利用了多核处理器中的一个处理核心。采用多线程技术是提高资源利用率的一个有效方法，在单核处理器时代,应用程序已经支持多线程技术，然后，单核内的多线程是串行的，即并发执行，在某一时刻，只有一段代码被CPU执行，并不能真正做到并行执行。在多核平台上，各个线程都是在相互独立的运行，如果线程数目小于等于CPU数目，那么各线程在运行时相互之间不存在对CPU资源的竞争，在某一时刻，可以有多个线程在同时运行，达到真正意义上的并行处理。本文将以N皇后算法为例，对多核环境下采用OpenMP多线程编程技术进行探讨。
1. OpenMP多线程编程 1.1. 简介
OpenMP是由OpenMP Architecture Review Board牵头提出的，并已被广泛接受的，用
于共享内存并行系统的多线程程序设计的一套指导性注释(Compiler Directive)。OpenMP支持的编程语言包括C语言、C++和Fortran；而支持OpenMP的编译器包括Sun Compiler，GNU Compiler和Intel Compiler等。OpenMP提供了对并行算法的高层的抽象描述，程序员通过在源代码中加入专用的pragma来指明自己的意图，由此编译器可以自动将程序进行并行化，并在必要之处加入同步互斥以及通信。当选择忽略这些pragma，或者编译器不支持OpenMP时，程序又可退化为通常的程序(一般为串行)，代码仍然可以正常运作，只是不能
1
利用多线程来加速程序执行。
OpenMP提供的这种对于并行描述的高层抽象降低了并行编程的难度和复杂度，这样程
序员可以把更多的精力投入到并行算法本身，而非其具体实现细节。对基于数据分集的多线程程序设计，OpenMP是一个很好的选择。同时，使用OpenMP也提供了更强的灵活性，可以较容易的适应不同的并行系统配置。线程粒度和负载平衡等是传统多线程程序设计中的难题，但在OpenMP中，OpenMP库从程序员手中接管了部分这两方面的工作。
但是，作为高层抽象，OpenMP并不适合需要复杂的线程间同步和互斥的场合。OpenMP
的另一个缺点是不能在非共享内存系统(如计算机集群)上使用。在这样的系统上，MPI使用较多。
1.2. OpenMP 的基本使用
要在Visual C++2005 中使用OpenMP其实不难，只要将 Project 的Properties中
C/C++里Language的OpenMP Support开启（参数为 /openmp），就可以让VC++2005 在编译时支持OpenMP 的语法了；而在编写使用OpenMP 的程序时，则需要先include OpenMP的头文件：omp.h。
而要将 for 回圈平行化处理，该怎么做呢？非常简单，只要在前面加上一行
#pragma omp parallel for.
2. N皇后问题 1.1. 问题描述
N皇后问题是八皇后问题的一个扩展。八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。
1.2. 串行算法实现
N皇后问题的求解过程是回溯算法的典型例题，所以本文用回溯法实现N皇后问题的串行算法。假设在n×n棋盘前i-1行已经放置了互不攻击的i-1个棋子，在第i行第j(j从1到n)列放置一个棋子，判断此时棋盘是否合法，即是否棋盘上的棋子互不攻击。如果合法
2
且i不是最后一行，则递归调用solve函数，进入下一行的放置棋子的过程；如果合法且i已经是最后一行了（即i==n-1）,则找到一个合法的棋盘布局，标识符find设置为true，程序跳出递归过程；如果当前棋盘不合法，则剪掉该子树分支，然后j+1,进入下一列的判断。
/*回溯函数，n表示一共几行几列*/ bool solve(int* x, int n) {
int k = 1; /*从第二行开始搜索*/ x[1] = -1;
/*当搜索到答案时，退出*/ while(k>0&&!resultfind) {
x[k]+=1;
while((x[k] x[k]+=1; } if(x[k] if(k == n-1) { resultfind = true; return true; } else { k++; x[k] = -1; } } else { k--; } } return false; } 1.3. 使用OpenMP对N皇后问题进行优化 如果我们现在使用OpenMP对N皇后问题进行优化，则可以提高一定的工作效率。并行执行的思想是这样的：我们用一个线程在第1行第1列放置一个棋子，然后仿照1.2串行算 3 法往下放置其他几行的棋子；再用第二线程在第1行第2列放置一个棋子，然后仿照1.2串行算法往下放置其他几行的棋子...。如此，则对N皇后问题分为多个线程同时求解。当其中有一个线程找到一个合法棋盘布局，则设置公共变量other_process_find为true,其他一旦检测到这个变量为true时，立即跳出递归过程。以八皇后问题为例，假设有8个线程共通求解。则第i个线程可以在第1行第i列放置一个棋子，然后往下执行回溯算法求解。在OpenMP编程环境中各个线程进行任务的划分，可以使用#pragma omp parallel for预编译指令，该指令可以用来将一个for循环分配到多个线程中执行。 #include #include bool resultfind = false; /*能否在当前位置放置一个皇后，a表示当前行*/ bool canput(int* x, int a) { for(int i=0;i if(x[i]==x[a] || x[i]+i==x[a]+a || x[i]-i==x[a]-a) { return false; } } return true; } /*回溯函数，n表示一共几行几列*/ bool solve(int* x, int n) { int k = 1; /*从第二行开始搜索*/ x[1] = -1; /*当搜索到答案时，退出*/ while(k>0&&!resultfind) { x[k]+=1; while((x[k] x[k]+=1; } 4 if(x[k] if(k == n-1) { resultfind = true; return true; } else { k++; x[k] = -1; } } else { k--; } } return false; } void nQueens(int* x, int n) { resultfind = false; #pragma omp parallel for for(int i=0; i int* y = new int[n]; /*第行的皇后所在列为i*/ y[0] = i; if(solve(y, n)){ /*拷贝最终结果到x数组*/ for(int j=0; j } delete[] y; } } 5