典型问题实例分析

1、3 典型问题并行实例分析n什么样的问题适合并行计算？n斐波那契序列(Fibonacci)的计算？n什么样的问题适合并行计算？n如果有大量结构一致的数据要处理，且数据可以分解成相同大小的部分， 那我们就可以设法使这道处理变成并行主要内容 3.1 易并行计算问题(分形图形并行生成) 3.2 数值计算(矩阵运算) 3.3 数排序问题 (流水线) 3.1 易并行计算问题 一个理想的并行计算是能被立即分解成许多完全独立部分且它们被同时执行的计算，这种情况被称为易并行。真正意义上的易并行计算意味着在各个进程间没有通信。 近似易并行计算是那种需将计算结果分布和收集，以及用某种方式加以组合的计算。这就意味着在

2、开始和最后只有一个进程处于运行状态。如果要创建动态进程，通常的方法是采用主从结构。首先创建一个主进程，由它启动相同的从进程。分布式图像处理 解决复杂图形应用问题的行之有效的方法是把复杂问题划分为可以并发执行的若干子任务，使它们并行执行。从而在联网的计算机系统中实现并行机才能够解决的问题。 存储一个二维图像的最基本方法是使用像素图，即位图。 图像处理输入数据是位图/像素图。通常存于文件中并被复制到数组中。并行编程主要关心将位图/像素图分成一些像素组以供每个处理器加工。实例1：分形图形的并行处理分形图形原理 Julia 集是由法国数学家 Gaston Julia 和 Pierre Faton 在发

3、展了复变函数迭代的基础理论后获得的。 Julia 集是一个典型的分形。由一个复变函数生成， 其中c为常数。由于c可以是任意值，所以当c取不同的值时，制出的图形也不相同。 u等于0时，两个吸引区域中间的边界即 Julia 集。当u u0 0，即控制参数变化时，JuliaJulia集构成各种各样的分维结构C0时两个吸引区域之间的分形边界 在控制参数u0时：分形出现了。U=-1 情况下的Julia集c = 0 . 1 + i 0 . 8 情况下的Julia集c = 0 . 3 i 0 . 4 情况下的Julia集 对于复映射zn+1zn2+u,我们也可以在复参数平面(p,q)上讨论，这种情况下不是取

4、定u，而是取定z0。定义:能够使上述|Zn|有界的点集(p,q)即为Mandelbrot集。若Z0=0 得到轨道0,u,u2+u, (u2+u)2+u, .n只要上述轨道上任何一点复数模大于2，则|Zn|趋向无穷。于是，该点集(p,q)就不属于Mandelbrot集。若Z0=0 得到轨道0,u,u2+u, (u2+u)2+u, . Zk+1Zku 对于复平面上的复数a+bi，Z的初值为0， Zk+1是复数za+bi的第k+1次迭代， Zk是z的第k次迭代，u是确定该点在复数平面中位置的复数值，迭代一直进行下去，直到|Zn|4或达到了一定的迭代次数。 若结果集合在64*64个像素区域内显示，则复

5、平面上需要计算64*64个像素点，根据每个像素点在复平面上的位置进行迭代。记录每个像素点的迭代次数值，将该值作为该像素点的颜色值进行显示。如256色，则对应到256种颜色中其中的一个颜色进行显示。分形图形并行处理的实现系统利用PVM的消息传递机制，采用Master/Slave模式来完成进程之间的异步通信。主进程(Master)负责进程的生成，初始化，收集并显示计算结果。从进程(Slave)执行实际的计算，其负载是由主进程动态分配，不受节点机性能不同或变化的影响。 一个PVM虚拟机的结构示意图 PVM虚拟机主节点从节点1从节点2主PVMD任务1任务2从PVMD1任务3任务4从PVMD2任务5任务

6、6发送方接收方消息发送数据发送缓冲区打包数据接收缓冲区解包PVM进程间发送/接收数据过程主进程程序流程图Masterfor(i=0,row=0;i480;i+,row=row+10) send(&row,Pi);for(i=0;i(480*640);i+) recv(&c,&color,Pany);display(c,color);从进程数据流向图Slave(process i)recv(&row,Pmaster)for(x=0;xdisp_width;x+)for(y=row;y(row+10);y+) c.real=min_real+(float)x*sca

7、le_real) c.imag=min_imag+(float)y*scale_imag) z=z+c ; while |z|4 or cal_pixel(c)k) then /* a循环左移至同行相邻处理器中 */Leftmoveonestep(a)end if if(jk) then /* b循环上移至同列相邻处理器中 */Upmoveonestep(b)end ifend for(3) for i = 0 to m-1 dofor j = 0 to m-1 do ci,j = 0end for end for(4) for k = 0 to -1 dofor i = 0 to -1 do

8、for j = 0 to -1 dofor k1 = 0 to -1 do ci,j = ci,j + ai,k1 * bk1,jend forend forend forLeftmoveonestep(a)/*子块a循环左移至同行相邻的处理器中 */Upmoveonestep(b)/* 子块b循环上移至同列相邻的处理器中 */end forEnd函数Leftmoveonestep（a）为例，给出处理器间交换数据的过程，如算法4： 算法4：函数Leftmoveonestep（a）的基本算法Begin(1) if (j = 0) then /* 最左端的子块 */(1.1) 将所存的A的子块发送

9、到同行最右端子块所在的处理器中(1.2) 接收其右邻处理器中发来的A的子块end if(2) if(j = -1) and (j mod 2 = 0) then /* 最右端子块处理器且块列号为偶数 */(2.1) 将所存的A的子块发送到其左邻处理器中(2.2) 接收其同行最左端子块所在的处理器发送来的A的子块end if(3) if (j = -1) and (j mod 2 0) then /* 最右端子块处理器且块列号为奇数 */(3.1)将所存的A的子块在缓冲区buffer中作备份(3.2)接收其同行最左端子块所在的处理器发送来的A的子块(3.3)将在缓冲区buffer中所存的A的子块

10、发送到其左邻处理器中 end if(4) if(j -1) and (j mod 2 = 0) and (j 0) then /* 其余的偶数号处理器 */(4.1) 将所存的A的子块发送到其左邻处理器中(4.2) 接收其右邻处理器中发来的A的子块end if (5) if(j -1) and (j mod 2 = 1) and (j 0) then /* 其余的奇数号处理器 */(5.1) 将所存的A的子块在缓冲区buffer中作备份(5.2) 接收其右邻处理器中发送来的A的子块(5.3) 将在缓冲区buffer中所存的A的子块发送到其左邻处理器中 end if End分成四个子任务的情况：

11、3.3 数的排序(流水线技术应用实例) 在流水线技术中，问题被分成一些列必须一个接一个完成的任务。每个任务由分离的过程或处理器执行，如图所示。一个流水线过程成为一个流水线级。每一级只解决问题的一部分并且把相关的信息传送给需要它的下一级。这种并行性可以看成是功能分解的一种形式。问题被划分为必须执行的独立的功能，而且在这种情况下这些功能必须被连续执行。 流水线技术描述 一个简单的循环： for (i = 0; i x) send(&x, Pi+1); x = number; else send(&number, Pi+1);数的排序问题描述(3) 对于n个数，第i个进程要接收n-i个数，它要上传n-i-1个数，因此可以使用一个简单的循环： right_procno=n-i-1 recv(&