典型問題實(shí)例分析

1、3 典型問題并行實(shí)例分析n什么樣的問題適合并行計算？n斐波那契序列(Fibonacci)的計算？n什么樣的問題適合并行計算？n如果有大量結(jié)構(gòu)一致的數(shù)據(jù)要處理，且數(shù)據(jù)可以分解成相同大小的部分， 那我們就可以設(shè)法使這道處理變成并行主要內(nèi)容 3.1 易并行計算問題(分形圖形并行生成) 3.2 數(shù)值計算(矩陣運(yùn)算) 3.3 數(shù)排序問題 (流水線) 3.1 易并行計算問題 一個理想的并行計算是能被立即分解成許多完全獨(dú)立部分且它們被同時執(zhí)行的計算，這種情況被稱為易并行。真正意義上的易并行計算意味著在各個進(jìn)程間沒有通信。 近似易并行計算是那種需將計算結(jié)果分布和收集，以及用某種方式加以組合的計算。這就意味著在

2、開始和最后只有一個進(jìn)程處于運(yùn)行狀態(tài)。如果要創(chuàng)建動態(tài)進(jìn)程，通常的方法是采用主從結(jié)構(gòu)。首先創(chuàng)建一個主進(jìn)程，由它啟動相同的從進(jìn)程。分布式圖像處理 解決復(fù)雜圖形應(yīng)用問題的行之有效的方法是把復(fù)雜問題劃分為可以并發(fā)執(zhí)行的若干子任務(wù)，使它們并行執(zhí)行。從而在聯(lián)網(wǎng)的計算機(jī)系統(tǒng)中實(shí)現(xiàn)并行機(jī)才能夠解決的問題。 存儲一個二維圖像的最基本方法是使用像素圖，即位圖。 圖像處理輸入數(shù)據(jù)是位圖/像素圖。通常存于文件中并被復(fù)制到數(shù)組中。并行編程主要關(guān)心將位圖/像素圖分成一些像素組以供每個處理器加工。實(shí)例1：分形圖形的并行處理分形圖形原理 Julia 集是由法國數(shù)學(xué)家 Gaston Julia 和 Pierre Faton 在發(fā)

3、展了復(fù)變函數(shù)迭代的基礎(chǔ)理論后獲得的。 Julia 集是一個典型的分形。由一個復(fù)變函數(shù)生成， 其中c為常數(shù)。由于c可以是任意值，所以當(dāng)c取不同的值時，制出的圖形也不相同。 u等于0時，兩個吸引區(qū)域中間的邊界即 Julia 集。當(dāng)u u0 0，即控制參數(shù)變化時，JuliaJulia集構(gòu)成各種各樣的分維結(jié)構(gòu)C0時兩個吸引區(qū)域之間的分形邊界 在控制參數(shù)u0時：分形出現(xiàn)了。U=-1 情況下的Julia集c = 0 . 1 + i 0 . 8 情況下的Julia集c = 0 . 3 i 0 . 4 情況下的Julia集 對于復(fù)映射zn+1zn2+u,我們也可以在復(fù)參數(shù)平面(p,q)上討論，這種情況下不是取

4、定u，而是取定z0。定義:能夠使上述|Zn|有界的點(diǎn)集(p,q)即為Mandelbrot集。若Z0=0 得到軌道0,u,u2+u, (u2+u)2+u, .n只要上述軌道上任何一點(diǎn)復(fù)數(shù)模大于2，則|Zn|趨向無窮。于是，該點(diǎn)集(p,q)就不屬于Mandelbrot集。若Z0=0 得到軌道0,u,u2+u, (u2+u)2+u, . Zk+1Zku 對于復(fù)平面上的復(fù)數(shù)a+bi，Z的初值為0， Zk+1是復(fù)數(shù)za+bi的第k+1次迭代， Zk是z的第k次迭代，u是確定該點(diǎn)在復(fù)數(shù)平面中位置的復(fù)數(shù)值，迭代一直進(jìn)行下去，直到|Zn|4或達(dá)到了一定的迭代次數(shù)。 若結(jié)果集合在64*64個像素區(qū)域內(nèi)顯示，則復(fù)

5、平面上需要計算64*64個像素點(diǎn)，根據(jù)每個像素點(diǎn)在復(fù)平面上的位置進(jìn)行迭代。記錄每個像素點(diǎn)的迭代次數(shù)值，將該值作為該像素點(diǎn)的顏色值進(jìn)行顯示。如256色，則對應(yīng)到256種顏色中其中的一個顏色進(jìn)行顯示。分形圖形并行處理的實(shí)現(xiàn)系統(tǒng)利用PVM的消息傳遞機(jī)制，采用Master/Slave模式來完成進(jìn)程之間的異步通信。主進(jìn)程(Master)負(fù)責(zé)進(jìn)程的生成，初始化，收集并顯示計算結(jié)果。從進(jìn)程(Slave)執(zhí)行實(shí)際的計算，其負(fù)載是由主進(jìn)程動態(tài)分配，不受節(jié)點(diǎn)機(jī)性能不同或變化的影響。 一個PVM虛擬機(jī)的結(jié)構(gòu)示意圖 PVM虛擬機(jī)主節(jié)點(diǎn)從節(jié)點(diǎn)1從節(jié)點(diǎn)2主PVMD任務(wù)1任務(wù)2從PVMD1任務(wù)3任務(wù)4從PVMD2任務(wù)5任務(wù)

6、6發(fā)送方接收方消息發(fā)送數(shù)據(jù)發(fā)送緩沖區(qū)打包數(shù)據(jù)接收緩沖區(qū)解包PVM進(jìn)程間發(fā)送/接收數(shù)據(jù)過程主進(jìn)程程序流程圖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);從進(jìn)程數(shù)據(jù)流向圖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循環(huán)左移至同行相鄰處理器中 */Leftmoveonestep(a)end if if(jk) then /* b循環(huán)上移至同列相鄰處理器中 */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循環(huán)左移至同行相鄰的處理器中 */Upmoveonestep(b)/* 子塊b循環(huán)上移至同列相鄰的處理器中 */end forEnd函數(shù)Leftmoveonestep（a）為例，給出處理器間交換數(shù)據(jù)的過程，如算法4： 算法4：函數(shù)Leftmoveonestep（a）的基本算法Begin(1) if (j = 0) then /* 最左端的子塊 */(1.1) 將所存的A的子塊發(fā)送

9、到同行最右端子塊所在的處理器中(1.2) 接收其右鄰處理器中發(fā)來的A的子塊end if(2) if(j = -1) and (j mod 2 = 0) then /* 最右端子塊處理器且塊列號為偶數(shù) */(2.1) 將所存的A的子塊發(fā)送到其左鄰處理器中(2.2) 接收其同行最左端子塊所在的處理器發(fā)送來的A的子塊end if(3) if (j = -1) and (j mod 2 0) then /* 最右端子塊處理器且塊列號為奇數(shù) */(3.1)將所存的A的子塊在緩沖區(qū)buffer中作備份(3.2)接收其同行最左端子塊所在的處理器發(fā)送來的A的子塊(3.3)將在緩沖區(qū)buffer中所存的A的子塊

10、發(fā)送到其左鄰處理器中 end if(4) if(j -1) and (j mod 2 = 0) and (j 0) then /* 其余的偶數(shù)號處理器 */(4.1) 將所存的A的子塊發(fā)送到其左鄰處理器中(4.2) 接收其右鄰處理器中發(fā)來的A的子塊end if (5) if(j -1) and (j mod 2 = 1) and (j 0) then /* 其余的奇數(shù)號處理器 */(5.1) 將所存的A的子塊在緩沖區(qū)buffer中作備份(5.2) 接收其右鄰處理器中發(fā)送來的A的子塊(5.3) 將在緩沖區(qū)buffer中所存的A的子塊發(fā)送到其左鄰處理器中 end if End分成四個子任務(wù)的情況：

11、3.3 數(shù)的排序(流水線技術(shù)應(yīng)用實(shí)例) 在流水線技術(shù)中，問題被分成一些列必須一個接一個完成的任務(wù)。每個任務(wù)由分離的過程或處理器執(zhí)行，如圖所示。一個流水線過程成為一個流水線級。每一級只解決問題的一部分并且把相關(guān)的信息傳送給需要它的下一級。這種并行性可以看成是功能分解的一種形式。問題被劃分為必須執(zhí)行的獨(dú)立的功能，而且在這種情況下這些功能必須被連續(xù)執(zhí)行。 流水線技術(shù)描述 一個簡單的循環(huán)： for (i = 0; i x) send(&x, Pi+1); x = number; else send(&number, Pi+1);數(shù)的排序問題描述(3) 對于n個數(shù)，第i個進(jìn)程要接收n-i個數(shù)，它要上傳n-i-1個數(shù)，因此可以使用一個簡單的循環(huán)： right_procno=n-i-1 recv(&