已阅读5页,还剩33页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
并行计算与多核多线程技术课程报告班级 _学号_ 姓名 _ 2014 年 11 月 26 日目 录1. N皇后问题 并行算法设计与实现11.1 功能描述与解决方案11.1.1功能描述11.1.2 解决方案11.2算法设计11.2.1 串行算法设计11.2.2 并行算法设计21.2.3 理论加速比分析(选作)31.3 基于OpenMP的并行算法实现31.3.1 代码及注释(变量名 名字首字母 开头)31.3.2 执行结果截图(体现串行时间、并行时间和加速比)71.3.3 遇到的问题及解决方案81.4 基于MPI的并行算法实现91.4.1 代码及注释(变量名 名字首字母 开头)91.4.2 执行结果截图(体现串行时间、并行时间和加速比)131.4.3 遇到的问题及解决方案141.5 基于Java(Tread或者Runnable)的并行算法实现151.5.1 代码及注释(变量名 名字首字母 开头)151.5.2 执行结果截图(体现串行时间、并行时间和加速比)191.5.3 遇到的问题及解决方案211.6 基于Windows(API或MFC或.net)的并行算法实现211.6.1 代码及注释(变量名 名字首字母 开头)211.6.2 执行结果截图(体现串行时间、并行时间和加速比)261.6.3 遇到的问题及解决方案271.7 基于Linux(fork或pthread)的并行算法实现281.7.1 代码及注释(变量名 名字首字母 开头)281.7.2 执行结果截图(体现串行时间、并行时间和加速比)321.7.3 遇到的问题及解决方案332. 理论基础342.1 并行计算机体系结构、并行计算模型、并行算法的概念342.2并行计算机体系结构、并行计算模型、并行算法的关系342.3实例说明并行计算机体系结构、并行计算模型、并行算法的关系34评 价实践效果(正确度/加速比)理论基础难度工作量独立性1. N皇后问题 并行算法设计与实现1.1 功能描述与解决方案1.1.1功能描述八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是:在8*8的棋盘上摆放8个皇后,使其不能互相攻击,即任意的两个皇后不能处在同意行,同 一列,或同意斜线上。可以把八皇后问题拓展为n皇后问题,即在n*n的棋盘上摆放n个皇后,使其任意两个皇后都不能处于同一行、同一列或同一斜线上。1.1.2 解决方案1、此题有多重解法,常见解法有残卷法(即穷举法,但时间复杂度和空间复杂度均为NN,并不高效)和递归+回溯算法(本次采用此算法)。2、判断当前放置的皇后“安全”的依据为同行、同列、对角线-、对角线-/的遍历结果均为TRUE即没有不满足问题条件的皇后存在。3、第一个线程从第一列第一行的坐标开始放置皇后,其他线程从其他列第一行的元素开始递归放置皇后,每放置一个皇后,判断其是否安全,若“安全”则继续在当前列和(当前行+1)处放置下一个皇后,若不安全则将当前皇后坐标设为0。4、采用三维数组mTHREADQUEENSQUEENS来存放棋盘的放置状态,第一维用于保证各线程不会影响其他线程的放置状态,第二、三维用来确定棋盘的规格。1.2算法设计1.2.1 串行算法设计/* * 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_isOk(m, x, y,0) if(y = QUEENS - 1) /print(m,0); else wy_serial_listAllCol(m, y+1);m0xy = 0;1.2.2 并行算法设计OpenMP使用parallel for 来调用listFirstCol()函数,listFirstCol再递归调用listSecondCol()函数来实现各线程并行递归回溯其他语言使用并行区域的办法来保证各线程并行递归回溯/* * 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 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 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();momp_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数目,最高加速比为N。因为最多允许N个线程同时运行。1.3 基于OpenMP的并行算法实现1.3.1 代码及注释(变量名 名字首字母 开头)/YTU Wang Yang 123-2 201258503222 OpenMP N-QUEEN#include stdafx.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 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 */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_listAllCol(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_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 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();momp_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;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_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 st = t2 - t1;printf(Serial Time = %fn,st);printf(相对加速比= %fn,st/pt);getch();return 0;1.3.2 执行结果截图(体现串行时间、并行时间和加速比)(1)小数据量验证正确性的执行结果N = 12 Serial Time = 498 , Parallel Time= 1235相对加速比 = 2.479(2)大数据量获得较好加速比的执行结果N = 14 Serial Time = 20340 , Parallel Time = 41072相对加速比 = 2.0191.3.3 遇到的问题及解决方案(1)问题一错误代码及后果当数组m维数为2维时,无法避免其他线程对当前线程的影响,各线程存在数据竞争,无法准确的描述棋盘放置状态。正确代码应将数组设置为3维,第1维为Thread维,避免多线程共同操作同一个棋盘,出现数据竞争。分析OpenMP和Intel的CPU兼容很好,所以加速比很理想。1.4 基于MPI的并行算法实现1.4.1 代码及注释(变量名 名字首字母 开头)/YTU Wang Yang 123-2 201258503222 MPI N-QUEEN#include stdafx.h #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 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 / , 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(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_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_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,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 mTHREADSQUEENSQUEENS , 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 (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_Comm_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();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 = t2 - t1;printf(Serial Time = %fn,st);printf(相对加速比= %fn,st/pt);system(pause);return 0;1.4.2 执行结果截图(体现串行时间、并行时间和加速比)(1)小数据量验证正确性的执行结果N = 12 Serial Time = 790 , Parallel Time= 1148相对加速比 = 2.072(2)大数据量获得较好加速比的执行结果N = 14 Serial Time = 21436, Parallel Time = 41090相对加速比 = 1.9391.4.3 遇到的问题及解决方案(1)问题一错误代码及后果当数组m维数为2维时,无法避免其他线程对当前线程的影响,各线程存在数据竞争,无法准确的描述棋盘放置状态。正确代码应将数组设置为3维,第1维为Thread维,避免多线程共同操作同一个棋盘,出现数据竞争。分析加速比理想。1.5 基于Java(Tread或者Runnable)的并行算法实现1.5.1 代码及注释(变量名 名字首字母 开头)/YTU Wang Yang 123-2 201258503222 Java-Runnable N-QUEENpackage com.nq.wy;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 intTHREADSQUEENSQUEENS;private static long t1 ;private static long t2 ;private int threadNum ;public NQueens(int threadNum )this.threadNum = threadNum;/* * wy_isOk : Check The Current 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 = 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 (int 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) 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 = 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 pt = 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.out.println(Serial Time = + (t2 - t1); System.out.println(相对加速比 = + (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(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); public 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 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 执行结果截图(体现串行时间、并行时间和加速比)(1)小数据量验证正确性的执行结果相对加速比 = 1.96875(2)大数据量获得较好加速比的执行结果N = 14 Serial Time = 10284 , Parallel Time = 17871相对加速比 = 1.7371.5.3 遇到的问题及解决方案(1)问题一错误代码及后果当数组m维数为2维时,无法避免其他线程对当前线程的影响,各线程存在数据竞争,无法准确的描述棋盘放置状态。正确代码应将数组设置为3维,第1维为Thread维,避免多线程共同操作同一个棋盘,出现数据竞争。分析加速比理想。1.6 基于Windows(API或MFC或.net)的并行算法实现1.6.1 代码及注释(变量名 名字首字母 开头)/YTU Wang Yang 123-2 201258503222 .Net(C#) N-QUEENusing System;using Sy
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- (2025年)山东省枣庄市公开遴选公务员笔试题及答案解析(B类)
- 2019年国考行测真题完整版答案解析
- 2026年皮肤性病学题库及答案
- 2026年皮肤病学皮肤外科手术模拟试卷(含答案)
- 2026年四川工业科技学院公共课大学计算机基础期末模拟试卷带答案
- 2026年乡村振兴战略与实践考试模拟试卷(含答案)
- 2026年实验室安全行为规范测试模拟试卷带答案
- 临床流行病学研究题库及答案
- 2026年教资考试河南题库及答案
- 医药行业资金链断裂危机应对手册
- 2021-2022学年上学期长沙初中道德与法治八年级期中典型试卷1
- 方剂学方歌(“十三五”第十版教材)(2021年新版)
- 企业职工养老保险知识
- 运动素质知到课后答案智慧树章节测试答案2025年春浙江大学
- 图纸保密协议
- 计算机组成原理(第6版)课件全套 纪禄平 第0-6章 概论-输入输出设备及其接口
- 江苏省苏州市昆山、太仓、常熟、张家港四市2024-2025学年八年级上学期期末阳光测试历史试题(含答案)
- 2024版科研项目合作协议书
- 陶瓷厂工艺设计概论(山东联盟)智慧树知到期末考试答案章节答案2024年齐鲁工业大学
- 驾照体检表完整版本
- 上门按摩项目融资计划书
评论
0/150
提交评论