1、常用算法與程序設(shè)計(jì),1,第 9 章,并行算法,常用算法與程序設(shè)計(jì),2,主要內(nèi)容,9.1 并行算法的基本概念 并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)模型 并行計(jì)算性能評(píng)價(jià) 9.2 并行算法設(shè)計(jì) SIMD共享存儲(chǔ)模型 SIMD互連網(wǎng)絡(luò)模型 MIMD共享存儲(chǔ)模型 MIMD異步通信模型 9.3 并行程序開發(fā) 并行程序設(shè)計(jì)的概念 共享存儲(chǔ)系統(tǒng)并行編程 分布存儲(chǔ)系統(tǒng)并行編程,常用算法與程序設(shè)計(jì),3,9.1并行算法的基本概念,9.1.1 并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)模型 SISD:單指令流單數(shù)據(jù)流。 SIMD:單指令流多數(shù)據(jù)流。 MISD:多指令流單數(shù)據(jù)流。 MIMD:多指令流多數(shù)據(jù)流。,常用算法與程序設(shè)計(jì),4,9.1.2 并行計(jì)算性能

2、評(píng)價(jià),1. 并行算法的成本C（n） 成本C（n）定義為并行算法的運(yùn)行時(shí)間T（n）與其所需的處理器數(shù)P（n）的乘積，即 C（n）T（n）* P（n） 它相當(dāng)于在最壞的情況下求解某一問題的總執(zhí)行步數(shù)。如果求解一個(gè)問題的并行算法的成本，在數(shù)量級(jí)上等于最壞情況下的串行求解此問題所需的執(zhí)行步數(shù)，那么稱此并行算法是成本最優(yōu)的。 。,常用算法與程序設(shè)計(jì),5,2. 加速比Sp（n） 并行算法的加速比Sp（n）可定義為 Sp（n）Ts（n）/ Tp（n） 式中，Ts（n）是最快的串行算法在最壞的情況下的運(yùn)行時(shí)間，Tp（n）是求解同一問題的某并行算法在最壞情況下的運(yùn)行時(shí)間 。 Sp（n）越大，則并行算法越好。,常

3、用算法與程序設(shè)計(jì),6,3. 并行算法的效率Ep（n） 并行算法的效率可定義為算法的加速比與處理器數(shù)目之比，即 Ep（n）Sp（n）/P(n) 并行算法的加速比不能反應(yīng)處理機(jī)的利用率，一個(gè)并行算法的加速比可能很大，但是處理機(jī)的利用率卻可能很低。并行算法的效率反映了在執(zhí)行算法時(shí)處理機(jī)的利用情況。,常用算法與程序設(shè)計(jì),7,并行程序設(shè)計(jì)包括將一個(gè)問題分解成若干部分，然后由各個(gè)處理器對(duì)各個(gè)部分分別進(jìn)行計(jì)算。 一個(gè)理想的并行計(jì)算是能被立即分解成許多完全獨(dú)立部分且它們能同時(shí)執(zhí)行的計(jì)算，可以貼切地稱為自然并行 。 許多問題不是自然并行的，需要使用一些技巧來(lái)解決。,9.2 并行算法設(shè)計(jì),常用算法與程序設(shè)計(jì),8,

4、SIMD共享存儲(chǔ)模型是假定有有限或無(wú)限個(gè)功能相同的處理器，每個(gè)處理器擁有簡(jiǎn)單的算術(shù)運(yùn)算和邏輯判斷能力，在理想的情況下假定存在一個(gè)容量無(wú)限大的共享存儲(chǔ)器，在任何時(shí)刻，任意一個(gè)處理器均可通過共享存儲(chǔ)器的共享單元同其他任何處理器互相交換數(shù)據(jù)，也稱之為PRAM（Parallel Random Access Machine）模型，即并行隨機(jī)存取機(jī)器。,9.2.1 SIMD共享存儲(chǔ)模型,常用算法與程序設(shè)計(jì),9,【例9.1】.廣播算法,（1）處理器P1將m復(fù)制到自己的存儲(chǔ)器中，然后將其寫入B（1） （2）for ( i = 0 ;i log N 1; i +) for j = 2i + 1 to 2 i+1

5、 par-do 處理器Pj將B（j 2i）復(fù)制到自己的存儲(chǔ)器中；然后將其寫入B（j）; end for （3）for i=1 to N par-do 處理器Pi從B（i）中讀取數(shù)據(jù)m ; end for,常用算法與程序設(shè)計(jì),10,SIMD互連網(wǎng)絡(luò)模型，簡(jiǎn)記為SIMD-IN，也稱為分布存儲(chǔ)的SIMD模型，簡(jiǎn)記為SIMD-DM。在這種模型中，每個(gè)處理器在控制器控制下或處于活動(dòng)狀態(tài)，或處于不活動(dòng)狀態(tài)?；顒?dòng)狀態(tài)的處理器都執(zhí)行相同的指令，處理器之間的數(shù)據(jù)交換是通過互連網(wǎng)絡(luò)進(jìn)行的。其中各處理器（包括算術(shù)邏輯單元和本地存儲(chǔ)器）可以通過多種互連方式連接。,9.2.2 SIMD互連網(wǎng)絡(luò)模型,常用算法與程序設(shè)計(jì),

6、11,【例9.2】一維線性模型上的并行排序算法 for ( k= 1; k ; k+ ) for each Pi : i=1,3,2-1 par-do if XiXi+1 then XiXi+1 ; end for for each Pi : i=2,4,2 par-do if XiXi+1 then XiXi+1 ; end for ,常用算法與程序設(shè)計(jì),12,共享存儲(chǔ)的MIMD計(jì)算模型是一個(gè)異步的PRAM模型，系由多個(gè)處理器組成，它的特點(diǎn)是每個(gè)處理器都有自己的本地存儲(chǔ)器、局部時(shí)鐘和局部程序；處理器間的通信經(jīng)過共享全局存儲(chǔ)器；沒有全局時(shí)鐘，各個(gè)處理器異步地執(zhí)行各自的指令；處理器任何時(shí)間依賴關(guān)

7、系必須明確地在各處理器的程序中加入同步（路）障（Synchronization Barrier）；一條指令可在非確定但有限的時(shí)間內(nèi)完成。,9.2.3 MIMD共享存儲(chǔ)模型,常用算法與程序設(shè)計(jì),13,【例9.3】并行求和算法 g = 0; for each Pi：0 i p par-do li = 0 ; for( j = 0 ; j n ; j += p ) li = li + aj; lock(g); g = g + li; unlock(g); end for,常用算法與程序設(shè)計(jì),14,MIMD異步通信計(jì)算模型可以抽象為一個(gè)無(wú)向圖，其中頂點(diǎn)集對(duì)應(yīng)處理器集合，邊集對(duì)應(yīng)處理器間的雙向通信鏈集合

8、。每個(gè)處理器都賦予惟一的編號(hào)，且只具有知曉與其有線相連的近鄰處理器的局部知識(shí)。系統(tǒng)中并無(wú)共享存儲(chǔ)器，各處理器之間的通信是通過發(fā)送和接受消息完成的。在算法運(yùn)行期間，每個(gè)處理器除了執(zhí)行自己的計(jì)算任務(wù)外，還向鄰近的處理器發(fā)送消息和接受并處理來(lái)自鄰近處理器的消息 。,9.2.4 MIMD異步通信模型,常用算法與程序設(shè)計(jì),15,【例9.4】MIMD-AC模型上的隨機(jī)k選擇算法 (1）通過對(duì)有根生成樹的一次掃描，根節(jié)點(diǎn)就可計(jì)算出總的元素?cái)?shù)B。如果B1，則根節(jié)點(diǎn)通知該元素所在節(jié)點(diǎn)將此元素送往根節(jié)點(diǎn)，算法結(jié)束；否則執(zhí)行以下各步； （2）分布隨機(jī)地從B個(gè)元素中挑選出一個(gè)元素m（劃分元素）送到根節(jié)點(diǎn)。其過程是：假

9、定每個(gè)進(jìn)程（節(jié)點(diǎn)）給其元素和其孩子都賦予一個(gè)固定的序號(hào)，并且還假定每個(gè)節(jié)點(diǎn)都知道t（1），t（p）。其中t（i）是它的第i個(gè)子樹中所有元素的數(shù)目（1ip）。根節(jié)點(diǎn)在區(qū)間1到n隨機(jī)地選擇一整數(shù)i，為了找相應(yīng)的元素，它首先檢查駐留在自己局部存儲(chǔ)器中t個(gè)元素是否是此元素；如果it，則說(shuō)明有此元素，否則根節(jié)點(diǎn)發(fā)送命令LOCATE（j）給第f個(gè)孩子，其中jitt（1）-t（f-1）（取最小正整數(shù)）。根據(jù)接受的LOCATE(j)信息，接收進(jìn)程就像根節(jié)點(diǎn)一樣作出類似的反應(yīng)。當(dāng)已經(jīng)定位到一個(gè)元素時(shí)，它就被發(fā)送至根并作為k選擇算法的劃分元素，發(fā)送給所有其他節(jié)點(diǎn)。,常用算法與程序設(shè)計(jì),16,（3）每個(gè)進(jìn)程i將其局

10、部存儲(chǔ)器中的元素按m劃分成三個(gè)子集合BLi，BEi，BGi，它們分別包含、m的那些元素。通過對(duì)生成樹從葉子到根的一次掃描，在根節(jié)點(diǎn)可計(jì)算出BL，BE，BG。一旦計(jì)算出BL、BE、BG，根節(jié)點(diǎn)就可以根據(jù)B和k決定算法是以選中m而結(jié)束，還是繼續(xù)遞歸調(diào)用。根節(jié)點(diǎn)向所有其他節(jié)點(diǎn)廣播這一決定，以便讓每個(gè)節(jié)點(diǎn)i知道集合BLi和BGi中哪一個(gè)應(yīng)作為下一次遞歸調(diào)用的參數(shù)，這一步需要交換的消息數(shù)為O（p）。 （4）根據(jù)新的參數(shù)B和k，算法就可自動(dòng)遞歸調(diào)用算法了。在分布式環(huán)境中，遞歸調(diào)用時(shí)其入口和出口均由根節(jié)點(diǎn)完成。它分布地計(jì)數(shù)現(xiàn)有活躍元素的數(shù)目。如果很多，則根節(jié)點(diǎn)通知所有其他節(jié)點(diǎn)，它們都遞歸調(diào)用它們局部的程序。

11、當(dāng)只剩下一個(gè)元素時(shí)，根節(jié)點(diǎn)就令其它節(jié)點(diǎn)將此元素發(fā)送給它，從而得到了第k個(gè)元素。此時(shí)每個(gè)進(jìn)程都可以從遞歸調(diào)用中退出而無(wú)需與根節(jié)點(diǎn)進(jìn)一步通信就可結(jié)束。,常用算法與程序設(shè)計(jì),17,9.3.1 并行程序概念 目前兩種最重要的并行編程模型是數(shù)據(jù)并行和消息傳遞。數(shù)據(jù)并行編程模型的編程級(jí)別比較高，編程相對(duì)簡(jiǎn)單，但它僅適用于數(shù)據(jù)并行問題；消息傳遞編程模型的編程級(jí)別相對(duì)較低，但消息傳遞編程模型可以有更廣泛的應(yīng)用范圍。,9.3 并行程序開發(fā),常用算法與程序設(shè)計(jì),18,9.3.2 共享存儲(chǔ)系統(tǒng)并行編程 在一個(gè)共享存儲(chǔ)器系統(tǒng)中，任一個(gè)處理器都可以訪問全部的存儲(chǔ)單元。所謂單一編址空間就是每一個(gè)存儲(chǔ)單元都由一個(gè)單地址范圍

12、內(nèi)的某個(gè)特定地址所指定。 OpenMp是一個(gè)共享存儲(chǔ)器標(biāo)準(zhǔn)，是為在多處理機(jī)上編寫并行程序而設(shè)計(jì)的一個(gè)應(yīng)用編程接口，得到許多硬件和軟件供應(yīng)商的支持,常用算法與程序設(shè)計(jì),19,“Hello World ”程序,#include #include int main() #pragma omp parallel printf(“Hello World n”); ,常用算法與程序設(shè)計(jì),20,9.3.3 分布存儲(chǔ)系統(tǒng)并行編程 對(duì)于分布存儲(chǔ)系統(tǒng)來(lái)說(shuō)，單一編址空間的假設(shè)不成立，組成系統(tǒng)的各計(jì)算機(jī)有自己的處理器和本地主存儲(chǔ)器，不能相互訪問各自的主存儲(chǔ)器，只能通過傳遞消息來(lái)進(jìn)行交互 通過在C或者Fortran語(yǔ)言中增加進(jìn)程間消息傳遞函數(shù)，可以完成大多數(shù)的并行程序設(shè)計(jì)。MPI標(biāo)準(zhǔn)是最流行的并行編程消息傳遞規(guī)范。幾乎所有商業(yè)的并行機(jī)都支持它，同時(shí)也有眾多支持MPI標(biāo)準(zhǔn)的開放軟件庫(kù)可供使用。,常用算法與程序設(shè)計(jì),21,“Hello World ”程序,#include “mpi.h” #include #include void main(argc,argv) int argc; char *argv; int myid,numprocs; int namelen; char processor_nameMPI_MAX_PROCESSOR_NAME; MPI_Init( ,常用算法與程序設(shè)計(jì),22,上機(jī)：