精华内容
下载资源
问答
  • 并行计算加速比

    万次阅读 2016-05-30 00:40:34
    并行计算加速比计算

    为了定量知道并行程序的执行速度相对于串行程序的执行速度加快了多少,首先定义以下参数:令 p 是并行系统中的处理器数量;W指问题规模,或者给定问题的计算量, Ws 指程序中的串行部分,程序中的并行部分为 Wp W=Ws+Wp ; f=Ws/W 为串行部分的比例; TsTp 分别为串行、并行部分的执行时间; S 为加速比,E为效率。


    Amdahl定律

    特点:要求实时性,因此时间是关键因素,而计算负载是确定的。适用于固定计算负载。
    对于固定的问题规模,通过增加处理器,减少平均的计算负载,来提升运算速度

    S=Ws+WpWs+Wp/p

    归一化之后得到,
    S=p1+f(p1)

    这意味着,随着处理器数目的不断增加,整个系统所能达到的最大加速比是有上界的,为 1f

    如果考虑到并行计算时的通信、同步和归约的操作所花费的额外开销时间 Wo ,则

    S=1f+Wo/W

    Gustafson定律

    特点:精度是关键因素,而计算时间不变,由此需要不断增加处理器,增大计算量。适用于可扩放问题。

    S=Ws+pWpWs+Wp

    归一化后,
    S=pf(p1)

    这意味着,加速比与处理器数量成比例线性增加,同样如果考虑到额外开销,则得到
    S=pf(p1)1+Wo/W

    Sun、Ni定律

    特点:在存储空间允许的情况下,满足规定的时间要求,尽量增大计算量。

    S=fw+(1f)G(p)Wfw+(1f)G(p)W/p

    其中 G(p) 表示存储容量增加 p 倍后增加的计算量,归一化后,
    S=f+(1f)G(p)f+(1f)G(p)/p

    可以发现当 G(p)=1 时,它变成Amdahl定律的表达式,当 G(p)=p 时,它变成Gustafson定律的表达式,当 G(p)>p 时,表示计算负载比存储空间增加得快,此时的加速比前面两个定律得到的结论都快。

    加速比的经验公式为

    p/logpSp

    一般作为可并行部分占比高的以及额外开销较少的,有望达到线性加速。

    知识共享许可协议
    本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行许可。

    展开全文
  • 并行算法】加速比性能模型

    千次阅读 2020-06-18 11:48:13
    一、基本概念和加速比 1、基本概念 1).处理机的时间积 处理机数目与处理时间的乘积用以度量这些处理机运行时的资源利用率。 若程序在P台处理机上运行的时间为Tp,则此P台处理机在Tp时间间隔内完成的工作最大数量为...

    一、基本概念和加速比

    1、基本概念

    1).处理机的时间积
    处理机数目与处理时间的乘积用以度量这些处理机运行时的资源利用率。
    若程序在P台处理机上运行的时间为Tp,则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp * P。
    可以将处理机实际工作曲线对时间的积分看成是这些处理机完成的有效工作量。
    效率为有效工作量与最大工作量之比。
    2).并行度(Degree Of Parallelism—DOP)
    并行度是在一定时间间隔内执行一个程序所用的处理机的数目。
    3).并行性分布图
    执行一个给定的程序时并行度对时间的分布图。
    并行度与对应时间的间隔之积即为处理机要完成的工作或工作负载。
    如图所示为一个并行性分布图。
    并行性分布图

    2 .加速比

    1). 绝对加速比
    将最好的串行算法与并行算法相比较.(这里的“最好的”不是绝对的,有时处理最快的是最好的,有时的到最优解的是最好的,有时会把最快和最优结合起来,所以具体问题具体分析)
    定义一(与具体机器有关)将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。
    定义二(与具体机器无关)将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。
    在这里插入图片描述
    (分子表示串行机,分母表示并行机)
    2).相对加速比
    同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。
    这种定义侧重于描述算法和并行计算机本身的可扩展性。
    在这里插入图片描述
    由S表示形式,可以看出随着处理器数量N的增加,加速比S在增大,如果这种增加呈现线性关系,就称之为线性加速比;如果这种增加速度呈现超线性关系,就称之为超线性加速比;如果S增长速度逐渐呈现递减关系,就称之为病态加速比。
    线性加速比:中间开销小,通信少,弱耦合计算
    超线性加速比:当应用需要大内存时可能出现
    病态加速比:加速比递减,可能是计算量太小

    二、加速比性能模型(三种)

    1.固定负载加速比性能模型—Amdahl定律

    在许多实时应用领域,计算负载的大小经常固定。在并行机中,此负载可分布至多台并行执行,获得的加速比称为fixed-load speedup。一个问题的负载可表示如下:
    W = Ws + Wp
    其中,Ws代表问题中不可并行化的串行部分负载, Wp表示可并行化的部分负载。
    则n个节点情况下,加速比可以表示如下:

    在这里插入图片描述
    设串行因子α为串行部分所占的比例。即:
    在这里插入图片描述
    代入即得Amdahl’law:
    在这里插入图片描述
    不管采用多少处理机,可望达到的最好加速比:
    在这里插入图片描述
    效率En可以表示为:
    在这里插入图片描述
    处理机数目n越大,效率En越低。
    Amdahl定律告诉我们:系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。
    在这里插入图片描述
    加速比的两个决定因素:
    1).计算机执行某个任务的总时间中可被改进部分的时间所占的百分比,即可被改进部分占用时间/改进前整个任务的执行时间,记为Fe,它总小于1。
    2).改进部分采用改进措施后比没有采用改进措施前性能提高的倍数,即
    改进前改进部分执行时间/改进后改进部分执行时间,记为Se。
    在这里插入图片描述
    例1:
    假设将某系统的某一部件的处理速度加快到10倍,但该部件的原处理时间仅为整个运行时间的40%,则整个系统的性能提高了多少?
    解:Fe = 0.4,Se = 10,
    在这里插入图片描述
    Amdahl’law又称为固定规模加速比模型,问题规模不随处理机变化而变化。固定问题规模,看用并行技术能达到的最短时间是多少。
    在固定规模加速比模型下,负载和执行时间随系统中处理机数目n变化的情况如下图:
    在这里插入图片描述
    (不管处理机数量有多少,串行和并行的负载都是固定的。但是串行的工作时间是固定的,并行随着处理机的增加,所用的工作时间在减少,而总的时间也随着处理机的增大而减小)
    当处理器数目n=1024,加速比Sn随α变化的情况如下:
    在这里插入图片描述
    得出曲线如下图:
    在这里插入图片描述
    可以比较不同的α对加速比带来的不同影响:
    在这里插入图片描述
    (红色曲线为α=0,红色下边为α=0.01,蓝色为α=0.1,蓝色下边为α=0.9)
    α=0时得到理想加速比,当α值增加时,加速比性能急剧下降。
    **结论:**加速比曲线随α的上升急剧下降,原因是存在顺序部分Ws,无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。
    影响:两种意见:
    1).劝阻制造商生产大规模并行计算机。(当然与实际情况是不相符的,现在的处理机数量一直在增加。)
    2).研究并行编译器,以降低α的值,从而提高系统的性能。
    规定负载加速比模型的可能应用范围:
    对时间要求严格的应用问题。

    2.固定时间加速比性能模型—Gustafsun定律

    有许多应用领域强调精度而不是运行时间。1988年,Gustafsun提出了固定时间加速比模型。当机器的规模扩大时,解题的规模也随着扩大,从而得到更加精确的解,而使运行时间保持不变。
    比如:有限元方法做结构分析,流体动力学做天气预报解PDE(偏微分方程组)就需要提高精度。
    粗格要求的计算量较少,而细格的计算量多,得到的精确度也较高。天气预报模拟求解四维PDE,如果使每个实际方向(X,Y,Z)的格点距离减少到原来的十分之一,并以同一幅度增加时间步,那么可以说格点增加了104倍,因而工作负载也至少增大了10000倍。
    

    模型提出的背景:
    固定负载模型有缺陷:因为Amdahl’law中,α取决于问题及并行编译器的效率,无法描述系统固有的特性。
    加速比的公式:
    在这里插入图片描述
    其中,Wp’=nWp和Ws+Wp=Ws’+Wp’/n作为固定时间的条件。 Ws’+Wp’/n表示在扩大负载后在增加处理机台数的情况下的平均负载(执行时间),它应当和负载没有扩大情况下的平均负载(执行时间)Ws+Wp相等。即有Ws+Wp=Ws’+Wp’/n。同时,负载的串行部分并没有改变,即有Ws=Ws’。
    在固定时间加速比模型下,负载和执行时间随系统中处理机数目n变化的情况如下图:
    固定时间加速比模型下的负载和执行时间情况
    增大问题规模的办法使所有处理机保持忙碌状态,在问题扩大到与可用的计算能力匹配时,程序中的顺序部分就不再是瓶颈了。
    当处理器数目n=1024,加速比Sn随α变化的情况如下:
    在这里插入图片描述
    在这里插入图片描述

    3.受限于存储器的加速比模型

    1993年,由Sun和Ni提出。
    大型科学计算和工程设计需要较大的存储空间,许多应用问题是存储器受限,而不是CPU受限或者I/O受限。
    比如:在分布存储系统中常遇到,总存储容量随节点数线性增加,许多节点集合起来解一个大题。
    基本思想:要在存储空间有限条件下解尽可能大的问题,这同样需要扩展工作负载,才能提供较高的加速比、较高的精度和较好的资源利用率。
    

    加速比可以表示如下:
    在这里插入图片描述
    其中:
    在单个处理机上顺序执行的工作负载与问题的规模或系统的规模无关,即:
    在这里插入图片描述
    而G(n)反映的是存储容量增加n倍时并行工作负载增加的倍数。
    讨论:
    1.G(n) = 1,即为固定负载的情况;
    2.G(n) = n,即存储器增加n倍,负载也增加n倍,为固定时间的情形;
    3.G(n) > n,计算负载的增加情况比存储器增加快,会有较高的加速比。
    比较三种加速比,对于相同的处理机数量,有:
    在这里插入图片描述
    (Sun.Ni模型大于等于Gustafsun模型大于等于Amdahl模型)

    在受限于存储器的加速比模型下,负载和执行时间随系统中处理机数目n变化的情况如下图:
    受限于存储器的加速比模型下的负载和执行时间情况
    例:n维矩阵乘法:A * B = C,其中A、B、C都是n*n的方阵。为得到C的每一个元素需要进行n次乘法、n次加法,所以总的计算量为:(n+n)n2 = 2n3。需要的存储量为3n2(两个源矩阵,一个结果矩阵)。如果n台计算机组成多计算机系统,则存储容量扩大n倍,那么矩阵的维数(原来为n)也可以增加了,设为N倍,那么加速比为多少解:存储容量变为:nM = n 3n2 = 3n3,而N维需要的存储量为3N2,计算量变为2N3,则有:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    4.并行计算的应用模型

    随机器规模的增大,工作负载增长的模式如下图:
    在这里插入图片描述
    上图中:
    采用受限于存储器的加速比模型中给出的公式,
    θ曲线对应的G(n) = n的1.5次方(靠近y轴)
    γ曲线对应的G(n) = n(红色)
    β曲线对应的G(n) = 0.5n(蓝色)
    α曲线对应的G(n) = 1(靠近x轴)
    则有加速比公式:
    在这里插入图片描述
    给定一个程序,假设Ws/Wp = 0.4,那么效率为:
    在这里插入图片描述
    相应的处理器数目—效率曲线如下图:
    在这里插入图片描述
    相关结论:
    1.如果工作负载(问题规模)保持不变,那么效率E随机器规模的增大而迅速下降,其原因是开销h比机器规模增加得快,为了使效率保持在一定的水平上,我们可以按比例增大机器规模和问题规模。
    2.如果工作负载按指数增长模式,效率要保持恒定或保持良好的加速比,必须使问题规模猛增才行,这样就会超过存储器或I/O限制,而问题规模只允许在计算机存储器可用的限度以内增长。
    并行计算机的应用模型如下图:
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 并行计算三种方式计算π:概率法,积分法,级数法,代码中包括计算量和线程个数设置。 使用时进行编译后输入相应提示的数值即可,例如N=100000 t=8
  • 转载于:https://www.cnblogs.com/chihaoyuIsnotHere/p/10552793.html

     

     

     

     

     

    转载于:https://www.cnblogs.com/chihaoyuIsnotHere/p/10552793.html

    展开全文
  • win7下CUDA并行计算加速方案 win7下CUDA并行计算加速方案 win7下CUDA并行计算加速方案
  • 3、 比较以上三种算法的运行时间,计算加速比。2 实验设计2.1 生成方阵为方便,本实验的方阵不采取手动输入的方式,而是使用随机数来生成矩阵元素。我定义了一个全局方阵变量——int p[100][100...

    以下内容为本人并行计算课程的期末作业,有不足的地方,请多多指教!

    实验目的

    本实验的目的主要有以下三点:

    1 实现方阵行列式的计算。

    2 实现方阵行列式的并行计算,分别基于 OpenMP MPI

    3 比较以上三种算法的运行时间,算加速比。

    实验设计

    2.生成方阵

    为方便,本实验的方阵不采取手动输入的方式,而是使用随机数来生成矩阵元素。

    定义了一个全局方阵变——int p[100][100]在创建方阵时,方阵的阶数N(N<100)外部输入。然后用两层for循环来给方阵 p左上角 N×N个位置赋值。具体实现如下

    /*
     * 定义矩阵阶数N
     */
    
    int N;
    
    /*
     * 定义一个全局矩阵
     */
    
    int p[100][100];
    
    /*
     * 用随机数生成矩阵
     */
    
    void create(){
    	int i,j;
    	for(i=0;i<N;i++)
    	{
    		for(j=0;j<N;j++)
    	
    	     {
               int a=rand()%15;//产生随机数,并赋给数组
    	       p[i][j]=a;
    		 }
    	}
    }


    2.打印矩阵

    将生成的矩阵输出,以便验算其计算行列式的正确性。具体实现如下:

    /*
     * 输出矩阵
     */
    
    void print()
    {
    	int i,j;
    	for(i=0;i<N;i++)
        {
    		for(j=0;j<N;j++)
    			printf("%d ",p[i][j]);
    		printf("\n");
    	}
    }

    2.计算矩阵行列式

    计算矩阵行列式的方法有很多,本实验选择的方法是:行列式按行展开法。行列式等于它任一行的各元素与其对应的代数余子式乘积之和。代数余子式:A(ij)=-1)^(i+j)M(ij).  (ij)为下标。某个元素的余子式等于原行列式划去该元素所在的行和列。本实验采取按第一行展开的方法。即:将高阶的行列式按第一行展开,一直重复展开行为,直到阶数为 1。上述过程可用递归完成。

    2.3.递归实现代码

    根据上面的理论,我们容易得出如下的实现方法:

    /*
     * 计算行列式的函数
     */
    
    long long mydet(int  p [100][100],int n){
    	if(n==1)  //n=1返回矩阵的唯一数,停止递归
    		return p[0][0];
    	else{
    		long long sum=0;
    		for(int i=0;i<n;i++)
    		{
    			    int pp[100][100];//用于存放少一维的矩阵,为方便直接定义为100×100.
    			for(int j=1,j1=0;j<n;j++)//去掉第一行
    			{
    				for(int k=0,k1=0;k<n;k++)
    				{
    					if(k==i)
    						;//去掉对应的列
    					else
    					{
    
    				     pp[j1][k1]=p[j][k];//pp为余子式	
    					 k1++;
    					}
    				}
    			    j1++;
    			}
    			if(i%2)
                    sum+=(-1)*p[0][i]*mydet(pp,n-1);
    			else
    				sum+=p[0][i]*mydet(pp,n-1);
    		}
    		return sum;
    	}
    }

    2.4  实现串行\OpenMP\MPI计算

    我这里的并行主要是放在第一次的按行展开那,具体实现看代码吧。

    2.4.1  串行代码

    /*************************************************************************
        > File Name: matrix_det.c
        > Author: surecheun
        > Mail: surecheun@163.com
        > Created Time: 2017年12月06日 星期三 17时28分00秒
     ************************************************************************/
    #include<stdlib.h>
    #include<stdio.h>
    #include<math.h>
    #include<time.h>
    #include<time.h>
    /*
     * 定义矩阵阶数N
     */
    
    int N;
    
    /*
     * 定义一个全局矩阵
     */
    
    int p[100][100];
    
    /*
     * 用随机数生成矩阵
     */
    
    void create(){
    	int i,j;
    	for(i=0;i<N;i++)
    	{
    		for(j=0;j<N;j++)
    	
    	     {
               int a=rand()%15;//产生随机数,并赋给数组
    	       p[i][j]=a;
    		 }
    	}
    }
          
    /*
     * 输出矩阵
     */
    
    void print()
    {
    	int i,j;
    	for(i=0;i<N;i++)
        {
    		for(j=0;j<N;j++)
    			printf("%d ",p[i][j]);
    		printf("\n");
    	}
    }
    
    /*
     * 计算行列式的函数
     */
    
    long long mydet(int  p [100][100],int n){
    	if(n==1)  //n=1返回矩阵的唯一数,停止递归
    		return p[0][0];
    	else{
    		long long sum=0;
    		for(int i=0;i<n;i++)
    		{
    			    int pp[100][100];//用于存放少一维的矩阵,为方便直接定义为100×100.
    			for(int j=1,j1=0;j<n;j++)//去掉第一行
    			{
    				for(int k=0,k1=0;k<n;k++)
    				{
    					if(k==i)
    						;//去掉对应的列
    					else
    					{
    
    				     pp[j1][k1]=p[j][k];//pp为余子式	
    					 k1++;
    					}
    				}
    			    j1++;
    			}
    			if(i%2)
                    sum+=(-1)*p[0][i]*mydet(pp,n-1);
    			else
    				sum+=p[0][i]*mydet(pp,n-1);
    		}
    		return sum;
    	}
    }
    
    int main(){
    	printf("N= ");
    	scanf("%d",&N);
        while(N){       //如果输入N就可以继续算下去,这个设计主要为了方便获取时间数据来计算平均用时
    		create();
    		print();
    		clock_t start_t=clock();  //开始计时
    		printf("the sum of 串行 is %lld .\n",mydet(p,N));
    	         clock_t  end_t=clock();  //结束计时
    		double   runing_t =(double)(end_t-start_t)/CLOCKS_PER_SEC;
    		printf("the runing time of 串行 is %f s.",runing_t);  //输出时间
    		printf("\n");
    		printf("N= ");
    		scanf("%d",&N);
    	}
     
    	return 0;
    }
    

    2.4.2 OpenMP代码

    /*************************************************************************
        > File Name: matrix_det_omp.c
        > Author: surecheun
        > Mail: surecheun@163.com
        > Created Time: 2017年12月07日 星期四 17时23分51秒
     ************************************************************************/
    
    #include<stdlib.h>
    #include<stdio.h>
    #include<math.h>
    #include<vector>
    #include<time.h>
    #include<omp.h>
    
    /*
     * 定义线程数
     */
    #define n_threads 2
    
     /*
     *定义矩阵的阶数为全局变量
     */
    
    int N;
    
    /*
     * 定义一个全局矩阵
     */
    
    int p[100][100];
    
    /*
     * 用随机数生成矩阵
     */
    
    void create(){
    	int i,j;
    	for(i=0;i<N;i++)
    	{
    		for(j=0;j<N;j++)
    	
    	     {
               int a=rand()%15;//产生随机数,并赋给数组
    	       p[i][j]=a;
    	     }
    	}
    }
          
    /*
     * 输出矩阵
     */
    
    void print()
    {
    	int i,j;
    	for(i=0;i<N;i++)
        {
    		for(j=0;j<N;j++)
    			printf("%d ",p[i][j]);
    		printf("\n");
    	}
    }
    
    /*
     * 计算行列式的函数
     */
    
    long long mydet(int  p [100][100],int n){
    	if(n==1)  //n=1返回矩阵的唯一数,停止递归
    		return p[0][0];
    	else{
    		long long sum=0;
    		for(int i=0;i<n;i++)
    		{
    		    int pp[100][100];
    			for(int j=1,j1=0;j<n;j++)//去掉第一行
    			{
    				for(int k=0,k1=0;k<n;k++)
    				{
    					if(k==i)//去掉和改数相同的列
    						;
    					else
    					{
    
    				     pp[j1][k1]=p[j][k];	//pp为代数余子式
    					 k1++;
    					}
    				}
    			    j1++;
    			}
    			if(i%2)
                                              sum+=(-1)*p[0][i]*mydet(pp,n-1);
    			else
    				sum+=p[0][i]*mydet(pp,n-1);
    		}
    		return sum;
    	}
    }
    
     
    int main(){
    	printf("N= ");
    	scanf("%d",&N);
        while(N){       //如果输入的N>0,则继续计算
    		create();  //创建矩阵
    		print();   //打印创建的矩阵
    		  double start1,finish1;
                        start1=omp_get_wtime();  //开始计算时间
                        long long sum=0;
                 omp_set_num_threads(n_threads);//设置线程数
               #pragma omp parallel for reduction(+:sum)//并行化
           for(int i=0;i<N;i++)
    		{
    		    int pp[100][100];
    			for(int j=1,j1=0;j<N;j++)//去掉第一行
    			{
    				for(int k=0,k1=0;k<N;k++)
    				{
    					if(k==i)//去掉和i相同的列
    						;
    					else
    					{
    
    				     pp[j1][k1]=p[j][k];	//pp为余子式
    					 k1++;
    					}
    				}
    			    j1++;
    			}
    			if(i%2)
    				sum+=(-1)*p[0][i]*mydet(pp,N-1);
    			else
    				sum+=p[0][i]*mydet(pp,N-1);
    		}
            printf("the sum of omp is %lld .\n",sum);//输出结果
    	    finish1=omp_get_wtime();   //结束计算时间
    		double   runing_t =finish1-start1;
    		printf("the runing time of opm is %f s.",runing_t);//输出时间
    		printf("\n");
    		printf("N= ");
    		scanf("%d",&N);
    	}
    	return 0;
    	}
    

    2.4.3 MPI实现代码

    /*************************************************************************
        > File Name: matrix_det_mpi.c
        > Author: surecheun
        > Mail: surecheun@163.com
        > Created Time: 2017年12月07日 星期四 16时24分03秒
     ************************************************************************/
    
    #include<stdlib.h>
    #include<stdio.h>
    #include<math.h>
    #include<time.h>
    #include<mpi.h>
    
    /*
     *定义矩阵的阶数为全局变量
     */
    
    int N;
    
    /*
     * 定义一个全局矩阵
     */
    
    int p[100][100];
    
    /*
     * 用随机数生成矩阵
     */
    
    void create(){
    	int i,j;
    	for(i=0;i<N;i++)
    	{
    		for(j=0;j<N;j++)
    	
    	     {
               int a=rand()%15;//产生随机数,并赋给数组
    	       p[i][j]=a;
    	     }
    	}
    }
          
    /*
     * 输出矩阵
     */
    
    void print()
    {
    	int i,j;
    	for(i=0;i<N;i++)
        {
    		for(j=0;j<N;j++)
    			printf("%d ",p[i][j]);
    		printf("\n");
    	}
    }
    
    /*
     * 计算行列式的函数
     */
    
    long long mydet(int  p [100][100],int n){
    	if(n==1)  //n=1返回矩阵的唯一数,停止递归
    		return p[0][0];
    	else{
    		long long sum=0;
    		for(int i=0;i<n;i++)
    		{
    		    int pp[100][100];
    			for(int j=1,j1=0;j<n;j++)//去掉第一行
    			{
    				for(int k=0,k1=0;k<n;k++)
    				{
    					if(k==i)
    						;
    					else
    					{
    
    				     pp[j1][k1]=p[j][k];	
    					 k1++;
    					}
    				}
    			    j1++;
    			}
    			if(i%2)
                    sum+=(-1)*p[0][i]*mydet(pp,n-1);
    			else
    				sum+=p[0][i]*mydet(pp,n-1);
    		}
    		return sum;
    	}
    }
    
    
    
    int main(int argc,char *argv[]){  
    	  scanf("%d",&N);
          int num_procs,my_rank;    
          double start = 0.0, stop = 0.0;  //记录时间的变量
          long long  per_procs = 0.0;  //记录每个进程算的和
          long long  result = 0.0;  //矩阵行列式结果
          MPI_Init(&argc, &argv);  
          MPI_Comm_size(MPI_COMM_WORLD, &num_procs);  
          MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);  
          if (my_rank == 0)
    	  {//0号线程创建矩阵
            create(); 
            print(); //打印创建的矩阵
           }  
         start = MPI_Wtime();   //开始计算时间
     
          MPI_Bcast(&N, 1, MPI_INT, 0, MPI_COMM_WORLD);    //将矩阵大小广播给所有进程  
          for (int i = 0; i <N; i++)
    	  {  
          MPI_Bcast(p[i],N, MPI_INT, 0, MPI_COMM_WORLD);  
          }           //将矩阵广播给所有进程  
       
          for (int i = my_rank; i <N; i += num_procs){ //每个线程处理不同的行和列 
                long long sum_i=0;
    		    int pp[100][100];
    			for(int j=1,j1=0;j<N;j++)//去掉第一行
    			{
    		    	for(int k=0,k1=0;k<N;k++)
    				{
    					if(k==i)
    						;
    					else
    					{
    				     pp[j1][k1]=p[j][k];	
    					 k1++;
    					}
    				}
    			    j1++;
    			}
           if(i%2)
                    sum_i=(-1)*p[0][i]*mydet(pp,N-1);
          else
    		sum_i=p[0][i]*mydet(pp,N-1);
            per_procs += sum_i;  //记录每个进程的和
        }  
        MPI_Reduce(&per_procs, &result, 1, MPI_LONG_LONG_INT, MPI_SUM, 0, MPI_COMM_WORLD);//在0号进程求总和  
        if (my_rank == 0){  
            printf("the sum of mpi is %lld .\n",result) ; 
            stop = MPI_Wtime();  //结束计算时间
            printf("the time of mpi is %f s\n", stop - start);  
            fflush(stdout);  
        }  
        MPI_Finalize();
        return 0;  
    }  
    
    

    4 实验结果

    4.1 正确性

    4.1.1串行

    结果分析,以 n=4为例,输出的矩阵为:

    13

    1

    12

    10

    8

    10

    1

    12

    9

    1

    2

    7

    5

    4

    8

    1




    输出结果为:3875

    和matlab计算结果一致!

    4.1.2 OpenMP

    结果分析,以 n=4为例,输出的矩阵为:

    5

    0

    8

    1

    1

    5

    11

    3

    2

    5

    1

    1

    0

    0

    14

    12







    输出结果为:-2710

    和matlab计算结果一致!

    4.1.3 MPI

    结果分析,以n=4为例,输出矩阵为:

    9

    1

    2

    7

    5

    4

    8

    1

    0

    6

    7

    1

    11

    8

    12

    9







    输出结果为:-202

    和matlab计算结果一致!

    4.2 加速比

    通过多次求平均,得到三种计算实现方法的计算时间(保留 3 位有效数字)如下:

     

    N(数)

    串行

     

    OpenMP

     

    MPI

     

    9

     

    0.0239s

     

    0.0117s

     

    0.0117s

     

    10

     

    0.195s

     

    0.105s

     

    0.100s







    柱状图如下:


    展开全文
  • 什么是并行计算

    千次阅读 多人点赞 2020-01-15 14:26:19
    原文出处:并行计算简介 并行计算简介 (本人刚刚完成这篇长文章的翻译,尚未认真校对。若里面有翻译错误和打字错误敬请谅解,并请参考原贴) 1 摘要 最近项目需要实现程序的并行化,刚好借着翻译这篇帖子的机会...
  • 线程池之前用过,但其实没有遇到过大量计算时候,还是没有进行过深入的了解和比较,正好,这次需要用到多线程并行计算并且同时返回计算结果的这么一个需求,网上找了一大圈,可能是搜索方式不对吧,相应的介绍比较少...
  • 每一次遇到问题和解决问题都是一种锻炼,一种尝试,从我们上并行计算课我懂得了很多电脑硬件和软件的知识,这些可能对于我们这个专业以后都是没有机会接触的,所以我觉得选择了并行计算与多核多线程技术这门课是非常...
  • 重建图像为2种和4种时,与重复执行多次单能CT并行重建相比,本文方法的重建过程加速比分别为1.88和3.24,其中最耗时反投影步骤加速比分别为1.90和3.66。实验和实际应用证明了该方法可有效提高双能CT重建的准确性和速度...
  • 1. 设计目的、意义(功能描述) 2. 方案分析(解决方案) 3. 设计分析 3.1 串行算法设计 ...3.2 并行算法设计 ...3.3 理论加速比分析 ...4.1 基于OpenMP的并行算法实现 ...4.1.2 实验加速比分析 ...4.6.2 实验加速比分析
  • Tp为使用p个处理器并行计算所花费的时间。 不能达到最佳效果(理论值)的原因: 1.不是每一部分的计算都能够并行优化 2.在并行化的过程在可能需要额外的计算或操作(如同步造成的开销) 3.进程间通信需要时间(这...
  • 并行计算的性能指标

    千次阅读 2018-10-21 10:55:41
    加速比 S 等于并行计算的核数 p,则称该并行程序具有线性加速比(linear speedup)。实际上,我们不可能获得线性加速比,因为多个线程/进程总是会引入一些代价。 此外,定义 E = S/p 的值为并行程序的效率。一般...
  • 提出一种蒙特卡洛方法并行计算高分子的单链性质,高分子链采用自回避行走方法生成初始...利用样本之间的独立性进行并行计算达到线性加速比,使蒙特卡洛模拟高分子链的并行计算时间缩短到科学计算可以接受的时间范围。
  • 并行计算圆周率π

    千次阅读 2016-10-19 10:21:44
    简单说明除了“数据挖掘与机器学习”,学院还开了“分布与并行计算”这门课,同样也是要求我们计算机1、2班的同学都选修这门课。 采用并行的方式计算π,是这门课的第二个实验内容,看起来很简单,实际上也很简单,...
  • [并行计算] 1. 并行计算简介

    万次阅读 多人点赞 2017-07-20 15:30:07
    这篇帖子旨在为并行计算这一广泛而宏大的话题提供一个非常快速的概述,作为随后教程的先导。因此,它只涵盖了并行计算的基础知识,实用于刚刚开始熟悉该主题的初学者。
  • 每一次遇到问题和解决问题都是一种锻炼,一种尝试,从我们上并行计算课我懂得了很多电脑硬件和软件的知识,这些可能对于我们这个专业以后都是没有机会接触的,所以我觉得选择了并行计算与多核多线程技术这门课是非常...
  • 为解决串行时域多分辨率(MRTD)散射... 通过增加中央处理器核数, 程序的并行加速比随之增大, 但单核运行效率却略有降低。随着粒子尺度参数的增大, 单核计算效率随之增加, 复折射率的改变并不会显著影响并行计算效率。
  • 并行计算机未来发展前景

    千次阅读 2016-11-24 20:37:47
    20世纪60年代初期, 由于晶体管以及磁芯...现代计算机的发展历程可以分为2个时代:串行计算时代和并行计算时代。并行计算是在串行计算的基础上发展起来的。并行计算将一项大规模的计算任务交由一组相同的处理单元共同完
  • 并行计算与MPI

    万次阅读 多人点赞 2019-06-01 16:54:08
    并行计算 1.1. 相关背景 (1)从1986年到2002年,微处理器的性能以平均50%的速度不断提升。但从2002年开始,单处理器的性能提升速度下降到每年大约20%,这个差距是巨大的。所以,从2005年起,大部分主流的CPU制造商...
  • 计算机并行计算考试重点总结

    千次阅读 2016-12-06 22:21:28
    **计算机体系结构由程序设计者看到的...计算机系统的层次结构 现代并行计算机的组成 ü硬件核心:处理机、存储器和外围设备组成了计算机系统。 ü互连:外围设备可以直接或通过局域网和广域网与主机相连。 ü映射
  • 它经常用于并行计算领域,用来预测适用多个处理器时理论上的最大加速比。在我们的性能调优领域,我们利用此定律有助于我们解决或者缓解性能瓶颈问题。 阿姆达尔定律的模型阐释了我们现实生产中串行资源争用时候的...
  • 本书系统介绍涉及并行计算的体系结构、编程范例、算法与应用和标准等。覆盖了并行计算领域的传统问题,并且尽可能地采用与底层平台无关的体系结构和针对抽象模型来设计算法。书中选择MPI(Message Passing Interface)...
  • 大型铝电解槽的数值仿真采用有限元分析方法,伴随着有限元模型的大型化、...数值分析结果表明:基于ANP算法的有限元并行计算方法在面对铝电解槽这类复杂三维模型时能够取得良好的划分结果,进而得到较优的并行计算加速比
  • CUDA 高性能并行计算入门

    万次阅读 多人点赞 2018-03-09 10:40:08
    CUDA 高性能并行计算入门 (UPDATE IN 2018.3.8) 1.更新pitch索引操作的描述 概述 什么是CUDA? CUDA(Compute Unified Device Architecture)是 NVIDIA公司开发的一种计算架构,可以利用NVIDIA系列显卡对一些...
  • 武汉理工大学-并行计算-2020年期末复习指南

    千次阅读 多人点赞 2020-10-31 15:33:53
    武汉理工大学-并行计算-2020年期末复习指南
  • 实验结果表明,提出的并行计算框架在处理数据密集型和计算密集型的海洋数据的效率上优于原生的Hadoop云平台,可达到6~8倍的加速比。因此,提出的云平台框架可以有效提高海洋信息可视化的计算效率,对我国海洋事业的...
  • 一、数据划分和处理器指派 1. 带状划分方法 又叫做行列划分,就是将矩阵的整行或整列分成若干组,各组指派给一个处理器。 例如:设矩阵A由n行和m列,对其串行处理的... 现在有p个处理器,可以并行的去处理。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,614
精华内容 16,645
关键字:

并行计算加速比计算