并行计算课程报告-n皇后问题(编辑修改稿)

并行计算课程报告-n皇后问题(编辑修改稿)内容摘要：

tic void print(int m[THREADS][QUEENS][QUEENS],int thread) { printf(%d\n,count)。 count++。 for(int i = 0。 i QUEENS。 i++) { for(int j = 0。 j QUEENS。 j++) { printf( %d,m[thread][i][j])。 } printf(\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。 } } 班级 __计 1232_ 学号 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后问题 11 /** * 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,thread)。 } 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[][][] * @param y */ static void wy_parallel_listFirstCol(int m[THREADS][QUEENS][QUEENS] , int y ,int thread) { int floorLength = int(floor(double(QUEENS / 2) ))。 if(thread == 0){ for (int x = 0。 x floorLength。 x++) { m[thread][x][y] = 1。 if (wy_isOk(m , x , y , thread)) { wy_parallel_listOtherCol(m , y+1 , thread)。 } m[thread][x][y] = 0。 } } else { for (int x = floorLength。 x QUEENS。 x++) { m[thread][x][y] = 1。 if (wy_isOk(m , x , y , thread)) { wy_parallel_listOtherCol(m , y+1 , thread)。 班级 __计 1232_ 学号 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后问题 12 } m[thread][x][y] = 0。 } } } int _tmain(int argc, char* argv[]) { int m[THREADS][QUEENS][QUEENS]。 /* Parallel Part */ int n = 0, done = 0。 int thread , size。 double t1 , t2。 MPI_Init(amp。 argc , amp。 argv)。 /* Init MPI */ MPI_Comm_size(MPI_COMM_WORLD,amp。 size)。 MPI_Comm_rank(MPI_COMM_WORLD,amp。 thread)。 for (int i = 0。 i THREADS。 i++) { for (int j = 0。 j QUEENS。 j++) { for (int z = 0。 z QUEENS。 z++) { m[i][j][z] = 0。 } } } while(!done){ if(thread == 0) { t1 = clock()。 } MPI_Bcast(amp。 n , 1 , MPI_INT , 0 , MPI_COMM_WORLD)。 if(n == 0) { done = 1。 } wy_parallel_listFirstCol(m , 0 , thread)。 if(n == 0) t2 = clock()。 } MPI_Finalize()。 /* Finish MPI */ double pt = t2 t1。 printf(N QUEEN : N = %d\n,QUEENS)。 printf(Parallel Time = %f\n,t2)。 班级 __计 1232_ 学号 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后问题 13 /* Serial Part */ t1 = clock()。 for (int i = 0。 i THREADS。 i++) { for (int j = 0。 j QUEENS。 j++) { for (int z = 0。 z QUEENS。 z++) { m[i][j][z] = 0。 } } } wy_serial_listAllCol(m, 0)。 t2 = clock()。 double st = t2 t1。 printf(Serial Time = %f\n,st)。 printf(相对加速比 = %f\n,st/pt)。 system(pause)。 return 0。 } 执行结果 截图 （体现串行时间、并行时间和加速比） （ 1）小数据量验证正确性的执行结果 N = 12 Serial Time = 790 , Parallel Time= 1148 相对加速比 = 班级 __计 1232_ 学号 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后问题 14 （ 2）大数据量获得较好加速比的执行结果 N = 14 Serial Time = 21436, Parallel Time = 41090 相对加速比 = 遇到的问题及解决方案 （ 1）问题一 错误代码及后果 当数组 m 维数为 2 维时，无法避免其他线程对当前线程的影响，各线程存在数据竞争，无法准确的描述棋盘放置状态。 正确代码 应将数组设置为 3 维，第 1 维为 Thread 维 ，避免多线程共同操作同一个棋盘，出现数据竞争。 分析 加速比 理想。 班级 __计 1232_ 学号 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后问题 15 基于 Java（ Tread 或者 Runnable）的并行算法实现 代码及注释 （ 变量名 名字首字母 开头 ） //YTU Wang Yang 1232 20xx58503222 JavaRunnable NQUEEN package。 public class NQueens implements Runnable { private static int QUEENS = 8。 /* QUEENS NUM *//* 8 QUEENS HAVE 92 RES */ private static int THREADS = 2。 /* THREADS TOTAL NUM */ private static int[][][] m = new int[THREADS][QUEENS][QUEENS]。 private static long t1。 private static long t2。 private int threadNum。 public NQueens(int threadNum ){ = threadNum。 } /** * wy_isOk : Check The Current Queen Site Validity * * @param m[][][] * @param x * @param y * @return booleanvalue */ public static boolean wy_isOk(int[][][] m, int x, int y,int thread) { int tx, ty。 /* Same row , return false */ for(ty = 0。 ty y。 ty++) { if(m[thread][x][ty] == 1)return false。 } /* Same col , impossible */ /* Diagonal \ , return false */ tx = x。 ty = y。 while(tx = 0 amp。 amp。 ty = 0) { if(m[thread][tx][ty] == 1)return false。 } 班级 __计 1232_ 学号 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后问题 16 /* Diagonal / , return false */ tx = x。 ty = y。 while(++tx QUEENS amp。 amp。 ty = 0) { if(m[thread][tx][ty] == 1)return false。 } return true。 } /** * count : Current Count */ private static int count = 1。 /** * print : Print Current Finished Chess Table * * @param m[][][] * @param thread */ public static void print(int[][][] m , int thread) { ( + count + Threadnum +thread)。 count++。 for (int i = 0。 i QUEENS。 i++) { for (int j = 0。 j QUEENS。 j++) { ( + m[thread][i][j])。 }。