并行程序設計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個從進程。個從進程。 主進程向每個從進程發(fā)送需處理的主進程向每個從進程發(fā)送需處理的1

12、010行的首行號，并接收每個從進程的處理結行的首行號，并接收每個從進程的處理結果以供顯示。果以供顯示。 每個從進程處理每個從進程處理1010* *640640的區(qū)域。的區(qū)域。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、量大 改進：盡量減少數據傳送，減小啟動時間改進：盡量減少數據傳送，減小啟動時間 每個進程可自己確定起始行號每個進程可自己確定起始行號 從進程每次返回一組結果而不是一個結果。從進程每次返回一組結果而不是一個結果。 最適合于共享存儲器多處理機最適合于共享存儲器多處理機 考慮通用性，以下可變：考慮通用性，以下可變： 顯示區(qū)域大小顯示區(qū)域大小 每個進程處理的行數每個進程處理的行數 進程數進程數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 曼德勃羅特集曼德勃羅特集 問題：問題： 從進程每次只發(fā)回一個結果。可從進程每次只發(fā)回一個結果。可 成組發(fā)送。成組發(fā)送。 負載不均衡負載不均衡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、算過程的不同 階段決定等待、繼續(xù)或終止階段決定等待、繼續(xù)或終止 純并行算法純并行算法（各部分之間沒有關系）（各部分之間沒有關系） 最理想的情況，各部分之間可以盡可能快地向前進，不需最理想的情況，各部分之間可以盡可能快地向前進，不需 要任何同步或等待，但是一般這樣的問題是少見的要任何同步或等待，但是一般這樣的問題是少見的48并行算法分類并行算法分類 根據并行計算任務的大小根據并行計算任務的大小 粗粒度并行算法粗粒度并行算法 一個并行任務包含較長的程序段和較大的計一個并行任務包含較長的程序段和較大的計算量算量 細粒度并行算法細粒度并行算法 一個并行任務包含較短的程序段和較小的計一個并行任務包含較短的程序段和較小的計算量。提高并行度，但通信次數和通信量算量。提高并行度，但通信次數和通信量就相對增多，增加了額外的開銷。就相對增多，增加了額外的開銷。 中粒度并行算法中粒度并行算法49并行算法的設計并行算法的設計并行算法設計的不同可能對程序的執(zhí)行效并行算法設計的不同可能對程序的執(zhí)行效率有很大的影響，不同的算法可以有幾倍幾率有很大的影響，不同的算法可以有幾倍幾十倍甚至上百倍的性能差異。十倍甚至上百倍的性能差異。對于機群計算：對于機群計算： 增加計算增加計算/ /通信比通信比 并行粒度不可能太小，因為這樣會大大增加并行粒度不可能太小，因為這樣會大大