并行计算八皇后问题

并行计算与多核多线程技术课程报告班级__________________学号_____________姓名_________________2014年11月26日目录1.N皇后问题并行算法设计与实现.....................................................................................................11.1功能描述与解决方案................................................................................................................11.1.1功能描述..........................................................................................................................11.1.2解决方案.........................................................................................................................11.2算法设计.....................................................................................................................................11.2.1串行算法设计.................................................................................................................11.2.2并行算法设计.................................................................................................................21.2.3理论加速比分析（选作）.............................................................................................31.3基于OpenMP的并行算法实现...............................................................................................31.3.1代码及注释（变量名名字首字母开头）.................................................................31.3.2执行结果截图（体现串行时间、并行时间和加速比）.............................................71.3.3遇到的问题及解决方案.................................................................................................81.4基于MPI的并行算法实现.......................................................................................................91.4.1代码及注释（变量名名字首字母开头）.................................................................91.4.2执行结果截图（体现串行时间、并行时间和加速比）...........................................131.4.3遇到的问题及解决方案...............................................................................................141.5基于Java（Tread或者Runnable）的并行算法实现...........................................................151.5.1代码及注释（变量名名字首字母开头）...............................................................151.5.2执行结果截图（体现串行时间、并行时间和加速比）...........................................191.5.3遇到的问题及解决方案...............................................................................................211.6基于Windows（API或MFC或.net）的并行算法实现......................................................211.6.1代码及注释（变量名名字首字母开头）...............................................................211.6.2执行结果截图（体现串行时间、并行时间和加速比）...........................................261.6.3遇到的问题及解决方案...............................................................................................271.7基于Linux（fork或pthread）的并行算法实现...................................................................281.7.1代码及注释（变量名名字首字母开头）...............................................................281.7.2执行结果截图（体现串行时间、并行时间和加速比）...........................................321.7.3遇到的问题及解决方案...............................................................................................332.理论基础............................................................................................................................................342.1并行计算机体系结构、并行计算模型、并行算法的概念..................................................342.2并行计算机体系结构、并行计算模型、并行算法的关系...................................................342.3实例说明并行计算机体系结构、并行计算模型、并行算法的关系...................................34评价实践效果（正确度/加速比）理论基础难度工作量独立性11.N皇后问题并行算法设计与实现1.1功能描述与解决方案1.1.1功能描述八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。1.1.2解决方案1、此题有多重解法，常见解法有残卷法（即穷举法，但时间复杂度和空间复杂度均为N^N，并不高效）和递归+回溯算法（本次采用此算法）。2、判断当前放置的皇后“安全”的依据为同行、同列、对角线-\、对角线-/的遍历结果均为TRUE即没有不满足问题条件的皇后存在。3、第一个线程从第一列第一行的坐标开始放置皇后，其他线程从其他列第一行的元素开始递归放置皇后，每放置一个皇后，判断其是否安全，若“安全”则继续在当前列和（当前行+1）处放置下一个皇后，若不安全则将当前皇后坐标设为0。4、采用三维数组m[THREAD][QUEENS][QUEENS]来存放棋盘的放置状态，第一维用于保证各线程不会影响其他线程的放置状态，第二、三维用来确定棋盘的规格。1.2算法设计1.2.1串行算法设计/***wy_serial_listAllCol:ListAllTheValidChessTableInSerialWay**@paramm[][][]*@paramy*/staticvoidwy_serial_listAllCol(intm[THREADS][QUEENS][QUEENS],inty){for(intx=0;xQUEENS;x++){m[0][x][y]=1;if(wy_isOk(m,x,y,0)){if(y==QUEENS-1){//print(m,0);}elsewy_serial_listAllCol(m,y+1);}2m[0][x][y]=0;}}1.2.2并行算法设计OpenMP使用parallelfor来调用listFirstCol()函数，listFirstCol再递归调用listSecondCol()函数来实现各线程并行递归回溯其他语言使用并行区域的办法来保证各线程并行递归回溯/***wy_parallel_listOtherCol:DetermineTheOtherColsInParallelWay**@paramm[][][]*@paramy*@paramthread*/staticvoidwy_parallel_listOtherCol(intm[THREADS][QUEENS][QUEENS],inty,intthread){for(intx=0;xQUEENS;x++){m[thread][x][y]=1;if(wy_isOk(m,x,y,thread)){if(y==QUEENS-1){//print(m,omp_get_thread_num());}elsewy_parallel_listOtherCol(m,y+1,thread);}m[thread][x][y]=0;}}/***wy_parallel_listFirstCol:DetermineTheFirstColInParallelWay**@paramm[][][]*@paramy*/staticvoidwy_parallel_listFirstCol(intm[THREADS][QUEENS][QUEENS],inty){#pragmaompparallelforfor(intx=0;xQUEENS;x++){//printf(thread_num%d\n,omp_get_thread_num());m[omp_get_thread_num()][x][y]=1;if(wy_isOk(m,x,y,omp_get_thread_num())){3wy_