资源描述：
《并行计算完全并行计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章完全（易）并行计算完全并行计算：一个计算任务可明显地分为若干个完全独立的部分，而每一部分可由一个独立的处理机（进程）来执行的计算。各个进程之间没有通信或只有极少的通信，即每个进程在完成它的任务时不需要与其它进程进行交互。实际上，我们常处理的一些问题是近似完全并行的计算任务。如：主/从结构中，主进程把计算数据分给各个从进程；各个从进程采用完全并行计算方式完成局部的计算任务；主进程收集计算结果，综合出整个计算任务的最终结果。在主/从结构中，我们可以使用SPMD的程序设计模式：if(process-id==Master)主进程的代码；else从进程的代码；时间主进程从进程spawn();发送
2、初始数据汇集结果recv();send();send();recv();完全并行实例图像的几何变换分形应用----Mandelbrot集蒙特卡罗法存储一个2维图像的最基本的方法是利用像素图(pixmap)，它是一个2维数组且数组的每个元素是一个二进制数，这个二进制数表示了该像素的颜色和亮度。像素(pixel)：是屏幕上能显示的最小可编址单元，也是可控制的最小屏幕区域。单位面积内的像素越多，其分辨率越高；每个像素所使用的二进制位数越多，图像色彩越丰富。图像的几何变换图象处理中常见的几何变换：移位(shifting)x’=x+Δx其中Δx为图像在x方向的移动量y’=y+ΔyΔy为图像在y方向的移
3、动量缩放(scaling)x’=xSx其中Sx为图像在x方向的缩放系数y’=ySySy为图像在y方向的缩放系数旋转(rotation)x’=xcosθ+ysinθ其中θ为绕坐标系原点旋转的角度y’=-xsinθ+ycosθ剪裁(clipping)xl≤x’≤xh其中(xl,yl)为剪裁图像的左上角坐标yl≤y’≤yh(xh,yh)为剪裁图像的右下角坐标假设图像为640*480的像素图，共有48个处理机可以对图像（被操作的数据）按下列形式进行划分：分为80*80的方阵分为640*10的长方阵主进程程序：假设map[480][640]存有原像素图for(i=0,row=0;i<48;i++,ro
4、w=row+10)send(&row,delta_x,delta_y,Pi);/*senddatatoeachprocess*/for(i=0;i<480;i++)/*initializetemp*/for(j=0;j<640;j++)temp_map[i][j]=0;/*0isblack*/for(i=0;i<(640*480);i++){/*foreachpixelacceptnewcoords*/recv(oldrow,oldcol,newrow,newcol,Pany);if!((newrow<0
5、
6、newrow>=480
7、
8、newcol<0
9、
10、newcol>=640))temp_m
11、ap[newrow][newcol]=map[oldrow][oldcol];}for(i=0;i<480;i++)/*updatebitmap*/for(j=0;j<640;j++)map[i][j]=temp_map[i][j];从进程程序:/*recvrowno.*/recv(row,delta_x,delta_y,Pmaster);/*transformcoords*/for(oldrow=row;oldrow<(row+10);oldrow++)for(oldcol=0;oldcol<640;oldcol++){newrow=oldrow+delta_x;/*shiftinXdir
12、ection*/newcol=oldcol+delta_y;/*shiftinYdirection*/send(oldrow,oldcol,newrow,newcol,Pmaster);}从进程中最后一个语句：send(oldrow,oldcol,newrow,newcol,Pmaster);其通信效率很低，实际上我们可以将该从进程计算出的所有结果（或部分结果）组成一个较大的消息进行发送，从而降低整个消息启动时间。算法分析假设每个像素需要1个单位的计算时间，共有n*n个像素相应的串行算法的时间复杂性为：(n2)并行算法的时间复杂性：通信时间+计算时间通信时间：tcomm=tstartup+
13、mtdata主进程将各数据块的启始行号通知p个从进程：p*(tstartup+3tdata)主进程将从各个从进程接收n2个消息，每个消息传送4数据项：n2*(tstartup+4tdata)总的通信时间为：p*(tstartup+3tdata)+n2*(tstartup+4tdata)=(p+n2)*tstartup+(3p+4n2)*tdata=(p+n2)计算时间：tcomp=(n2/p)算法执行时间
