下载 >  开发技术 >  其它 > 基_2FF并行算法及实现

基_2FF并行算法及实现

基_2FF并行算法及实现 基_2FF并行算法及实现
2009-06-13 上传大小:84KB
分享
收藏 举报
枚举排序的并行算法MPI程序实现

枚举排序是一种最简单的排序算法,该算法的具体思想是对每一个待排序的元素统计小于它的所有元素的个数,从而得到该元素最终处于序列钟的位置。对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序,只需使每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程钟,由主进程负责完成所有元素的最终排位。

立即下载
32位CRC校验码的并行算法及硬件实现

32位CRC校验码的并行算法及硬件实现32位CRC校验码的并行算法及硬件实现32位CRC校验码的并行算法及硬件实现32位CRC校验码的并行算法及硬件实现

立即下载
并行算法.pdf并行算法.pdf

并行算法 并行算法 并行算法 并行算法 并行算法 并行算法

立即下载
并行计算实验快速排序的并行算法

3.1实验目的与要求 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现

立即下载
并行算法设计与分析习题答案

陈国良第二版的《并行算法的分析与设计》习题答案,希望能对你们有帮助,参考参考

立即下载
POM海洋模式的并行算法

POM海洋模式的并行算法POM海洋模式的并行算法POM海洋模式的并行算法POM海洋模式的并行算法POM海洋模式的并行算法POM海洋模式的并行算法POM海洋模式的并行算法

立即下载
并行计算课程设计(报告+代码+可执行文件)

1. 设计目的、意义(功能描述) 蒙特·卡罗方法(Monte Carlo method),也称统计模拟方法,是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明,而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。本次大作业主要是对蒙特·卡罗方法进行并行处理,通过OpenMP、MPI、.NET、Java、Win32API等一系列并行技术和并行机制对该算法进行并行处理,从而也进一步熟悉了蒙特·卡罗方法的串行算法和并行算法,实现了用蒙特·卡罗方法计算出半径为1单位的球体的体积,体会到了并行技术在实际生活中的应用。 2. 方案分析(解决方案) 蒙特·卡罗方法(Monte Carlo method)是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。球的体积可以估算为:位于点模型内随机点个数与全体随机点个数的比值乘以包围盒的体积算的。 3. 设计分析 3.1 串行算法设计 假定球体用B表示,半径r=1单位,B1是包含B的参考立方体(在本例中是边长为2的正方体),在B1中产生N个均匀分布的伪随机点。对每个随机点检测其是否在B内,假设位于B内的随机点个数为N(in)(<=N),应用蒙特卡洛算法,则B的体积为 V=V1(N(in)/N) 其中V1是B1的体积。如果产生足够多的随机点,理论上可以获得任意逼近精度。 算法描述如下: BEGIN N=_MAX; FOR I=0;I<_MAX;I++ X=RANDOM(); Y=RANDOM(); Z=RANDOM(); IF (X*X+Y*Y+Z*Z)<=1 COUNT++; END IF; END FOR; BULK=V1*(COUNT/_MAX); END; 本算法主要是在参考立方体的选取上和定义的_MAX的值对结果影响较大,所以应该选择合适的数。 3.2 并行算法设计 对FOR循环进行划分使用两个处理器完成计算。例如对一个长为n的序列,首先划分得到两个长为n/2的序列,将其交给两个处理器分别处理;而后进一步划分得到四个长为n/4的序列,再分别交给四个处理器处理;如此递归下去最终得到结果。当然这是理想的划分情况,如果划分步骤不能达到平均分配的目的,那么结果的效率会相对较差。 伪代码如下: BEGIN N=_MAX; FOR1 I=0;I<_MAX/2;I++ X1=RANDOM(); Y1=RANDOM(); Z1=RANDOM(); IF (X1*X1+Y1*Y1+Z1*Z1)<=1 COUNT1++; END IF; END FOR1; FOR2 I=_MAX/2+1;I<_MAX;I++ X2=RANDOM(); Y2=RANDOM(); Z2=RANDOM(); IF (X2*X2+Y2*Y2+Z2*Z2)<=1 COUNT2++; END IF; END FOR2; BULK=V1*((COUNT1+ COUNT2)/_MAX); END; 3.3 理论加速比分析 实验中大量数据所产生的加速比比小量数据所产生的加速比要体现得更明显,并且数据生成的并行加速比随着处理器核的增加而增加。设处理器个数为p,数据量为n,由于正常情况下该快速排序算法的复杂度为O(nlogn),并行处理的时间复杂度为O(klogk),其中k=n/p,所以并行算法的时间复杂度为O((n/p)log(n/p)),理论加速比为nlogn/((n/p)log(n/p))=p+logp. 4. 功能模块实现与最终结果分析 4.1 基于OpenMP的并行算法实现 4.1.1 主要功能模块与实现方法 利用了OpenMP里面的#omp parallel sections将对两个for循环用两个线程并行化执行,以多线程方式并行运行程序,并行的算法步骤如下: (1)初始化_max = 10000000; (2)创建两个线程; (3)由OpenMP编译指导语句控制产生并行执行代码区段; (4)将数据存放到tianqing_count; (5)各线程调用算法得出结果; 并行算法的部分代码如下: #pragma omp parallel for private(tianqing_x,tianqing_y,tianqing_z) reduction(+:tianqing_count2) for (tianqing_i = 0; tianqing_i<tianqing_max; tianqing_i++) { tianqing_x = rand(); tianqing_x = tianqing_x / 32767; tianqing_y = rand(); tianqing_y = tianqing_y / 32767; tianqing_z = rand(); tianqing_z = tianqing_z / 32767; if ((tianqing_x*tianqing_x + tianqing_y*tianqing_y + tianqing_z*tianqing_z) <= 1) tianqing_count2++; } tianqing_bulk = 8 * ((double)(tianqing_count2) / tianqing_max); 4.1.2 实验加速比分析 实验中创建了两个线程,通过多次测试,得出实验结果:由上面的理论加速比分析可知,当线程数为2时,理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响,实验加速比达不到理论值3.实验加速比在1.9左右,比较符合常理。 4.2 基于MPI的并行算法实现 4.2.1 主要功能模块与实现方法 主要利用了MPI的MPI_Bcast()函数和MPI_Recv()函数进行各个进程之间的通信,算法步骤如下: (1)初始化_max = 10000000; (2)动态申请2个数组,分别记录分块的起始地址、各个进程所获得的数据个数; (3)各个进程之间进行通信,发送接收各个进程的起始地址与数据大小; (4)并行执行算法; (5)得出结果; 伪代码如下: //初始化MPI执行环境 MPI_Init(&argc, &argv); //用MPI_Comm_rank 获得进程的rank,该rank值为到p-1间的整数,相当于进程的ID MPI_Comm_rank(MPI_COMM_WORLD, &myid); //用MPI_Comm_size 获得进程个数 int MPI_Comm_size(MPI_Comm comm, int *size); MPI_Comm_size(MPI_COMM_WORLD, &numprocs); MPI_Get_processor_name(processor_name, &namelen); MPI_Bcast(&tianqing_n,1,MPI_INT,0,MPI_COMM_WORLD);//将tianqing_n值广播出去 算法执行; MPI_Reduce(&tianqing_bulk, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);//各个进程并行计数得到的计数总和 获得结果。 4.2.2 实验加速比分析 实验中使用了两个处理器,因此理论加速比应该为2,通过多次测试,得出实验结果:加速比:1.976906139262282,由于客观因素的影响,结果合理。 4.3 基于Java的并行算法实现 4.3.1 主要功能模块与实现方法 在Java中,创建用户自己的线程类,使用启动线程的start()方法启动线程对象,使之从新建状态转入就绪状态,定义线程操作的run()方法,并定义新的run()方法覆盖原来的run()方法。 伪代码如下: And thread1=new And(1,10000000); And thread2=new And(2,10000000); long startTime=System.currentTimeMillis(); 启动线程1和线程2; 等待进程结束; And and=new And(a,10000000); bulk1=8*((b*1.0)/tianqing_n); 4.3.2 实验加速比分析 实验中创建了两个线程,通过多次测试,得出实验结果:由上面的理论加速比分析可知,当线程数为2时,理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响,实验加速比达不到理论值3.实验加速比在1.9左右,比较符合常理。 4.4 基于Windows API的并行算法实现 4.4.1 主要功能模块与实现方法 这里主要用到了Win32 API的进入点函数,在进程中创建一个线程时,也必须给这个线程提供一个进入点函数。线程函数必须返回一个值,它将成为该线程的退出代码。使用CreateThread()函数创建线程,用WaitForMultipleObject()函数管理线程来监测多个对象。采用SetEvent来设置事件处理线程间的同步问题。 伪代码如下: DWORD WINAPI ThreadOne(LPVOID param) { 对前一半数据进行处理; SetEvent(finish[0]); return 0; } DWORD WINAPI ThreadTwo(LPVOID param) { 对后一半数据进行处理; SetEvent(finish[1]); return 0; } 创建两个事件; HANDLE thread1=CreateThread(NULL,0,ThreadOne,NULL,0,NULL);//两个并行线程 HANDLE thread2=CreateThread(NULL,0,ThreadTwo,NULL,0,NULL); WaitForMultipleObjects(2,finish,true,INFINITE); 得出结果; 4.4.2 实验加速比分析 实验中创建了两个线程,通过多次测试,得出实验结果:由上面的理论加速比分析可知,当线程数为2时,理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响,实验加速比达不到理论值3.实验加速比在1.6左右。 4.5 基于.net的并行算法实现 4.5.1 主要功能模块与实现方法 先创建ThreadStart代理,指定要由该线程执行的线程函数,然后将ThreadStart代理传递给Thread类的构造函数,调用Thread类的Start方法启动新的线程然后调用Join()方法保证应用程序域等待异步程序结束后才终止运行。 伪代码如下: Stopwatch stopwatch = new Stopwatch(); 创建Work类的对象work1; ThreadStart thread1 = new ThreadStart(() => work1.pSumto(b, 0, MAXN - 1)); Thread newthread1 = new Thread(thread1); 创建Work类的对象work2; ThreadStart thread2 = new ThreadStart(() => work2.pSumto(c, 0, MAXN - 1)); Thread newthread2 = new Thread(thread2); stopwatch.Start(); 启动线程1和线程2; 等待进程结束; stopwatch.Stop(); 得到结果; 4.5.2 实验加速比分析 实验中创建了两个线程,通过多次测试,得出实验结果:由上面的理论加速比分析可知,当线程数为2时,理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响,实验加速比达不到理论值3.实验加速比在2.6~2.7左右。 4.6 并行计算技术在实际系统中的应用 4.6.1 主要功能模块与实现方法 该飞机订票系统主要实现了对机票的一些基本信息进行存储和管理的功能。在系统中实现了对机票信息的增删改查,考虑到查询的方便性,对机票按照航班号进行排序,而此排序方法用并行快速排序运用进来。利用OpenMP的并行技术,对机票信息按顺序排列好,并分析了实验过程中的加速比。 4.6.2 实验加速比分析 实验中创建了两个线程,通过多次测试,得出实验结果:当数据量比较大时,加速比理论在1.9左右。数据量较大时体现出来的加速比更准确。由上面的理论加速比分析可知,当线程数为2时,理论加速比为2+log2=3.但由于实际操作中硬件设备以及内存分配的影响,实验加速比达不到理论值3.实验加速比在2.2~2.4左右。 5. 设计体会 虽然没有按时完成作业,但这份报告花了我好几天的时间,从开始的搭建并行计算平台到最后的程序运行成功可以说是对我的一个锻炼。每一次的遇到问题与每一次的解决问题都是一个成长。每一次遇到问题和解决问题都是一种锻炼,一种尝试,从我们上并行计算课我懂得了很多电脑硬件和软件的知识,这些可能对于我们这个专业以后都是没有机会接触的,所以我觉得选择了并行计算与多核多线程技术这门课是非常正确的。对OpenMP、MPI、WIN32API、Java、.NET的并行技术有了一定的了解。在搭建MPI并行程序这块,学习的知识尤为增加,这些都是在不断的摸索、学习中学会的。 这次的大作业虽然是对以前实验的整合,但它加深了我对并行计算的印象,也使我对并行计算知识的理解更加深刻,也使我认识到了自己很多不足之处。学习并行计算的历程不会因为完成本次大作业而停止,我们是为了用知识武装大脑而学习,通过学习充实自己的生活,要努力学习,争取以后能够完成规模更大的程序。

立即下载
CUDA的图像分割并行算法的设计与实现

CUDA的图像分割并行算法的设计与实现 真的很好啊

立即下载
mpi程序并行算法源码 陈国良书中的全部算法源码

fft并行算法实现,C语言开发,用mpi编程完成 陈国良并行算法的设计与分析中算法的源码全部

立即下载
并行算法的设计与分析 第3版 陈国良编著 pdf版

并行算法的设计与分析 第3版 陈国良编著 2009年8月出版 高清扫描pdf版,值得大家收藏~~ 另外:并行计算——结构·算法·编程(修订版)—陈国良编著 2003,请参看我的上传列表

立即下载
矩阵计算的并行算法实现

对于大型矩阵的乘积运算和高阶方阵的求逆运算, 构造了一种适用于多处理机系统的并行算法. 该方法能较大地节约计算机的工作单元, 提高计算速度和效率, 同时给出了具体的并行程序和计算结果.

立即下载
矩阵转置的并行算法mpi实现

矩阵转置的并行化实现,用的的是c语言,mpi实现的,可以参考下

立即下载
矩阵相乘的MPI并行算法

使用MPI+C并行语言实现矩阵相乘,该程序已经经过调试,完全可运行。

立即下载
MPI实现并行的快速排序

利用MPI实现快速排序的并行算法,算法使用C语言实现

立即下载
矩阵乘法串行并行算法

512*512的矩阵,实现并行算法分行,分列,分块的做法以及串行算法的实现

立即下载
并行粒子群优化算法的设计与实现

粒子群算法的并行实现算法,有利于加深对粒子群算法的理解

立即下载
八皇后问题并行算法及源代码(附N皇后)

八皇后问题并行算法及源代码(附N皇后)八皇后问题并行算法及源代码(附N皇后)八皇后问题并行算法及源代码(附N皇后)八皇后问题并行算法及源代码(附N皇后)

立即下载
非数值并行算法—模拟退火算法

一本常用的书 非数值并行算法—模拟退火算法 非数值并行算法—模拟退火算法 非数值并行算法—模拟退火算法

立即下载
矩阵相乘FOX并行算法

矩阵相乘FOX并行算法,矩阵相乘FOX并行算法

立即下载
基于Java多线程实现所有顶点间最短路径的并行算法

基于Java多线程实现所有顶点间最短路径的并行算法

立即下载
关闭
img

spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
点击完成任务获取下载码
输入下载码
为了良好体验,不建议使用迅雷下载
img

基_2FF并行算法及实现

会员到期时间: 剩余下载个数: 剩余C币: 剩余积分:0
为了良好体验,不建议使用迅雷下载
VIP下载
您今日下载次数已达上限(为了良好下载体验及使用,每位用户24小时之内最多可下载20个资源)

积分不足!

资源所需积分/C币 当前拥有积分
您可以选择
开通VIP
4000万
程序员的必选
600万
绿色安全资源
现在开通
立省522元
或者
购买C币兑换积分 C币抽奖
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
为了良好体验,不建议使用迅雷下载
确认下载
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
为了良好体验,不建议使用迅雷下载
VIP和C币套餐优惠
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
您的积分不足,将扣除 10 C币
为了良好体验,不建议使用迅雷下载
确认下载
下载
您还未下载过该资源
无法举报自己的资源

兑换成功

你当前的下载分为234开始下载资源
你还不是VIP会员
开通VIP会员权限,免积分下载
立即开通

你下载资源过于频繁,请输入验证码

您因违反CSDN下载频道规则而被锁定帐户,如有疑问,请联络:webmaster@csdn.net!

举报

若举报审核通过,可返还被扣除的积分

  • 举报人:
  • 被举报人:
  • *类型:
    • *投诉人姓名:
    • *投诉人联系方式:
    • *版权证明:
  • *详细原因: