《1并行計(jì)算模型分析》由會(huì)員分享，可在線閱讀，更多相關(guān)《1并行計(jì)算模型分析（39頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,*,并行處理及體系結(jié)構(gòu),實(shí)踐部分,,聯(lián)系方式：,,信息科學(xué)與工程學(xué)院計(jì)算機(jī)系,,信息館413 王璿,,,E-mail:,,研究方向：并行計(jì)算、生物計(jì)算,,主要參考文獻(xiàn),1 陳國(guó)良等編著 《并行算法實(shí)踐 》2004年 高等教育出版社,,2. Bary Wilkinson著 陸鑫達(dá)譯 《并行程序設(shè)計(jì)》 2002年 機(jī)械工業(yè)出版社,,3.Calvin Lin等著，陸鑫達(dá)譯 《并行程序設(shè)計(jì)原理》 2009年 機(jī)械工業(yè)出版社,,4.Brian Goetz等著， 《Java并發(fā)編程實(shí)戰(zhàn)》 2012 機(jī)
2、械工業(yè)出版社,,問(wèn)題的并行求解過(guò)程,一個(gè)物理問(wèn)題并行求解的最終目的是將該問(wèn)題映射到并行機(jī)上，這一物理上的映射是通過(guò)不同層次上的抽象映射來(lái)實(shí)現(xiàn)的。,,在并行機(jī)上求解問(wèn)題，首先要寫(xiě)出求解問(wèn)題的并行算法。并行算法是在并行計(jì)算模型上設(shè)計(jì)出來(lái)的，而并行計(jì)算模型是從不同的并行計(jì)算機(jī)體系結(jié)構(gòu)模型中抽象出來(lái)的。然后，根據(jù)并行算法進(jìn)行并行程序設(shè)計(jì)。,,為了達(dá)到將問(wèn)題的并行求解算法轉(zhuǎn)化為特定的適合并行計(jì)算模型的并行算法的目的。需要解決兩方面的問(wèn)題：,首先是問(wèn)題的并行求解算法必須能夠?qū)?wèn)題內(nèi)在的并行特征充分體現(xiàn)出來(lái),，,否則并行求解算法將無(wú)法利用這些并行特征，從而使問(wèn)題的高效并行求解成為不可能；,其次是并行求解模型
3、要和并行計(jì)算模型盡量吻合，,這樣，就為問(wèn)題向并行機(jī)上的高效解決提供了前提。,,1 并行計(jì)算模型,什么是并行計(jì)算模型？,,并行計(jì)算模型是并行計(jì)算機(jī),基本特征的抽象,。并行計(jì)算模型從并行計(jì)算機(jī)中,抽取,若干個(gè)能夠反映計(jì)算特征的可以計(jì)算或者可以測(cè)量的,參數(shù),，按照,模型所定義的計(jì)算行為,構(gòu)造成本函數(shù)，從而進(jìn)行算法的性能分析，是算法設(shè)計(jì)和分析的基礎(chǔ)。,編程模型,,計(jì)算模型,,體系結(jié)構(gòu)模型,,機(jī)器模型,用戶(hù),系統(tǒng),,,1.1 PRAM模型,,（,Parallel Random Access Machine,）,又稱(chēng)為SIMD-SM模型（共享存儲(chǔ)的SIMD）。由Fortune和Wyllie1978年提出,
4、。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過(guò)SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。,在PRAM中有一個(gè),同步時(shí)鐘,，所有操作都是同步進(jìn)行的。,結(jié)構(gòu)圖,,回顧：共享存儲(chǔ)的多處理機(jī)模型,,,PRAM模型特點(diǎn),優(yōu)點(diǎn)：適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。,,缺點(diǎn)：不適合MIMD并行機(jī)，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素,模型中使用了一個(gè)全局共享存儲(chǔ)器，且局存容量較小，,,不足以描述分布主存多處理機(jī)的性能瓶頸，,,而且共享單一存儲(chǔ)器的假定，,,顯然不適合于分布存儲(chǔ)結(jié)構(gòu)的MIMD機(jī)器,PRAM模型是同步的，因此，,所有的指令都按照鎖步的方式,,操作,，用戶(hù)雖然感覺(jué)不到同步
5、的存在，,,但同步的存在的確很耗費(fèi)時(shí)間,，,,而且不能反映現(xiàn)實(shí)中很多系統(tǒng)的異步性,PRAM模型假設(shè)了每個(gè)處理器可在單位時(shí)間訪問(wèn),,共享存儲(chǔ)器的任一單元，因此要求處理機(jī)間通信無(wú)延遲、,,無(wú)限帶寬和無(wú)開(kāi)銷(xiāo)，略去了實(shí)際存在,,比如資源競(jìng)爭(zhēng)和有限帶寬，這是不現(xiàn)實(shí)的,,1.2 異步APRAM模型,基本概念,,又稱(chēng)分相（Phase）PRAM或MIMD-SM。,每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序,；,無(wú)全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過(guò)SM進(jìn)行通訊；處理器間依賴(lài)關(guān)系，需在并行程序中顯式地加入同步路障,。,,計(jì)算過(guò)程：由同步障分開(kāi)的全局相組成,,,計(jì)算時(shí)間,,設(shè)局部操作為單位時(shí)間；全局讀/寫(xiě)平
6、均時(shí)間為d，,,d隨著處理器數(shù)目的增加而增加；,,同步路障時(shí)間為B=B(p)非降函數(shù)。,,滿(mǎn)足關(guān)系,,令 為全局相內(nèi)各處理器執(zhí)行時(shí)間最長(zhǎng)者，則APRAM上的計(jì)算時(shí)間為,,,,,優(yōu)缺點(diǎn)：,,易編程和分析算法的復(fù)雜度，但與現(xiàn)實(shí)相差較遠(yuǎn)，其上并行算法非常有限，也不適合MIMD-DM模型。,,,回顧：分布式存儲(chǔ)多處理機(jī)模型,,,1.3 BSP模型,基本概念,,由Valiant(1990)提出的，其含義為“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)。塊內(nèi)異步并行，塊間顯示同步。,,,模型參數(shù),,● p: 處理器數(shù)(帶有存儲(chǔ)器）,,● g: 路由器吞吐率,（也稱(chēng)為帶寬因子 1/ba
7、ndwidth） 處理器模塊之間點(diǎn)對(duì)點(diǎn)傳遞消息的路由器；,,● L: 同步障時(shí)間,全局同步之間的時(shí)間間隔,；,,計(jì)算過(guò)程,,由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為右圖,,優(yōu)缺點(diǎn),,強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個(gè)編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條 消息的傳遞等。,,1.4 LogP模型,基本概念,,由Culler(1993)年提出的，是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。,,,模型參數(shù),,L：network latency,,o：communication overhead,,g：gap=1/bandwidth,
8、,P：#processors,,注：L和g反映了通訊網(wǎng)絡(luò)的容量,,（1）L(Latency),表示源節(jié)點(diǎn)與接收節(jié)點(diǎn)進(jìn)行消息傳遞所需要的等待或延遲時(shí)間的上限。,（2）o(overhead),處理器發(fā)送或接收一個(gè)消息所需的處理時(shí)間開(kāi)銷(xiāo)。,（3）g(gap),表示一臺(tái)處理機(jī)連續(xù)兩次發(fā)送或接收消息時(shí)的最小時(shí)間間隔，其倒數(shù)即每個(gè)處理器的有效通信帶寬。,（4）P(Processor),處理機(jī)/存儲(chǔ)器模塊個(gè)數(shù),,LogP模型上設(shè)計(jì)的算法和BSP模型上相似，只是算法不再有超級(jí)步的概念。所有的進(jìn)程異步地執(zhí)行，通過(guò)消息傳遞顯示地同步，處理器接收到消息后可以立即在后面計(jì)算中使用，充分利用了處理器的計(jì)算資源.,,,優(yōu)
9、缺點(diǎn),,捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲(chǔ)、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。,BSP,?,LogP,：,BSP,塊同步,?,BSP,子集同步,,?,BSP,進(jìn)程對(duì)同步＝,LogP,,回顧：分布式共享存儲(chǔ)多處理機(jī)模型,,1.5 分層模型,屬于分布共享存儲(chǔ)模型，包括均勻存儲(chǔ)層次UMH模型和分布存儲(chǔ)層次DRAM（h）模型及層次并行存儲(chǔ)HPM模型等。,,分層計(jì)算模型可將單一模型中的功能按要求分配到模型不同的層次中，緩解單一計(jì)算模型的精確性與可用性之間的矛盾。分層后，各層次模型職能不同，目標(biāo)單一，各負(fù)其責(zé)，易于設(shè)計(jì)和實(shí)現(xiàn)。,,實(shí)
10、例：四種并行計(jì)算模型上N體問(wèn)題求解算法,N體問(wèn)題及其串行算法,,N 體問(wèn)題可以描述如下: 在一定的物理空間中, 分布有N個(gè)粒子, 每對(duì)粒子間都存在相互作用力( 如萬(wàn)有引力、庫(kù)侖力等) 。它們從一個(gè)初始的狀態(tài)開(kāi)始, 每隔一定的時(shí)間步, 由于粒子間的相互作用, 粒子的狀態(tài)會(huì)有一個(gè)增量, 需要對(duì)粒子的加速度、速度、位置信息進(jìn)行更新。下面給出N 體問(wèn)題的串行算法。,r,,算法1.1 N 體問(wèn)題求解的串行算法,輸入: 空間中N 個(gè)粒子的狀態(tài)信息, 包括初始速度、位置等信息。,,輸出: 給出經(jīng)過(guò)一個(gè)時(shí)間步后所有N 個(gè)粒子的新的狀態(tài)信息。,,,Begin,,( 1) 讀入N 個(gè)粒子的初始信息,,( 2) F
11、or,i=1 to N,,For,j=1 to N,,If,i≠j,Then,,計(jì)算粒子j 對(duì)粒子i 的作用力, 并且累加;,,Endif,,Endfor,,Endfor,,( 3) For i=1 to N,,根據(jù)牛頓定律, 用( 2) 中計(jì)算出的粒子i 受到的力更新粒子i 的狀態(tài)信息,,Endfor,N個(gè)天體，每個(gè)天體計(jì)算N-1次受力，因此需要計(jì)算N×(N-1)次受力。因此算法復(fù)雜度為O(N,2,),,算法1.2 PRAM模型上N 體問(wèn)題求解并行算法,Begin,,( 1) 每個(gè)處理器讀入N/P 個(gè)粒子的初始信息,,( 2),For all Pi Where i∈[0, P- 1] Pa
12、r- Do,,For j=i×N/P+1 to ( i+1) ×N/P Do,,,For k=1 to N Do,,If j≠k Then,,計(jì)算粒子k 對(duì)粒子j 的作用力, 并且累加;,,Endif,,Endfor,,Endfor,,Endfor,//粒子j 各處理器中的N/P個(gè)粒子,//k 共享存儲(chǔ)器中的N個(gè)粒子,,原來(lái)串行算法的計(jì)算量平均分配給P個(gè)處理器。因此算法復(fù)雜度為O(N,2,/P),,( 3) For all Pi Where i∈[0, P- 1] Par- Do,,For j=i×N/P+1 to ( i+1) ×N/P Do,,根據(jù)牛頓定律, 用( 2) 中計(jì)算出的粒子j
13、 受到的力更新粒子j 的狀態(tài)信息,,Endfor,,Endfor,,,P個(gè)處理器各自負(fù)責(zé)計(jì)算N/P個(gè)粒子的受力以及對(duì)這些粒子的狀態(tài)進(jìn)行更新。因?yàn)镾M因此不考慮通訊。,,假設(shè)：N=16 P=4,SM,N/P,P,0,N/P,P,1,N/P,P,2,N/P,P,3,1~4,5~8,9~12,13~16,1~16,1~N/P,N/P+1~2N/P,2N/P+1~3N/P,3N/P+1~4N/P,1~N,,算法1.3 APRAM模型上N 體問(wèn)題求解的并行算法,Begin,,( 1) 每個(gè)處理器處理N/P 個(gè)粒子, 讀入N/P 個(gè)粒子的初始狀態(tài)信息;,,( 2),每個(gè)處理器將其上N/P 個(gè)粒子寫(xiě)入到共
14、享單元SM中;,,( 3)Barrier; /* 實(shí)施路障同步*/,,( 4) For all Pi Where i∈[0, P- 1] Par- Do,,,For j=1 to N/P Do,,,For k=1 to P- 1 Do,,,For l=1 to N/P Do,,,u=[( i+k)%P]×(N/P) +1;,,計(jì)算Pi 中粒子j 和共享單元中粒子k 之間的作用力, 并且累加;,,Endfor,,Endfor,,Barrier; /* 實(shí)施路障同步*/,,Endfor,,Endfor,,//粒子j 各處理器自己的N/P個(gè)粒子,//k 除自己之外的其他P-1個(gè)處理器,//l
15、共享單元中其他處理器中的N/P個(gè)粒子,//u 防止多個(gè)處理器同時(shí)讀取同一個(gè)共享單元，每個(gè)處理器對(duì)共享單元中讀取順序不同。,,第（4）步處理本處理機(jī)與共享單元中粒子之間的受力。其中計(jì)算某個(gè)粒子N-1個(gè)受力時(shí)，有(P-1)×N/P個(gè)要從共享單元中讀取。,,( 5),For all Pi Where i∈[0, P- 1] Par- Do,,計(jì)算Pi 中N/P 個(gè)粒子間的作用力, 并且累加;,,Endfor,,( 6) For all Pi Where i∈[0, P- 1] Par- Do,,For j=1 to N/P,,,根據(jù)牛頓定律, 用( 5) 中計(jì)算出的粒子j 受到的力, 更新粒子j的
16、狀態(tài)信息,,Endfor,,Endfor,第（5）步處理本處理機(jī)N/P個(gè)粒子之間的受力。其中計(jì)算某個(gè)粒子N-1個(gè)受力時(shí)，有N/P個(gè)從本地存儲(chǔ)單元中讀取。,,根據(jù)第4和5步，每個(gè)處理器的計(jì)算時(shí)間仍為O(N,2,/P)。但第4步中，每個(gè)處理器異步讀寫(xiě)全局存儲(chǔ)器，令全局讀寫(xiě)開(kāi)銷(xiāo)為d。計(jì)算某個(gè)粒子N-1個(gè)受力時(shí)，有(P-1)×N/P個(gè)要從共享單元中讀取，則需要時(shí)間為d× (P-1)×N/P。,因此算法復(fù)雜度為 O(N,2,/P)+d ×N,,SM,LM,,1~N/P,LM,,N/P+1~2N/P,P,0,P,1,P,2,P,3,1~N/P,,s,0,N/P+1~2N/P,,s,1,2N/P+1~3
17、N/P,,s,2,3N/P+1~4N/P,,s,3,LM,,2N/P+1~3N/P,LM,,3N/P+1~4N/P,(2),( 4)計(jì)算Pi 中粒子j 和共享單元中粒子k 之間的作用力, 并且累加;,,,這里 u=[( i+k)%P]×(N/P) +1;,,i=0 k=1 u=[(0+1)%4]×N/P+1=N/p+1,,k=2 u= [(0+2)%4]×N/P+1=2N/p+1,,k=3 u= [(0+3)%4]×N/P+1=3N/p+1,,因此，P,0,號(hào)處理器讀取共享存儲(chǔ)器的順序?yàn)閟1,s2,s3,,同理，P,1,號(hào)讀取順序?yàn)閟2,s3,s0；P,2,號(hào)讀取順序?yàn)閟3,s0,s1；,
18、,P,3,號(hào)讀取順序?yàn)閟0,s1,s2,（4）,（5）處理本處理機(jī)N/P個(gè)粒子之間的受力,（5）,,算法1.4 BSP模型上N 體問(wèn)題并行算法,Begin,,( 1) 每個(gè)處理器處理N/P 個(gè)粒子, 讀入N/P 個(gè)粒子的初始狀態(tài)信息;,,( 2) For all Pi Where i∈[0, P- 1] Par- Do,,計(jì)算Pi 內(nèi)部粒子間的作用力;,,,Pi 把其內(nèi)N/P 個(gè)粒子的狀態(tài)信息發(fā)送給其右鄰居;,,Endfor,,( 3),Barrier,;,,內(nèi)部N/P個(gè)粒子受力計(jì)算(N/P),×,(N/P-1) ，然后將本地N/P個(gè)粒子的狀態(tài)信息發(fā)送,通訊時(shí)間為 （N/P）,×g。,,,則第
19、一個(gè)超級(jí)步內(nèi)包含計(jì)算時(shí)間和發(fā)送時(shí)間。然后進(jìn)入之后的P-1個(gè)超級(jí)步。,,( 4),For all Pi Where i∈[0, P- 1] Par- Do,,,For j=0 to P- 2 Do,,,Pi 接收其左鄰居發(fā)送過(guò)來(lái)的粒子信息,;,,Pi 計(jì)算其內(nèi)粒子和收到的粒子間的作用力, 并且累加;,,,Pi 把其接收到粒子的狀態(tài)信息發(fā)送給其右鄰居,;,,,Barrier;,,Endfor,,Endfor,,每個(gè)超級(jí)步內(nèi)包括計(jì)算時(shí)間，通信時(shí)間和同步時(shí)間。整個(gè)計(jì)算需要超級(jí)步為O(P)。因此算法執(zhí)行時(shí)間為：,,,O(,P,×((N/P),2,+ 2 × N/P ×g +B))=,,O(N,2,/P+
20、2 × N×g+B ×P),通信時(shí)間N/P ×g,通信時(shí)間N/P ×g,計(jì)算時(shí)間,,N/P × N/P,同步時(shí)間,,B,,( 5) For all Pi Where i∈[0, P- 1] Par- Do,,For j=1 to N/P,,根據(jù)牛頓定律, 用( 5) 中計(jì)算出的粒子j 受到的力, 更新粒子j 的狀態(tài)信息;,,Endfor,,Endfor,,,,,算法1.5 LogP模型上N 體問(wèn)題并行算法,Begin,,( 1) 每個(gè)處理器處理N/P 個(gè)粒子, 讀入N/P 個(gè)粒子的初始狀態(tài)信息;,,( 2) For all Pi Where i∈[0, P- 1],,計(jì)算Pi 內(nèi)部粒子間的作用
21、力;,,Pi 把其內(nèi)N/P 個(gè)粒子的狀態(tài)信息發(fā)送給其右鄰居;,,,( 3) For all Pi Where i∈[0, P- 1] Par- Do,,For j=0 to P- 2 Do,,Pi 接收其左鄰居發(fā)送過(guò)來(lái)的粒子信息;,,Pi 把其接收到粒子的狀態(tài)信息發(fā)送給其右鄰居;,,Pi 計(jì)算其內(nèi)粒子和收到的粒子間的作用力;,,Endfor,,Endfor,進(jìn)程異步執(zhí)行,,( 4) For all Pi Where i∈[0, P- 1] Do,,For j=1 to N/P,,根據(jù)牛頓定律, 用( 3) 中計(jì)算出的粒子j 受到的力, 更新粒子j 的狀態(tài)信息;,,Endfor,,Endfor,
22、,,所有計(jì)算平均分配到P個(gè)處理器上執(zhí)行，因此計(jì)算時(shí)間為,O(N,2,/P)。,每個(gè)處理器需要進(jìn)行P-1次消息傳遞，每次傳遞N/P個(gè)粒子信息。處理器傳遞大小為N/P的信息包的開(kāi)銷(xiāo)為2,×,o+L+ (N/P),×g。因?yàn)?每個(gè)處理器,需要與其他P-1個(gè)處理器進(jìn)行通信，,通信開(kāi)銷(xiāo)為(P-1) ×(,2,×,o+L+ (N/P),×g)。,這樣P個(gè)處理器,總的通信開(kāi)銷(xiāo)為,P,×((P-1) ×(,2,×,o+L+ (N/P),×g)),。因此，算法總體執(zhí)行時(shí)間為：,,O(,N,2,/P+ P,×((P-1) ×(,2,×,o+L+ (N/P),×g))),,,課后練習(xí)：,,1. 通過(guò)N體問(wèn)題在四個(gè)不同并行計(jì)算模型上算法設(shè)計(jì)，了解四種模型的特點(diǎn)。,,,課后閱讀：,,苗乾坤等.若干并行計(jì)算模型上的N體問(wèn)題求解算法.計(jì)算機(jī)工程與應(yīng)用.2007,43(10):52-55,,,
1并行計(jì)算模型分析
