典型问题实例分析精要.ppt

3 典型问题并行实例分析 主要内容 3.1 易并行计算问题(分形图形并行生成) 3.2 数值计算(矩阵运算) 3.3 数排序问题 (流水线) 3.1 易并行计算问题 一个理想的并行计算是能被立即分解成许多完全独立部分且它们被同时执行的计算，这种情况被称为易并行。真正意义上的易并行计算意味着在各个进程间没有通信。 近似易并行计算是那种需将计算结果分布和收集，以及用某种方式加以组合的计算。这就意味着在开始和最后只有一个进程处于运行状态。如果要创建动态进程，通常的方法是采用主从结构。首先创建一个主进程，由它启动相同的从进程。 分布式图像处理 解决复杂图形应用问题的行之有效的方法是把复杂问题划分为可以并发执行的若干子任务，使它们并行执行。从而在联网的计算机系统中实现并行机才能够解决的问题。 存储一个二维图像的最基本方法是使用像素图，即位图。 图像处理输入数据是位图/像素图。通常存于文件中并被复制到数组中。并行编程主要关心将位图/像素图分成一些像素组以供每个处理器加工。 实例1：分形图形的并行处理 当u≠0，即控制参数变化时，Julia集 构成各种各样的分维结构 在控制参数u≠0时：分形出现了。 只要上述轨道上任何一点复数模大于2，则|Zn|趋向无穷。于是，该点集(p,q)就不属于Mandelbrot集。 Zk+1→Zk２＋u 对于复平面上的复数a+bi，Z的初值为0， Zk+1是复数z＝a+bi的第k+1次迭代， Zk是z的第k次迭代，u是确定该点在复数平面中位置的复数值，迭代一直进行下去，直到|Zn|4或达到了一定的迭代次数。 若结果集合在64*64个像素区域内显示，则复平面上需要计算64*64个像素点，根据每个像素点在复平面上的位置进行迭代。记录每个像素点的迭代次数值，将该值作为该像素点的颜色值进行显示。如256色，则对应到256种颜色中其中的一个颜色进行显示。 分形图形并行处理的实现 系统利用PVM的消息传递机制，采用Master/Slave模式来完成进程之间的异步通信。 主进程(Master)负责进程的生成，初始化，收集并显示计算结果。从进程(Slave)执行实际的计算，其负载是由主进程动态分配，不受节点机性能不同或变化的影响。 Master for(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); 在800*600的分辨率下，在两个节点中并行生成分形图形的实际加速比在PVM和MPI中分别为： Sp=12/9=1.33 Sm=16/11=1.45 在三个节点共同进行并行计算生成的分形图形的实际加速比分别为： Sp=12/7=1.71 Sm=16/8=2 3.2 数值计算--矩阵运算 矩阵运算是数值计算中最重要的一类运算，特别是在线性代数和数值分析中，它是一种最基本的运算。许多科学问题的基础都是矩阵。稠密矩阵的运算包括矩阵转置、矩阵和向量相乘以及矩阵相乘等。 矩阵是一些数的二维数组。一个n×m的矩阵有n行和m列元素，通常用二维数组来存储一个矩阵。 矩阵相乘串行算法 算法1：输入：Am×n， Bn×k 输出：Cm×k ? for i=0 to m-1 do for j=0 to k-1 do c[i,j] =0 for r=0 to n-1 do c[i,j]=c[i,j]+a[i,r]*b[r,j] 矩阵相乘并行算法 矩阵的划分方法 矩阵的两种常见的划分方法，即行列划分（带状划分）和棋盘划分（块状划分）。 所谓带状划分（Striped Partitioning）就是将矩阵整行或整列地分成若干个组，每组指派给一个处理器。也可将若干行或若干列指派给一个处理器，而且这些行和列可以是连续的，也可以是等距相间的。 对于一个n*n的矩阵和p个处理器（编号为P0,P1,···Pp-1）而言，每个处理器将均匀连续地分配有n/p列，其中Pi包含有列（n/p）i，（n/p）i+1,···（n/p）（i+1）-1,0≤i≤p-1。 所谓棋盘划分（Checker Board Partitioning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任意处理器均不