并行程序設(shè)計(jì)Chapter3

1、1第3章 易并行計(jì)算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并行程序并行程序 易并行計(jì)算易并行計(jì)算 主從結(jié)構(gòu)，一個(gè)主進(jìn)程，主從結(jié)構(gòu)，一個(gè)主進(jìn)程，4848個(gè)從進(jìn)程。個(gè)從進(jìn)程。 主進(jìn)程向每個(gè)從進(jìn)程發(fā)送需處理的主進(jìn)程向每個(gè)從進(jìn)程發(fā)送需處理的1

12、010行的首行號(hào)，并接收每個(gè)從進(jìn)程的處理結(jié)行的首行號(hào)，并接收每個(gè)從進(jìn)程的處理結(jié)果以供顯示。果以供顯示。 每個(gè)從進(jìn)程處理每個(gè)從進(jìn)程處理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 順序時(shí)間復(fù)雜性為順序時(shí)間復(fù)雜性為O(nO(n2 2) ) 并行時(shí)間復(fù)雜性：并行時(shí)間復(fù)雜性： 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 對(duì)于常數(shù)對(duì)于常數(shù)p p，時(shí)間復(fù)雜性為，時(shí)間復(fù)雜性為O(nO(n2 2) )183.2.1 Geometrical Transformation of Images3.2.1 Geometrical Transformation of Images 性能差原因：傳送的數(shù)據(jù)量大性能差原因：傳送的數(shù)據(jù)

19、量大 改進(jìn)：盡量減少數(shù)據(jù)傳送，減小啟動(dòng)時(shí)間改進(jìn)：盡量減少數(shù)據(jù)傳送，減小啟動(dòng)時(shí)間 每個(gè)進(jìn)程可自己確定起始行號(hào)每個(gè)進(jìn)程可自己確定起始行號(hào) 從進(jìn)程每次返回一組結(jié)果而不是一個(gè)結(jié)果。從進(jìn)程每次返回一組結(jié)果而不是一個(gè)結(jié)果。 最適合于共享存儲(chǔ)器多處理機(jī)最適合于共享存儲(chǔ)器多處理機(jī) 考慮通用性，以下可變：考慮通用性，以下可變： 顯示區(qū)域大小顯示區(qū)域大小 每個(gè)進(jìn)程處理的行數(shù)每個(gè)進(jìn)程處理的行數(shù) 進(jìn)程數(shù)進(jìn)程數(shù)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為迭代次數(shù)，為迭代次數(shù)，maxma

21、x為最大迭帶次數(shù)為最大迭帶次數(shù)* */ / 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 曼德勃羅特集曼德勃羅特集 問題：問題： 從進(jìn)程每次只發(fā)回一個(gè)結(jié)果。可從進(jìn)程每次只發(fā)回一個(gè)結(jié)果。可 成組發(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 曼德勃羅特集曼德勃羅特集 順序時(shí)間復(fù)雜性為：順序時(shí)間復(fù)雜性為： t t s s max max n n 并行時(shí)間復(fù)雜性：并行時(shí)間復(fù)雜性：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 蒙特卡羅法蒙特卡羅法 這是一種基于概率（隨機(jī)選擇）的解決問這是一種基于概率（隨機(jī)選擇）的解決問題的方法，典型應(yīng)用場合有：計(jì)算圓周率，題的方法，典型應(yīng)用場合有：計(jì)算圓周率，計(jì)算積分等。計(jì)算積分等。 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 理想的易并行計(jì)算理想的易并行計(jì)算 Embarrassingly parallel problems

43、and analysesEmbarrassingly parallel problems and analyses 可完全并行計(jì)算的問題及其分析可完全并行計(jì)算的問題及其分析 Partitioning a two-dimensional data setPartitioning a two-dimensional data set 二維數(shù)據(jù)集的劃分二維數(shù)據(jù)集的劃分 Work pool approach to achieve load balancingWork pool approach to achieve load balancing 面向負(fù)載平衡的工作池方法面向負(fù)載平衡的工作池方法 Mon

44、te Carlo methodsMonte Carlo methods 蒙特卡羅方法蒙特卡羅方法45并行算法分類并行算法分類 根據(jù)運(yùn)算的基本對(duì)象根據(jù)運(yùn)算的基本對(duì)象 根據(jù)進(jìn)程之間的依賴關(guān)系根據(jù)進(jìn)程之間的依賴關(guān)系 根據(jù)并行計(jì)算任務(wù)的大小根據(jù)并行計(jì)算任務(wù)的大小46并行算法分類并行算法分類 根據(jù)運(yùn)算的基本對(duì)象根據(jù)運(yùn)算的基本對(duì)象 數(shù)值并行算法數(shù)值計(jì)算數(shù)值并行算法數(shù)值計(jì)算 如矩陣運(yùn)算、多項(xiàng)式求值、線性代數(shù)方程組求解等。求解數(shù)值如矩陣運(yùn)算、多項(xiàng)式求值、線性代數(shù)方程組求解等。求解數(shù)值計(jì)算問題的算法稱為數(shù)值算法（計(jì)算問題的算法稱為數(shù)值算法（Numerical AlgorithmNumerical Algorit

45、hm）。）。 科學(xué)科學(xué)與工程中的計(jì)算問題如計(jì)算力學(xué)、計(jì)算物理、計(jì)算化學(xué)等一般與工程中的計(jì)算問題如計(jì)算力學(xué)、計(jì)算物理、計(jì)算化學(xué)等一般是數(shù)值計(jì)算問題。是數(shù)值計(jì)算問題。 非數(shù)值并行算法非數(shù)值并行算法（符號(hào)計(jì)算、基于比較關(guān)系運(yùn)算）（符號(hào)計(jì)算、基于比較關(guān)系運(yùn)算） 諸如排序、選擇、搜索、匹配等符號(hào)處理，相應(yīng)的算法諸如排序、選擇、搜索、匹配等符號(hào)處理，相應(yīng)的算法 也稱為非數(shù)值算法（也稱為非數(shù)值算法（Non-numerical AlgorithmNon-numerical Algorithm）。）。 非數(shù)值計(jì)算在符號(hào)類信息處理中獲得廣泛應(yīng)用，如數(shù)據(jù)非數(shù)值計(jì)算在符號(hào)類信息處理中獲得廣泛應(yīng)用，如數(shù)據(jù) 庫領(lǐng)域的計(jì)算

46、問題、海量數(shù)據(jù)挖掘等，庫領(lǐng)域的計(jì)算問題、海量數(shù)據(jù)挖掘等， 近年來廣泛關(guān)注的生物信息學(xué)主要也是非數(shù)值計(jì)算近年來廣泛關(guān)注的生物信息學(xué)主要也是非數(shù)值計(jì)算 47并行算法分類并行算法分類 根據(jù)進(jìn)程之間的依賴關(guān)系根據(jù)進(jìn)程之間的依賴關(guān)系 同步并行算法同步并行算法（步調(diào)一致）（步調(diào)一致） 任務(wù)的各個(gè)部分是同步向前推進(jìn)的，有一個(gè)全任務(wù)的各個(gè)部分是同步向前推進(jìn)的，有一個(gè)全 局的時(shí)鐘局的時(shí)鐘（不一定是物理的）來控制各部分的步伐（不一定是物理的）來控制各部分的步伐 異步并行算法異步并行算法（步調(diào)、進(jìn)展互不相同）（步調(diào)、進(jìn)展互不相同） 各部分的步伐是互不相同的，它們根據(jù)計(jì)算過程的不同各部分的步伐是互不相同的，它們根據(jù)計(jì)

47、算過程的不同 階段決定等待、繼續(xù)或終止階段決定等待、繼續(xù)或終止 純并行算法純并行算法（各部分之間沒有關(guān)系）（各部分之間沒有關(guān)系） 最理想的情況，各部分之間可以盡可能快地向前進(jìn)，不需最理想的情況，各部分之間可以盡可能快地向前進(jìn)，不需 要任何同步或等待，但是一般這樣的問題是少見的要任何同步或等待，但是一般這樣的問題是少見的48并行算法分類并行算法分類 根據(jù)并行計(jì)算任務(wù)的大小根據(jù)并行計(jì)算任務(wù)的大小 粗粒度并行算法粗粒度并行算法 一個(gè)并行任務(wù)包含較長的程序段和較大的計(jì)一個(gè)并行任務(wù)包含較長的程序段和較大的計(jì)算量算量 細(xì)粒度并行算法細(xì)粒度并行算法 一個(gè)并行任務(wù)包含較短的程序段和較小的計(jì)一個(gè)并行任務(wù)包含較短的程序段和較小的計(jì)算量。提高并行度，但通信次數(shù)和通信量算量。提高并行度，但通信次數(shù)和通信量就相對(duì)增多，增加了額外的開銷。就相對(duì)增多，增加了額外的開銷。 中粒度并行算法中粒度并行算法49并行算法的設(shè)計(jì)并行算法的設(shè)計(jì)并行算法設(shè)計(jì)的不同可能對(duì)程序的執(zhí)行效并行算法設(shè)計(jì)的不同可能對(duì)程序的執(zhí)行效率有很大的影響，不同的算法可以有幾倍幾率有很大的影響，不同的算法可以有幾倍幾十倍甚至上百倍的性能差異。十倍甚至上百倍的性能差異。對(duì)于機(jī)群計(jì)算：對(duì)于機(jī)群計(jì)算： 增加計(jì)算增加計(jì)算/ /通信比通信比 并行粒度不可能太小，因?yàn)檫@樣會(huì)大大增加并行粒度不可能太小，因?yàn)檫@樣會(huì)大大