并行程序设计Chapter3

1、1第3章 易并行计算Embarrassingly Parallel Computations1 1、IDEAL PARALLEL COMPUTATIONIDEAL PARALLEL COMPUTATION2 2、EMBARRASSINGLY PARALLEL EMBARRASSINGLY PARALLEL EXAMPLES EXAMPLES Geometrical Transformation of Images Geometrical Transformation of Images 图形的几何变图形的几何变 换换 Mandelbrot Set Mandelbrot Set 曼德勃罗特集曼德

2、勃罗特集 Monte Carlo Methods Monte Carlo Methods 蒙特卡罗法蒙特卡罗法23.1 IDEAL PARALLEL COMPUTATION3.1 IDEAL PARALLEL COMPUTATION Embarrassingly Parallel ComputationsEmbarrassingly Parallel Computations A computation that can A computation that can obviously obviously be divided into a be divided into a number o

3、f number of completely independentcompletely independent parts, each of parts, each of which can be executed by a separate process(or).which can be executed by a separate process(or). This means there are no communications between This means there are no communications between everyevery processproc

4、ess. .3 No communication or very little communication No communication or very little communication between processes between processes Each process can do its tasks without any Each process can do its tasks without any interaction with other processes interaction with other processes3.1 IDEAL PARAL

5、LEL COMPUTATION3.1 IDEAL PARALLEL COMPUTATION43.1 IDEAL PARALLEL COMPUTATIONNearly embarrassingly parallel computationsNearly embarrassingly parallel computationsare those that require results to be distributedare those that require results to be distributedand combined in some way. This means only

6、one and combined in some way. This means only one process is running at first and at cess is running at first and at last. Master-slave structure Master-slave structure Static process creation Static process creation Dynamic process creation Dynamic process creation53.1 IDEAL PARALLEL COMPUT

7、ATION3.1 IDEAL PARALLEL COMPUTATIONPractical embarrassingly parallel computation with static Practical embarrassingly parallel computation with static process creation and master-slave approachprocess creation and master-slave approach63.1 IDEAL PARALLEL COMPUTATION3.1 IDEAL PARALLEL COMPUTATIONPrac

8、tical embarrassingly parallel computation with Practical embarrassingly parallel computation with dynamic process creation and master-slave approachdynamic process creation and master-slave approach73.2 EMBARRASSINGLY PARALLEL EXAMPLES3.2 EMBARRASSINGLY PARALLEL EXAMPLES1 1、Geometrical Transformatio

9、n of Images Geometrical Transformation of Images 图形的几何变图形的几何变 换换2 2、Mandelbrot Set Mandelbrot Set 曼德勃罗特集曼德勃罗特集3 3、Monte Carlo Methods Monte Carlo Methods 蒙特卡罗法蒙特卡罗法83.2.1 Geometrical Transformation of Images Many low level image processing operationsMany low level image processing operationsonly inv

10、olve local data with very limited if only involve local data with very limited if any communication between areas of interestany communication between areas of interest.93.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Images103.2.1 Geometrical Transformation of Images3.

11、2.1 Geometrical Transformation of Images113.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Images123.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Images并行程序并行程序 易并行计算易并行计算 主从结构，一个主进程，主从结构，一个主进程，4848个从进程。个从进程。 主进程向每个从进程发送需处理的主进程向每个从进程发送需处理的1

12、010行的首行号，并接收每个从进程的处理结行的首行号，并接收每个从进程的处理结果以供显示。果以供显示。 每个从进程处理每个从进程处理1010* *640640的区域。的区域。133.2.1 Geometrical Transformation of Image3.2.1 Geometrical Transformation of ImageMaster:Master:/ /* *send row No. to each slave-processsend row No. to each slave-process* */ /for(i=1,row=0;i=48;i+,row=row+10) f

13、or(i=1,row=0;i=48;i+,row=row+10) send(&row, Pi);send(&row, Pi);for(i=0;i480;i+)for(i=0;i480;i+) for(j=0;j640;j+) for(j=0;j640;j+) / /* *initialize temp initialize temp * */ / temp_mapij=0; temp_mapij=0;143.2.1 Geometrical Transformation of Image3.2.1 Geometrical Transformation of Imagefor(i=

14、0;i(640for(i=0;i0&newrow0&newrow0&newcol0&newcol641)temp_mapnewrownewcol=mapoldrowoldcoltemp_mapnewrownewcol=mapoldrowoldcol 153.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Imagesfor(i=0;i480;i+)for(i=0;i480;i+) for(j=0;j640;j+) for(j=0;j640;j+) / /* *

15、update bitmap update bitmap * */ / mapij=temp_mapij; mapij=temp_mapij;Slave:Slave: recv(row,Pmaster); recv(row,Pmaster); / /* * recv row no. recv row no.* */ /163.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Imagesfor(oldrow=row;oldrow(row+10);oldrow+)for(oldrow=row;ol

16、drow(row+10);oldrow+) for(oldcol=0;oldcol640;oldcol+) for(oldcol=0;oldcol640;oldcol+) / /* *transform coordstransform coords* */ / newrow=oldrow+delta_x; newrow=oldrow+delta_x; / /* *shift in X directionshift in X direction* */ / newcol=oldcol +delta_y; newcol=oldcol +delta_y; / /* *shift in Y direc

17、tionshift in Y direction* */ / send(oldrow,oldcol,newrow,newcol,Pmaster); send(oldrow,oldcol,newrow,newcol,Pmaster); 173.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Images 顺序时间复杂性为顺序时间复杂性为O(nO(n2 2) ) 并行时间复杂性：并行时间复杂性： t tcommcomm=p p( (t tstartstart+ +t tdatadata)+4 n

18、)+4 n2 2 ( (t tstartstart+ +t tdatadata) ) =O(p+n =O(p+n2 2) ) t tcomp=2(comp=2(n n2 2/p/p )= )=OO( (n n2 2/p/p ) ) t tp= p= t tcomm+ comm+ t tcompcomp 对于常数对于常数p p，时间复杂性为，时间复杂性为O(nO(n2 2) )183.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Images 性能差原因：传送的数据量大性能差原因：传送的数据

19、量大 改进：尽量减少数据传送，减小启动时间改进：尽量减少数据传送，减小启动时间 每个进程可自己确定起始行号每个进程可自己确定起始行号 从进程每次返回一组结果而不是一个结果。从进程每次返回一组结果而不是一个结果。 最适合于共享存储器多处理机最适合于共享存储器多处理机 考虑通用性，以下可变：考虑通用性，以下可变： 显示区域大小显示区域大小 每个进程处理的行数每个进程处理的行数 进程数进程数193.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集203.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集

20、曼德勃罗特集213.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集Sequential Code:Sequential Code:structure complex float real ;float imag;structure complex float real ;float imag;int cal_pixel(complex c)int cal_pixel(complex c) int count=0,max=256; int count=0,max=256; / /* *countcount为迭代次数，为迭代次数，maxma

21、x为最大迭带次数为最大迭带次数* */ / float temp,lengthsq; float temp,lengthsq; complex z; complex z; z.real=0.0; z.real=0.0; z.imag=0.0; z.imag=0.0;223.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集 do do temp= z.real temp= z.real* * z.real- z.imag z.real- z.imag* * z.imag+c.real; z.imag+c.real; z.imag=2 z.i

22、mag=2* * z.real z.real* * z.imag+ c.imag z.imag+ c.imag z.real=temp; z.real=temp; lengthsq= z.real lengthsq= z.real* * z.real+ z.imag z.real+ z.imag* * z.imag; z.imag; count+; count+; while(length4.0)&(countmax); while(length4.0)&(countmax); return count; return count; 233.2.2 Mandelbrot Set

23、 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集#define disp_height 800 #define disp_height 800 #define disp_width 800 #define disp_width 800 #define real_min -2#define real_min -2#define imag_min -2#define imag_min -2#define real_max 2#define real_max 2#define imag_max 2#define imag_max 2243.2.2 Mandelbrot Set 3

24、.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集void display(int x,int y,int color)void display(int x,int y,int color)main()main() int x, y, color, scale_real, scale_imag; int x, y, color, scale_real, scale_imag; complex c; complex c; scale_real=(real_max-real_min)/disp_width; scale_real=(real_max-real_min)/disp_wi

25、dth; scale_imag=(imag_max-imag_min)/disp_height; scale_imag=(imag_max-imag_min)/disp_height;253.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集for(x=0; xdisp_width; x+)for(x=0; xdisp_width; x+) for(y=0;ydisp_height; y+) for(y=0;ydisp_height; y+) c.real=real_min+(float)x c.real=real_min+(float)x

26、* * scale_real); scale_real); c.imag=imag_min+(float)y c.imag=imag_min+(float)y* * scale_imag); scale_imag); color=cal_pixel(c); color=cal_pixel(c); display(c.real,c.imag,color); display(c.real,c.imag,color); 263.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集It is clear that the iterating of o

27、ne point isntIt is clear that the iterating of one point isntdependent on that of other points. So it isdependent on that of other points. So it isconvenient to parallel.convenient to parallel. There are two ways to assign a fixed area of There are two ways to assign a fixed area of image to each pr

28、ocess:image to each process: static task assignmentstatic task assignment dynamic task assignment dynamic task assignment273.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集283.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集static task assignment:static task assignment:MasterMasterfor(i=0,r

29、ow=0;i48;i+,row=row+10) for(i=0,row=0;i48;i+,row=row+10) send(&row, Pi); send(&row, Pi);for(i =0;i(640for(i =0;i(640* *480); i+)480); i+) recv(&c,&color,Pany); recv(&c,&color,Pany); display(c,color); display(c,color); 293.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集Sl

30、aveSlaverecv(&row, Pmaster);recv(&row, Pmaster);for(x=0; xdisp_width; x+)for(x=0; xdisp_width; x+) for(y=row;y(row+10); y+) for(y=row;y(row+10); y+) c.real= real_min+(float)x c.real= real_min+(float)x* * scale_real); scale_real); c.imag= imag_min+(float)y c.imag= imag_min+(float)y* * scale_i

31、mag); scale_imag); color=cal_pixel(c); color=cal_pixel(c); send(&c,&color,Pmaster); send(&c,&color,Pmaster); 303.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集 问题：问题： 从进程每次只发回一个结果。可从进程每次只发回一个结果。可 成组发送。成组发送。 负载不均衡负载不均衡313.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集323.2

32、.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集Dynamic task assignmentDynamic task assignmentwork pool/processor farmswork pool/processor farmsmaster:master:count=0,row=0;count=0,row=0;for(k=0;kproc; k+)for(k=0;kproc; k+) send(&row, P send(&row, Pk k, data_tag);, data_tag); count+; row+;

33、 count+; row+; 33dodo recv(&slave, &c, color, P recv(&slave, &c, color, Panyany, result_tag);, result_tag); count-; count-; / /* *每收到一行，每收到一行，countcount减一减一* */ / if(rowdisp_height) if(row0); while(count0);34slave:slave:recv(y, Pmaster, ANYTAG, source_tag);recv(y, Pmaster, ANYTAG, so

34、urce_tag);while(source_tag=data_tag)while(source_tag=data_tag) c.imag= imag_min+(float)y c.imag= imag_min+(float)y* * scale_imag); scale_imag); for(x=0; xdisp_width; x+) for(x=0; xdisp_width; x+) c.real= real_min+(float)x c.real= real_min+(float)x* * scale_real); scale_real); colorx=cal_pixel(c); co

35、lorx=cal_pixel(c); send(&c, color,Pmaster,result_tag); send(&c, color,Pmaster,result_tag); recv(y, Pmaster, anytag, source_tag); recv(y, Pmaster, anytag, source_tag); 353.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集 顺序时间复杂性为：顺序时间复杂性为： t t s s max max n n 并行时间复杂性：并行时间复杂性：1. 1. t tcomm

36、1=comm1=s s( (t tstartup+ startup+ t tdata)data)2.2. T Tcomp comp (max (max n) / s n) / s3. 3. t tcomm2=comm2=(n/s)(n/s)( (t tstartup+ startup+ t tdata)data)t t p p (max (max n) / s+(n/s+s)( n) / s+(n/s+s)(t tstart+ start+ t tdatadata) )363.2.2 Mandelbrot Set 3.2.2 Mandelbrot Set 曼德勃罗特集曼德勃罗特集373.2.3

37、 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法 这是一种基于概率（随机选择）的解决问这是一种基于概率（随机选择）的解决问题的方法，典型应用场合有：计算圆周率，题的方法，典型应用场合有：计算圆周率，计算积分等。计算积分等。 Monte Carlo methods use of random selections.Monte Carlo methods use of random selections.383.2.3 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法3

38、93.2.3 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法403.2.3 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法413.2.3 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法423.2.3 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法并行代码：并行代码：Master:Master:for(i=0;iN/n; i+)for(

39、i=0;iN/n; i+) for(j=0;jn; j+) xrj=rand ( ); for(j=0;jn; j+) xrj=rand ( ); / /* *n=no of random n=no of random * */ / recv (Pany, req_tag, Psource); recv (Pany, req_tag, Psource); / /* * numbers for slave numbers for slave* */ / send(xr, &n, Psource, compute_tag); send(xr, &n, Psource, comput

40、e_tag); for(i=0;islave _ no; i+)for(i=0;islave _ no; i+) recv(Pi, req_tag); recv(Pi, req_tag); send(Pi, stop_tag); send(Pi, stop_tag); sum=0;sum=0;reduce_add(&sum, Pgroup);reduce_add(&sum, Pgroup);433.2.3 Monte Carlo Methods 3.2.3 Monte Carlo Methods 蒙特卡罗法蒙特卡罗法Slave:Slave:sum=0;sum=0;send (P

41、master, req_tag);send (Pmaster, req_tag);recv (xr, &n, Pmaster, source_tag);recv (xr, &n, Pmaster, source_tag);while(source_tag=compute_tag)while(source_tag=compute_tag) for( i=0;in; i+) sum+= xri for( i=0;in; i+) sum+= xri* *(xri-3);(xri-3); send (Pmaster, req_tag); send (Pmaster, req_tag);

42、 recv (xr, &n, Pmaster, source_tag); recv (xr, &n, Pmaster, source_tag); ;reduce_add(&sum, Pgroup);reduce_add(&sum, Pgroup);44SUMMARYSUMMARY An (ideal) embarrassingly parallel computationAn (ideal) embarrassingly parallel computation 理想的易并行计算理想的易并行计算 Embarrassingly parallel problems

43、and analysesEmbarrassingly parallel problems and analyses 可完全并行计算的问题及其分析可完全并行计算的问题及其分析 Partitioning a two-dimensional data setPartitioning a two-dimensional data set 二维数据集的划分二维数据集的划分 Work pool approach to achieve load balancingWork pool approach to achieve load balancing 面向负载平衡的工作池方法面向负载平衡的工作池方法 Mon

44、te Carlo methodsMonte Carlo methods 蒙特卡罗方法蒙特卡罗方法45并行算法分类并行算法分类 根据运算的基本对象根据运算的基本对象 根据进程之间的依赖关系根据进程之间的依赖关系 根据并行计算任务的大小根据并行计算任务的大小46并行算法分类并行算法分类 根据运算的基本对象根据运算的基本对象 数值并行算法数值计算数值并行算法数值计算 如矩阵运算、多项式求值、线性代数方程组求解等。求解数值如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法（计算问题的算法称为数值算法（Numerical AlgorithmNumerical Algorit

45、hm）。）。 科学科学与工程中的计算问题如计算力学、计算物理、计算化学等一般与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。是数值计算问题。 非数值并行算法非数值并行算法（符号计算、基于比较关系运算）（符号计算、基于比较关系运算） 诸如排序、选择、搜索、匹配等符号处理，相应的算法诸如排序、选择、搜索、匹配等符号处理，相应的算法 也称为非数值算法（也称为非数值算法（Non-numerical AlgorithmNon-numerical Algorithm）。）。 非数值计算在符号类信息处理中获得广泛应用，如数据非数值计算在符号类信息处理中获得广泛应用，如数据 库领域的计算

46、问题、海量数据挖掘等，库领域的计算问题、海量数据挖掘等， 近年来广泛关注的生物信息学主要也是非数值计算近年来广泛关注的生物信息学主要也是非数值计算 47并行算法分类并行算法分类 根据进程之间的依赖关系根据进程之间的依赖关系 同步并行算法同步并行算法（步调一致）（步调一致） 任务的各个部分是同步向前推进的，有一个全任务的各个部分是同步向前推进的，有一个全 局的时钟局的时钟（不一定是物理的）来控制各部分的步伐（不一定是物理的）来控制各部分的步伐 异步并行算法异步并行算法（步调、进展互不相同）（步调、进展互不相同） 各部分的步伐是互不相同的，它们根据计算过程的不同各部分的步伐是互不相同的，它们根据计

47、算过程的不同 阶段决定等待、继续或终止阶段决定等待、继续或终止 纯并行算法纯并行算法（各部分之间没有关系）（各部分之间没有关系） 最理想的情况，各部分之间可以尽可能快地向前进，不需最理想的情况，各部分之间可以尽可能快地向前进，不需 要任何同步或等待，但是一般这样的问题是少见的要任何同步或等待，但是一般这样的问题是少见的48并行算法分类并行算法分类 根据并行计算任务的大小根据并行计算任务的大小 粗粒度并行算法粗粒度并行算法 一个并行任务包含较长的程序段和较大的计一个并行任务包含较长的程序段和较大的计算量算量 细粒度并行算法细粒度并行算法 一个并行任务包含较短的程序段和较小的计一个并行任务包含较短的程序段和较小的计算量。提高并行度，但通信次数和通信量算量。提高并行度，但通信次数和通信量就相对增多，增加了额外的开销。就相对增多，增加了额外的开销。 中粒度并行算法中粒度并行算法49并行算法的设计并行算法的设计并行算法设计的不同可能对程序的执行效并行算法设计的不同可能对程序的执行效率有很大的影响，不同的算法可以有几倍几率有很大的影响，不同的算法可以有几倍几十倍甚至上百倍的性能差异。十倍甚至上百倍的性能差异。对于机群计算：对于机群计算： 增加计算增加计算/ /通信比通信比 并行粒度不可能太小，因为这样会大大增加并行粒度不可能太小，因为这样会大大