并行計(jì)算課程報(bào)告-N皇后問題

1、并行計(jì)算與多核多線程技術(shù)課程報(bào)告班級(jí) _計(jì)123-2_學(xué)號(hào) _2_姓名 _王 洋_ 2014 年 11 月 26 日目 錄1. N皇后問題 并行算法設(shè)計(jì)與實(shí)現(xiàn)11.1 功能描述與解決方案11.1.1功能描述11.1.2 解決方案11.2算法設(shè)計(jì)11.2.1 串行算法設(shè)計(jì)11.2.2 并行算法設(shè)計(jì)21.2.3 理論加速比分析（選作）31.3 基于OpenMP的并行算法實(shí)現(xiàn)31.3.1 代碼及注釋（變量名 名字首字母 開頭）31.3.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）71.3.3 遇到的問題及解決方案81.4 基于MPI的并行算法實(shí)現(xiàn)91.4.1 代碼及注釋（變量名 名字首字母 開

2、頭）91.4.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）131.4.3 遇到的問題及解決方案141.5 基于Java（Tread或者Runnable）的并行算法實(shí)現(xiàn)151.5.1 代碼及注釋（變量名 名字首字母 開頭）151.5.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）191.5.3 遇到的問題及解決方案211.6 基于Windows（API或MFC或.net）的并行算法實(shí)現(xiàn)211.6.1 代碼及注釋（變量名 名字首字母 開頭）211.6.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）261.6.3 遇到的問題及解決方案271.7 基于Linux（fork或pthread

3、）的并行算法實(shí)現(xiàn)281.7.1 代碼及注釋（變量名 名字首字母 開頭）281.7.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）321.7.3 遇到的問題及解決方案332. 理論基礎(chǔ)342.1 并行計(jì)算機(jī)體系結(jié)構(gòu)、并行計(jì)算模型、并行算法的概念342.2并行計(jì)算機(jī)體系結(jié)構(gòu)、并行計(jì)算模型、并行算法的關(guān)系342.3實(shí)例說明并行計(jì)算機(jī)體系結(jié)構(gòu)、并行計(jì)算模型、并行算法的關(guān)系34評(píng) 價(jià)實(shí)踐效果（正確度/加速比）理論基礎(chǔ)難度工作量獨(dú)立性1. N皇后問題 并行算法設(shè)計(jì)與實(shí)現(xiàn)1.1 功能描述與解決方案1.1.1功能描述八皇后問題是十九世紀(jì)著名數(shù)學(xué)家高斯于1850年提出的。問題是：在8*8的棋盤上擺放8個(gè)皇后

4、，使其不能互相攻擊，即任意的兩個(gè)皇后不能處在同意行，同 一列，或同意斜線上?？梢园寻嘶屎髥栴}拓展為n皇后問題，即在n*n的棋盤上擺放n個(gè)皇后，使其任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。1.1.2 解決方案1、此題有多重解法，常見解法有殘卷法（即窮舉法，但時(shí)間復(fù)雜度和空間復(fù)雜度均為NN，并不高效）和遞歸+回溯算法（本次采用此算法）。2、判斷當(dāng)前放置的皇后“安全”的依據(jù)為同行、同列、對(duì)角線-、對(duì)角線-/的遍歷結(jié)果均為TRUE即沒有不滿足問題條件的皇后存在。3、第一個(gè)線程從第一列第一行的坐標(biāo)開始放置皇后，其他線程從其他列第一行的元素開始遞歸放置皇后，每放置一個(gè)皇后，判斷其是否安全，若“安

5、全”則繼續(xù)在當(dāng)前列和（當(dāng)前行+1）處放置下一個(gè)皇后，若不安全則將當(dāng)前皇后坐標(biāo)設(shè)為0。4、采用三維數(shù)組mTHREADQUEENSQUEENS來存放棋盤的放置狀態(tài)，第一維用于保證各線程不會(huì)影響其他線程的放置狀態(tài)，第二、三維用來確定棋盤的規(guī)格。1.2算法設(shè)計(jì)1.2.1 串行算法設(shè)計(jì)/* * wy_serial_listAllCol : List All The Valid Chess Table In Serial Way * * param m * param y */static void wy_serial_listAllCol(int mTHREADSQUEENSQUEENS , int y

6、) for(int x = 0; x QUEENS; x+) m0xy = 1;if(wy_isOk(m, x, y,0) if(y = QUEENS - 1) /print(m,0); else wy_serial_listAllCol(m, y+1);m0xy = 0;1.2.2 并行算法設(shè)計(jì)OpenMP使用parallel for 來調(diào)用listFirstCol()函數(shù)，listFirstCol再遞歸調(diào)用listSecondCol()函數(shù)來實(shí)現(xiàn)各線程并行遞歸回溯其他語(yǔ)言使用并行區(qū)域的辦法來保證各線程并行遞歸回溯/* * wy_parallel_listOtherCol : Determi

7、ne The Other Cols In Parallel Way * * param m * param y * param thread */static void wy_parallel_listOtherCol(int mTHREADSQUEENSQUEENS , int y,int thread) for(int x = 0; x QUEENS; x+) mthreadxy = 1;if(wy_isOk(m, x, y,thread) if(y = QUEENS - 1) /print(m,omp_get_thread_num(); else wy_parallel_listOthe

8、rCol(m, y+1,thread);mthreadxy = 0;/* * wy_parallel_listFirstCol : Determine The First Col In Parallel Way * * param m * param y */static void wy_parallel_listFirstCol(int mTHREADSQUEENSQUEENS , int y) #pragma omp parallel forfor(int x = 0; x QUEENS; x+) /printf(thread_num%dn,omp_get_thread_num();mom

9、p_get_thread_num()xy = 1;if(wy_isOk(m, x, y,omp_get_thread_num() wy_parallel_listOtherCol(m, y+1,omp_get_thread_num();momp_get_thread_num()xy = 0;1.2.3 理論加速比分析（選作）在N皇后問題中，加速比一般為Thread數(shù)目，最高加速比為N。因?yàn)樽疃嘣试SN個(gè)線程同時(shí)運(yùn)行。1.3 基于OpenMP的并行算法實(shí)現(xiàn)1.3.1 代碼及注釋（變量名 名字首字母 開頭）/YTU Wang Yang 123-2 2 OpenMP N-QUEEN#include s

10、tdafx.h #define QUEENS 8/* QUEENS NUM */* 8 QUEENS HAVA 92 RES */#define THREADS 4/* THREADS TOTAL NUM */* * wy_isOk : Check The Current Queen Site Validity * * param x * param y * return bool-value */static bool wy_isOk(int mTHREADSQUEENSQUEENS,int x,int y,int thread) int tx,ty;/* Same row , return

11、 false */for(ty = 0;ty = 0 & -ty = 0) if(mthreadtxty = 1)return false;/* Diagonal / , return false */tx = x;ty = y;while(+tx = 0) if(mthreadtxty = 1)return false;return true;/* * count : Current Count */static int count = 1;/* * print : Print Current Finished Chess Table * * param m * param thread *

12、/static void print(int mTHREADSQUEENSQUEENS,int thread) printf(%dn,count);count+;for(int i = 0 ; i QUEENS ; i+) for(int j = 0 ; j QUEENS ; j+) printf( %d,mthreadij);printf(n);/* * wy_serial_listAllCol : List All The Valid Chess Table In Serial Way * * param m * param y */static void wy_serial_listAl

13、lCol(int mTHREADSQUEENSQUEENS , int y) for(int x = 0; x QUEENS; x+) m0xy = 1;if(wy_isOk(m, x, y,0) if(y = QUEENS - 1) /print(m,0); else wy_serial_listAllCol(m, y+1);m0xy = 0;/* * wy_parallel_listOtherCol : Determine The Other Cols In Parallel Way * * param m * param y * param thread */static void wy

14、_parallel_listOtherCol(int mTHREADSQUEENSQUEENS , int y,int thread) for(int x = 0; x QUEENS; x+) mthreadxy = 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);mthreadxy = 0;/* * wy_parallel_listFirstCol : Determine The First C

15、ol In Parallel Way * * param m * param y */static void wy_parallel_listFirstCol(int mTHREADSQUEENSQUEENS , int y) #pragma omp parallel forfor(int x = 0; x QUEENS; x+) /printf(thread_num%dn,omp_get_thread_num();momp_get_thread_num()xy = 1;if(wy_isOk(m, x, y,omp_get_thread_num() wy_parallel_listOtherC

16、ol(m, y+1,omp_get_thread_num();momp_get_thread_num()xy = 0;int _tmain(int argc, _TCHAR* argv) int mTHREADSQUEENSQUEENS;/* Parallel Part */omp_set_num_threads(THREADS);clock_t t1 = clock();for (int i = 0; i THREADS; i+) for (int j = 0; j QUEENS; j+) for (int z = 0; z QUEENS; z+) mijz = 0;wy_parallel_

17、listFirstCol(m, 0);clock_t t2 = clock();float pt = t2 - t1;printf(N QUEEN : N = %dn,QUEENS);printf(Parallel Time = %fn,pt);/* 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+) mijz = 0;wy_serial_listAllCol(m, 0);t2 = clock();float s

18、t = t2 - t1;printf(Serial Time = %fn,st);printf(相對(duì)加速比= %fn,st/pt);getch();return 0;1.3.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）（1）小數(shù)據(jù)量驗(yàn)證正確性的執(zhí)行結(jié)果N = 12 Serial Time = 498 , Parallel Time= 1235相對(duì)加速比 = 2.479（2）大數(shù)據(jù)量獲得較好加速比的執(zhí)行結(jié)果N = 14 Serial Time = 20340 , Parallel Time = 41072相對(duì)加速比 = 2.0191.3.3 遇到的問題及解決方案（1）問題一錯(cuò)誤代碼及后果當(dāng)

19、數(shù)組m維數(shù)為2維時(shí)，無法避免其他線程對(duì)當(dāng)前線程的影響，各線程存在數(shù)據(jù)競(jìng)爭(zhēng)，無法準(zhǔn)確的描述棋盤放置狀態(tài)。正確代碼應(yīng)將數(shù)組設(shè)置為3維，第1維為Thread維，避免多線程共同操作同一個(gè)棋盤，出現(xiàn)數(shù)據(jù)競(jìng)爭(zhēng)。分析OpenMP和Intel的CPU兼容很好，所以加速比很理想。1.4 基于MPI的并行算法實(shí)現(xiàn)1.4.1 代碼及注釋（變量名 名字首字母 開頭）/YTU Wang Yang 123-2 2 MPI N-QUEEN#include stdafx.h #define QUEENS 8/* QUEENS NUM */* 8 QUEENS HAVE 92 RES */#define THREADS 2/*

20、 THREADS TOTAL NUM */* * wy_isOk : Check The Current Queen Site Validity * * param x * param y * return bool-value */static bool wy_isOk(int mTHREADSQUEENSQUEENS,int x,int y,int thread) int tx,ty;/* Same row , return false */for(ty = 0;ty = 0 & -ty = 0) if(mthreadtxty = 1)return false;/* Diagonal /

21、, return false */tx = x;ty = y;while(+tx = 0) if(mthreadtxty = 1)return false;return true;/* * count : Current Count */static int count = 1;/* * print : Print Current Finished Chess Table * * param m * param thread */static void print(int mTHREADSQUEENSQUEENS,int thread) printf(%dn,count);count+;for

22、(int i = 0 ; i QUEENS ; i+) for(int j = 0 ; j QUEENS ; j+) printf( %d,mthreadij);printf(n);/* * wy_serial_listAllCol : List All The Valid Chess Table In Serial Way * * param m * param y */static void wy_serial_listAllCol(int mTHREADSQUEENSQUEENS , int y) for(int x = 0; x QUEENS; x+) m0xy = 1;if(wy_i

23、sOk(m, x, y,0) if(y = QUEENS - 1) /print(m,0); else wy_serial_listAllCol(m, y+1);m0xy = 0;/* * wy_parallel_listOtherCol : Determine The Other Cols In Parallel Way * * param m * param y * param thread */static void wy_parallel_listOtherCol(int mTHREADSQUEENSQUEENS , int y,int thread) for(int x = 0; x

24、 QUEENS; x+) mthreadxy = 1;if(wy_isOk(m, x, y,thread) if(y = QUEENS - 1) /print(m,thread); else wy_parallel_listOtherCol(m, y+1,thread);mthreadxy = 0;/* * wy_parallel_listFirstCol : Determine The First Col In Parallel Way * * param m * param y */static void wy_parallel_listFirstCol(int mTHREADSQUEEN

25、SQUEENS , int y ,int thread) int floorLength= int(floor(double(QUEENS / 2) ); if(thread = 0) for (int x = 0 ; x floorLength ; x+) mthreadxy = 1; if (wy_isOk(m , x , y , thread) wy_parallel_listOtherCol(m , y+1 , thread); mthreadxy = 0; else for (int x = floorLength ; x QUEENS ; x+) mthreadxy = 1; if

26、 (wy_isOk(m , x , y , thread) wy_parallel_listOtherCol(m , y+1 , thread); mthreadxy = 0; int _tmain(int argc, char* argv) int mTHREADSQUEENSQUEENS;/* Parallel Part */int n = 0, done = 0;int thread , size;double t1 , t2;MPI_Init(&argc , &argv);/* Init MPI */MPI_Comm_size(MPI_COMM_WORLD,&size);MPI_Com

27、m_rank(MPI_COMM_WORLD,&thread);for (int i = 0; i THREADS; i+) for (int j = 0; j QUEENS; j+) for (int z = 0; z QUEENS; z+) mijz = 0;while(!done)if(thread = 0) t1 = clock();MPI_Bcast(&n , 1 , MPI_INT , 0 , MPI_COMM_WORLD);if(n = 0) done = 1;wy_parallel_listFirstCol(m , 0 , thread);if(n = 0)t2 = clock(

28、);MPI_Finalize();/* Finish MPI */double pt = t2 - t1;printf(N QUEEN : N = %dn,QUEENS);printf(Parallel Time = %fn,t2);/* 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+) mijz = 0;wy_serial_listAllCol(m, 0);t2 = clock();double st = t

29、2 - t1;printf(Serial Time = %fn,st);printf(相對(duì)加速比= %fn,st/pt);system(pause);return 0;1.4.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）（1）小數(shù)據(jù)量驗(yàn)證正確性的執(zhí)行結(jié)果N = 12 Serial Time = 790 , Parallel Time= 1148相對(duì)加速比 = 2.072（2）大數(shù)據(jù)量獲得較好加速比的執(zhí)行結(jié)果N = 14 Serial Time = 21436, Parallel Time = 41090相對(duì)加速比 = 1.9391.4.3 遇到的問題及解決方案（1）問題一錯(cuò)誤代碼及后果當(dāng)

30、數(shù)組m維數(shù)為2維時(shí)，無法避免其他線程對(duì)當(dāng)前線程的影響，各線程存在數(shù)據(jù)競(jìng)爭(zhēng)，無法準(zhǔn)確的描述棋盤放置狀態(tài)。正確代碼應(yīng)將數(shù)組設(shè)置為3維，第1維為Thread維，避免多線程共同操作同一個(gè)棋盤，出現(xiàn)數(shù)據(jù)競(jìng)爭(zhēng)。分析加速比理想。1.5 基于Java（Tread或者Runnable）的并行算法實(shí)現(xiàn)1.5.1 代碼及注釋（變量名 名字首字母 開頭）/YTU Wang Yang 123-2 2 Java-Runnable N-QUEENpackage com.nq.wy;public class NQueens implements Runnable private static int QUEENS = 8;/

31、* QUEENS NUM */* 8 QUEENS HAVE 92 RES */private static int THREADS= 2;/* THREADS TOTAL NUM */private static int m = new intTHREADSQUEENSQUEENS;private static long t1 ;private static long t2 ;private int threadNum ;public NQueens(int threadNum )this.threadNum = threadNum;/* * wy_isOk : Check The Curr

32、ent Queen Site Validity * * param m * param x * param y * return boolean-value */public static boolean wy_isOk(int m, int x, int y,int thread) int tx, ty; /* Same row , return false */for(ty = 0;ty = 0 & -ty = 0) if(mthreadtxty = 1)return false;/* Diagonal / , return false */tx = x;ty = y;while(+tx

33、= 0) if(mthreadtxty = 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) System.out.println( + count + -Threadnum- +thread); count+; for (i

34、nt i = 0; i QUEENS; i+) for (int j = 0; j QUEENS; j+) System.out.print( + mthreadij); System.out.println(); /* * wy_serial_listAllCol : List All The Valid Chess Table In Serial Way * * param y */public static void wy_serial_listAllCol(int y) for(int x = 0; x QUEENS; x+) m0xy = 1;if(wy_isOk(m, x, y,0

35、) if(y = QUEENS - 1) /print(m,0); else wy_serial_listAllCol(y+1);m0xy = 0; /* * wy_parallel_listFirstCol : Determine The First Column In Parallel Way * * param y * param thread */ public static void wy_parallel_listFirstCol(int y, int thread) int floorLength=(int) Math.floor( QUEENS / 2 ); if(thread

36、 = 0) for (int x = 0 ; x floorLength ; x+) mthreadxy = 1; if (wy_isOk(m , x , y , thread) wy_parallel_listOtherCol(y+1 , thread); mthreadxy = 0; else for (int x = floorLength ; x QUEENS ; x+) mthreadxy = 1; if (wy_isOk(m , x , y , thread) wy_parallel_listOtherCol(y+1 , thread); mthreadxy = 0; long p

37、t = t2 - t1; System.out.println(Parallel Time = + (t2 - t1); /* Serial Part */ for (int i = 0; i THREADS; i+) for (int j = 0; j QUEENS; j+) for(int z = 0 ; z QUEENS ; z+) mijz = 0; t1 = System.currentTimeMillis(); wy_serial_listAllCol(0); t2 = System.currentTimeMillis(); long st = t2 - t1; System.ou

38、t.println(Serial Time = + (t2 - t1); System.out.println(相對(duì)加速比 = + (double)st/pt + n); /* * wy_parallel_listOtherCol : Determine The Other Column In Parallel Way * * param y * param thread */ public static void wy_parallel_listOtherCol(int y , int thread) for(int x = 0; x QUEENS; x+) mthreadxy = 1;if

39、(wy_isOk(m , x , y , thread) if(y = QUEENS - 1) if(x = QUEENS - 1)t2 = System.currentTimeMillis();/print(m , thread); else wy_parallel_listOtherCol(y+1 , thread);mthreadxy = 0; Override public void run() if(this.threadNum = 0) wy_parallel_listFirstCol(0 , 0); else wy_parallel_listFirstCol(0 , 1); pu

40、blic static void main(String args) throws InterruptedException System.out.println(N QUEEN : N = + QUEENS); /* Parallel Part */ for (int i = 0; i THREADS; i+) for (int j = 0; j QUEENS; j+) for(int z = 0 ; z QUEENS ; z+) mijz = 0; t1 = System.currentTimeMillis(); NQueens eq1 = new NQueens(0); NQueens

41、eq2 = new NQueens(1); Thread td1 = new Thread(eq1); Thread td2 = new Thread(eq2); td1.start(); td2.start(); /td1.join(); /td2.join(); 1.5.2 執(zhí)行結(jié)果截圖（體現(xiàn)串行時(shí)間、并行時(shí)間和加速比）（1）小數(shù)據(jù)量驗(yàn)證正確性的執(zhí)行結(jié)果相對(duì)加速比 = 1.96875（2）大數(shù)據(jù)量獲得較好加速比的執(zhí)行結(jié)果N = 14 Serial Time = 10284 , Parallel Time = 17871相對(duì)加速比 = 1.7371.5.3 遇到的問題及解決方案（1）問題一錯(cuò)誤代碼及后果當(dāng)數(shù)組m維數(shù)為2維時(shí)，無法避免其他線程對(duì)當(dāng)前線程的影響，各線程存在數(shù)據(jù)競(jìng)爭(zhēng)，無法準(zhǔn)確的描述棋盤放置狀態(tài)。正確代碼應(yīng)將數(shù)組設(shè)置為3維，第1維為Thread維，避免多線程共同操作同一個(gè)棋盤，出現(xiàn)數(shù)據(jù)競(jìng)爭(zhēng)。分析加速比理想。1.6 基于Windows（API或MFC或.net）的并行算法實(shí)現(xiàn)1.6.1 代碼及注釋（變量名 名字首字母 開頭）/YTU Wang Yang 123-2 2 .Net(C#) N-QUEENusing System;using System.Collections.Gen