并行计算课程报告

并行计算与多核多线程技术课程报告专业 _班级 _学号 _姓名 _成绩 _年 月 日课程报告要求手写内容：设计目的、意义，设计分析，方案分析，功能模块实现，最终结果分析，设计体会等。允许打印内容：设计原理图等图形、图片，电路图，源程序。硬件类的设计，要有最终设计的照片图；软件类设计，要有各个功能模块实现的界面图、输入输出界面图等。评 价理论基础实践效果（正确度/加速比）难度工作量独立性班级_ 学号_ 姓名_ 算法名称_目 录1. 设计目的、意义（功能描述） .12. 方案分析（解决方案） .13. 设计分析 .13.1 串行算法设计 .13.2 并行算法设计 .13.3 理论加速比分析 .24. 功能模块实现与最终结果分析 .24.1 基于 OpenMP 的并行算法实现 .24.1.1 主要功能模块与实现方法 .24.1.2 实验加速比分析 .24.2 基于 MPI 的并行算法实现 .24.2.1 主要功能模块与实现方法 .24.2.2 实验加速比分析 .24.3 基于 Java 的并行算法实现 .34.3.1 主要功能模块与实现方法 .34.3.2 实验加速比分析 .34.4 基于 Windows API 的并行算法实现 .34.4.1 主要功能模块与实现方法 .34.4.2 实验加速比分析 .34.5 基于.net 的并行算法实现 .34.5.1 主要功能模块与实现方法 .34.5.2 实验加速比分析 .34.6 基于 Linux 的并行算法实现（选作） .44.6.1 主要功能模块与实现方法 .44.6.2 实验加速比分析 .44.7 基于 Hadoop/MapReduce 的并行算法实现（选作） .44.7.1 主要功能模块与实现方法 .44.7.2 实验加速比分析 .44.8 并行计算技术在实际系统中的应用 .44.8.1 主要功能模块与实现方法 .44.8.2 实验加速比分析 .55. 设计体会 .5班级_ 学号_ 姓名_ 算法名称_6. 附录 .66.1 基于 MPI 的并行程序设计 .66.1.1 代码及注释 .66.1.2 执行结果截图 .66.1.3 遇到的问题及解决方案 .66.2 基于 MPI 的并行程序设计 .76.1.1 代码及注释 .76.2.2 执行结果截图 .76.2.3 遇到的问题及解决方案 .76.3 基于 Java 的并行程序设计 .86.3.1 代码及注释 .86.3.2 执行结果截图 .86.3.3 遇到的问题及解决方案 .96.4 基于 Windows API 的并行程序设计 .96.4.1 代码及注释 .96.4.2 执行结果截图 .106.4.3 遇到的问题及解决方案 .106.5 基于.net 的并行程序设计 .116.5.1 代码及注释 .116.5.2 执行结果截图 .116.5.3 遇到的问题及解决方案 .116.6 基于 Linux 的并行程序设计（选作） .126.6.1 代码及注释 .126.6.2 执行结果截图 .126.6.3 遇到的问题及解决方案 .136.7 基于 Hadoop/MapReduce 的并行程序设计（选作） .136.7.1 代码及注释 .136.7.2 执行结果截图 .146.7.3 遇到的问题及解决方案 .146.8 并行计算技术在实际应用系统的应用 .156.8.1 代码及注释 .156.8.2 执行结果截图 .156.8.3 遇到的问题及解决方案 .15班级_ 学号_ 姓名_ 算法名称_11. 设计目的、意义（功能描述）并行计算或称平行计算是相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。为了缩短程序的运行时间，我们采用了并行技术实现枚举排序。2. 方案分析（解决方案）将要排序的数组分为多个部分放入不同的线程中，运用多线程技术实现并行计算，最后在用多路归并将排序的数组归并到一起。归并算法采用的是串行。3. 设计分析3.1 串行算法设计枚举排序（Enumeration Sort）是一种最简单的排序算法，通常也称为秩排序（Rank Sort） 。该算法的具体思想是（假设按关键字递增排序） ，对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的 n 个数存在a1an中。首先将 a1与 a2an比较，记录比其小的数的个数，令其为 k，a1 就被存入有序的数组 b1bn的 bk+1位置上；然后将 a2与 a1，a3an比较，记录比其小的数的个数，依此类推。这样的比较操作共 n(n-1)次，所以串行秩排序的时间复杂度为O（n 2） 。算法 枚举排序串行算法输入：a1an输出：b1bnBeginfor i=1 to n do(1) k=1(2) for j=1 to n doif aiaj thenk=k+1end ifend for(3) bk= aiend forEnd3.2 并行算法设计算法的并行化算法比较的简单,将随机数分成两个部分，对每一部分进行排序.算法 枚举排序并行算法输入：a1an输出：b1bn班级_ 学号_ 姓名_ 算法名称_2Beginfor i=1 to n do(1) k=1(2) for j=1 to n doif aiaj thenk=k+1end ifend for(3) bk= aiend forEnd假定待排序的 n 个数存在 a1an/2中。首先将 a1与 a2an/2比较，记录比其小的数的个数，令其为 k，a1 就被存入有序的数组 b1bn/2的 bk+1位置上；然后将 a2与a1，a3an/2比较，记录比其小的数的个数，依此类推。这样的比较操作共(n/2)(n-1)/2)次，所以串行秩排序的时间复杂度为 O（(n/2） 2） 。3.3 理论加速比分析在串行秩排序的时间复杂度为 O（n 2）, 并行算法的复杂度为 O（(n/2 ）2） 。所以理论加速比在 1 到 4 之间；4. 功能模块实现与最终结果分析4.1 基于 OpenMP 的并行算法实现4.1.1 主要功能模块与实现方法主函数模块：主函数模块：实现随机数的产生，对数组空间的分配以及对并行串行函数的调用；并行排序模块：对无序数组进行秩排序，并且在 for 循环中 parallel 和 for 指令联合使用，并行化的语句紧跟在编译指导语后面，编译指导语的功能区域一直延伸到外层 for 循环结束后，并且并行化作用于外部循环；串行排序模块：利用两个 for 循环对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。4.1.2 实验加速比分析实验加速比在 1.7 到 2.5 之间，数值越大，越能体现加速比；4.2 基于 MPI 的并行算法实现4.2.1 主要功能模块与实现方法主函数模块：运用 MPI_Init()函数实现了 mpi 执行环境的初始化；MPI_Comm_rank()函数识别各个进程；MPI_Comm_size()函数识别该进程中的进程数；用一对多群集通信函数 MPI_Bcast()将待排序序列长度广播给各个进程；rand（）函数产生随机数，对数组空间的分配，和在各个处理器间划分任务；并行排序模块：对无序数组进行秩排序，将待排序序列的长度 DataSize，该处理器要排序班级_ 学号_ 姓名_ 算法名称_3的序列长度 MyLength 和总处理器个数以及处理器 ID 传参给 CountRank（）函数实现每个处理器的排序；4.2.2 实验加速比分析实验加速比在 1.5 到 2.0 之间,数值越大越能体现加速比.4.3 基于 Java 的并行算法实现4.3.1 主要功能模块与实现方法在程序中创建了三个类，并在 liuhongling 类中调用其余类中的方法实现多线程，创建自己的 Thread 类的子类，并且在 chuanxing 和 bingxing 中重新定义了 run()方法来完成并行和串行排序；在 liuhongling 类中用 start()方法启动线程，使之从新建状态转入就绪状态并进入就绪队列排队；第二个线程等待调用 join()方法的线程结束，再继续执行。4.3.2 实验加速比分析实验加速比在 2.5 到 3.0 之间；4.4 基于 Windows API 的并行算法实现4.4.1 主要功能模块与实现方法主函数模块：用动态分配实现对排序数组的空间分配；rand()函数实现随机数的产生；CreateThread()函数创建进程，WaitForMultipleObjects()函数来监测对象；归并模块：将两个已排序的数组归并到一起； 4.4.2 实验加速比分析实验加速比在 1.8 到 2.5 之间,数值越大越能体现加速比.4.5 基于.net 的并行算法实现4.5.1 主要功能模块与实现方法开启进程模块：这里我们用定义了一个 ThreadStart 类型的委托,这个委托制定了线程需要执行的方法：work.bingxing 在这个方法里实现了枚举排序的并行算法4.5.2 实验加速比分析实验加速比在 3.5 到 5.0 之间；4.6 基于 Linux 的并行算法实现（选作）4.6.1 主要功能模块与实现方法班级_ 学号_ 姓名_ 算法名称_44.6.2 实验加速比分析4.7 基于 Hadoop/MapReduce 的并行算法实现（选作）4.7.1 主要功能模块与实现方法4.7.2 实验加速比分析4.8 并行计算技术在实际系统中的应用4.8.1 主要功能模块与实现方法4.8.2 实验加速比分析5. 设计体会班级_ 学号_ 姓名_ 算法名称_5班级_ 学号_ 姓名_ 算法名称_66. 附录6.1 基于 OpenMP 的并行程序设计6.1.1 代码及注释#include “stdafx.h“#include #include #include #include using namespace std;int chuanxing(int *in, int *out, int size) int lhl_i, lhl_j, lhl_k; clock_t t3, t4; t3 = clock(); for (lhl_i = 0; lhl_iinlhl_j) lhl_k+;/记录比自己小的数的个