【文章內(nèi)容簡介】 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。 } 執(zhí)行結(jié)果 截圖 （體現(xiàn)串行時間、并行時間和加速比） （ 1）小數(shù)據(jù)量驗證正確性的執(zhí)行結(jié)果 N = 12 Serial Time = 790 , Parallel Time= 1148 相對加速比 = 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 14 （ 2）大數(shù)據(jù)量獲得較好加速比的執(zhí)行結(jié)果 N = 14 Serial Time = 21436, Parallel Time = 41090 相對加速比 = 遇到的問題及解決方案 （ 1）問題一 錯誤代碼及后果 當數(shù)組 m 維數(shù)為 2 維時，無法避免其他線程對當前線程的影響，各線程存在數(shù)據(jù)競爭，無法準確的描述棋盤放置狀態(tài)。 正確代碼 應(yīng)將數(shù)組設(shè)置為 3 維，第 1 維為 Thread 維 ，避免多線程共同操作同一個棋盤，出現(xiàn)數(shù)據(jù)競爭。 分析 加速比 理想。 班級 __計 1232_ 學號 _20xx58503222_ 姓名 ___王 洋 ___ N 皇后問題 15 基于 Java（ Tread 或者 Runnable）的并行算法實現(xiàn) 代碼及注釋 （ 變量名 名字首字母 開頭 ） //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])。 }