【正文】 三維數(shù)組 m[THREAD][QUEENS][QUEENS]來存放棋盤的放置狀態(tài)，第一維用于保 證各線程不會影響其他線程的放置狀態(tài)，第二、三維用來確定棋盤的規(guī)格。 if(wy_isOk(m, x, y,0)) { if(y == QUEENS 1) { //print(m,0)。 x QUEENS。 } m[thread][x][y] = 0。 m[omp_get_thread_num()][x][y] = 1。 因為最多允許 N 個線程同時運行。ty++) { if(m[thread][x][ty] == 1)return false。amp。 while(++tx QUEENS amp。 } /** * count : Current Count */ static int count = 1。 i QUEENS 。 } printf(\n)。 if(wy_isOk(m, x, y,0)) { if(y == QUEENS 1) { //print(m,0)。 x QUEENS。 } m[thread][x][y] = 0。 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 6 m[omp_get_thread_num()][x][y] = 1。 /* Parallel Part */ omp_set_num_threads(THREADS)。 i++) { for (int j = 0。 z++) { m[i][j][z] = 0。 printf(N QUEEN : N = %d\n,QUEENS)。 i THREADS。 z QUEENS。 float st = t2 t1。 return 0。 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 9 基于 MPI 的并行算法實現(xiàn) 代碼及注釋 （ 變量名 名字首字母 開頭 ） //YTU Wang Yang 1232 20xx58503222 MPI NQUEEN include define QUEENS 8 /* QUEENS NUM *//* 8 QUEENS HAVE 92 RES */ define THREADS 2 /* THREADS TOTAL NUM */ /** * wy_isOk : Check The Current Queen Site Validity * * param x * param y * return boolvalue */ static bool wy_isOk(int m[THREADS][QUEENS][QUEENS],int x,int y,int thread) { int tx,ty。 } /* Same col , impossible */ /* Diagonal \ , return false */ tx = x。 ty = 0) { if(m[thread][tx][ty] == 1)return false。amp。 /** * print : Print Current Finished Chess Table * * param m[][][] * param thread */ static void print(int m[THREADS][QUEENS][QUEENS],int thread) { printf(%d\n,count)。 i++) { for(int j = 0 。 } } /** * 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。 } else wy_serial_listAllCol(m, y+1)。 x++) { m[thread][x][y] = 1。 } } /** * 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 (wy_isOk(m , x , y , thread)) { wy_parallel_listOtherCol(m , y+1 , thread)。 x++) { m[thread][x][y] = 1。 /* Parallel Part */ int n = 0, done = 0。argc , amp。 MPI_Comm_rank(MPI_COMM_WORLD,amp。 i++) { for (int j = 0。 z++) { m[i][j][z] = 0。 if(n == 0) { done = 1。 /* Finish MPI */ double pt = t2 t1。 for (int i = 0。 j++) { for (int z = 0。 t2 = clock()。 system(pause)。 分析 加速比 理想。 /* THREADS TOTAL NUM */ private static int[][][] m = new int[THREADS][QUEENS][QUEENS]。 public NQueens(int threadNum ){ = threadNum。ty++) { if(m[thread][x][ty] == 1)return false。amp。 while(++tx QUEENS amp。 } /** * count : Current Count */ private static int count = 1。 i QUEENS。 } ()。 if(wy_isOk(m, x, y,0)) { if(y == QUEENS 1) { //print(m,0)。 if(thread == 0){ for (int x = 0 。 } m[thread][x][y] = 0。 if (wy_isOk(m , x , y , thread)) { wy_parallel_listOtherCol(y+1 , thread)。 /* Serial Part */ for (int i = 0。 j++) { for(int z = 0 。 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 18 wy_serial_listAllCol(0)。 (相對加速比 = + (double)st/pt + \n)。 if(wy_isOk(m , x , y , thread)) { if(y == QUEENS 1) { if(x == QUEENS 1){ t2 = ()。 } } Override public void run() { if( == 0){ wy_parallel_listFirstCol(0 , 0)。 i THREADS。 z QUEENS 。 NQueens eq2 = new NQueens(1)。 ()。 正確代碼 應(yīng)將數(shù)組設(shè)置為 3 維，第 1 維為 Thread 維 ，避免多線程共同操作同一個棋盤，出現(xiàn)數(shù)據(jù)競爭。 using 。 namespace NQueen { class NQueens { private static int QUEENS = 12。 /* Construct Func */ public NQueens(int threadNum){ = threadNum。ty++) { if(m[thread,x,ty] == 1)return false。amp。 while(++tx QUEENS amp。 } /** * count : Current Count */ private static int count = 1。 i QUEENS。 } ()。 if(wy_isOk(m, x, y,0)) { if(y == QUEENS 1) { //print(m,0)。 if(thread == 0){ for (int x = 0 。 } m[thread,x,y] = 0。 if (wy_isOk(m , x , y , thread)) { wy_parallel_listOtherCol(y+1 , thread)。 x++) { m[thread,x,y] = 1。 } } /* Have To No Parameters */ public void runThread() { 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 25 if(threadNum == 0){ wy_parallel_listFirstCol(0 , 0)。 i THREADS。 z QUEENS。 Thread thread1 = new Thread(delegete1)。 ()。 ()。 (Parallel Time = + (pt))。 j QUEENS。 } } } ()。 long st = (long)。 } } } 執(zhí)行結(jié)果 截圖 （體現(xiàn)串行時間、并行時間和加速比） （ 1）小數(shù)據(jù)量驗證正確性的執(zhí)行結(jié)果 N = 12 Serial Time = 1429 , Parallel Time = 3734 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 27 相對加速比 = （ 2） 大數(shù)據(jù)量獲得較好加速比的執(zhí)行結(jié)果 N = 14 Serial Time = 55851 , Parallel Time = 151356 相對加速比 = 遇到的問題及解決方案 （