并行计算八皇后问题技巧.doc

并行计算与多核多线程技术 课程报告 班级 __________________ 学号_____________ 姓名 _________________ 2014 年 11 月 26 日 目 录 1. N皇后问题 并行算法设计与实现 1 1.1 功能描述 1 1.1.1功能描述 1 1.1.2 解决方案 1 1.2算法 1 1.2.1 串行 1 1.2.2 并行算法 2 1.2.3 理论加速比分析（选作） 3 1.3 基于OpenMP的并行算法实现 3 1.3.1 代码及注释 3 1.3.2 执行结果截图 7 1.3.3 遇到的问题及解决方案 8 1.4 基于MPI的并行算法实现 9 1.4.1 代码及注释 9 1.4.2 执行结果截图 13 1.4.3 遇到的问题及解决方案 14 1.5 基于Java（Tread或者Runnable）的并行算法实现 15 1.5.1 代码及注释 15 1.5.2 执行结果截图 19 1.5.3 遇到的问题及解决方案 21 1.6 基于Windows（API或MFC或.net）的并行算法实现 21 1.6.1 代码及注释 21 1.6.2 执行结果截图 26 1.6.3 遇到的问题及解决方案 27 1.7 基于Linux（fork或pthread）的并行算法实现 28 1.7.1 代码及注释 28 1.7.2 执行结果截图 32 1.7.3 遇到的问题及解决方案 33 2. 理论基础 34 2.1 并行计算机体系结构、并行计算模型、并行算法的概念 34 2.2并行计算机体系结构、并行计算模型、并行算法的关系 34 2.3实例说明并行计算机体系结构、并行计算模型、并行算法的关系 34  评 价 实践效果（正确度/加速比） 理论基础 难度 工作量 独立性 1. N皇后问题 并行算法设计与实现 1.1 功能描述功能描述八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同 一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。 算法串行/** * wy_serial_listAllCol : List All The Valid Chess Table In Serial Way * * @param m[][][] * @param y */ static void wy_serial_listAllCol(int m[THREADS][QUEENS][QUEENS] , int y) { for(int x = 0; x QUEENS; x++) { m[0][x][y] = 1; if(wy_isOk(m, x, y,0)) { if(y == QUEENS - 1) { //print(m,0); } else wy_serial_listAllCol(m, y+1); } m[0][x][y] = 0; } } 1.2.2 并行算法/** * wy_parallel_listOtherCol : Determine The Other Cols In Parallel Way * * @param m[][][] * @param y * @param thread */ static void wy_parallel_listOtherCol(int m[THREADS][QUEENS][QUEENS] , int y,int thread) { for(int x = 0; x QUEENS; x++) { m[thread][x][y] = 1; if(wy_isOk(m, x, y,thread)) { if(y == QUEENS - 1) { //print(m,omp_get_thread_num()); } else wy_parallel_listOtherCol(m, y+1,thread); } m[thread][x][y] = 0; } } /** * wy_parallel_listFirstCol : Determine The First Col In Parallel Way * * @param m[]