并行計(jì)算模型分析課件

《并行計(jì)算模型分析課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(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ī)械工業(yè)出版社,問(wèn)題的并行求解過(guò)程,一個(gè)物理問(wèn)題并行求解的最終目

2、的是將該問(wèn)題映射到并行機(jī)上，這一物理上的映射是通過(guò)不同層次上的抽象映射來(lái)實(shí)現(xiàn)的。,在并行機(jī)上求解問(wèn)題，首先要寫出求解問(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)題的高效并行求解成為不可能；,其次是并行求解模型要和并行計(jì)算模型盡量吻合，,這樣，就為問(wèn)題向并行機(jī)上的高效解決提供了

3、前提。,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ī)器模型,用戶,系統(tǒng),1.1 PRAM模型,（,Parallel Random Access Machine,）,又稱為SIMD-SM模型（共享存儲(chǔ)的SIMD）。由Fortune和Wyllie1978年提出,。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過(guò)SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。,

4、在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模型是同步的，因此，,所有的指令都按照鎖步的方式,操作,，用戶雖然感覺(jué)不到同步的存在，,但同步的存在的確很耗費(fèi)時(shí)間,，,而且不能反映現(xiàn)實(shí)中很多系統(tǒng)的異步性,PRAM模型假設(shè)了每個(gè)

5、處理器可在單位時(shí)間訪問(wèn),共享存儲(chǔ)器的任一單元，因此要求處理機(jī)間通信無(wú)延遲、,無(wú)限帶寬和無(wú)開(kāi)銷，略去了實(shí)際存在,比如資源競(jìng)爭(zhēng)和有限帶寬，這是不現(xiàn)實(shí)的,1.2 異步APRAM模型,基本概念,又稱分相（Phase）PRAM或MIMD-SM。,每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序,；,無(wú)全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過(guò)SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障,。,計(jì)算過(guò)程：由同步障分開(kāi)的全局相組成,計(jì)算時(shí)間,設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，,d隨著處理器數(shù)目的增加而增加；,同步路障時(shí)間為B=B(p)非降函數(shù)。,滿足關(guān)系,令 為全局相內(nèi)各處理器執(zhí)行時(shí)間

6、最長(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:路由器吞吐率,（也稱為帶寬因子 1/bandwidth）處理器模塊之間點(diǎn)對(duì)點(diǎn)傳遞消息的路由器；,L:同步障時(shí)間,全局同步之間的時(shí)間間隔,；,計(jì)算過(guò)程,由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為右圖,優(yōu)缺點(diǎn),強(qiáng)調(diào)了計(jì)算和通訊

7、的分離，提供了一個(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,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í)

8、間開(kāi)銷。,（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)缺點(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ì)同步,L

9、ogP,回顧：分布式共享存儲(chǔ)多處理機(jī)模型,1.5 分層模型,屬于分布共享存儲(chǔ)模型，包括均勻存儲(chǔ)層次UMH模型和分布存儲(chǔ)層次DRAM（h）模型及層次并行存儲(chǔ)HPM模型等。,分層計(jì)算模型可將單一模型中的功能按要求分配到模型不同的層次中，緩解單一計(jì)算模型的精確性與可用性之間的矛盾。分層后，各層次模型職能不同，目標(biāo)單一，各負(fù)其責(zé)，易于設(shè)計(jì)和實(shí)現(xiàn)。,實(shí)例：四種并行計(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ì)有一

10、個(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)For,i=1 to N,For,j=1 to N,If,ij,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

11、次受力，因此需要計(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 i0,P-1 Par-Do,For j=iN/P+1 to(i+1)N/P Do,For k=1 to N Do,If jk 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),

12、(3)For all Pi Where i0,P-1 Par-Do,For j=iN/P+1 to(i+1)N/P Do,根據(jù)牛頓定律,用(2)中計(jì)算出的粒子j 受到的力更新粒子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,14,58,912,1316,116,1N/P,N/P+12N/P,2N/P+13N/P,3N/P+14N/P,1N,算法1.3 APRAM模型上N 體問(wèn)題求解的并行算法,Begin,(1

13、)每個(gè)處理器處理N/P 個(gè)粒子,讀入N/P 個(gè)粒子的初始狀態(tài)信息;,(2),每個(gè)處理器將其上N/P 個(gè)粒子寫入到共享單元SM中;,(3)Barrier;/*實(shí)施路障同步*/,(4)For all Pi Where i0,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 除自己之外

14、的其他P-1個(gè)處理器,/l 共享單元中其他處理器中的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 i0,P-1 Par-Do,計(jì)算Pi 中N/P 個(gè)粒子間的作用力,并且累加;,Endfor,(6)For all Pi Where i0,P-1 Par-Do,For j=1 to N/P,根據(jù)牛頓定律,用(5)中計(jì)算出的粒子j 受到的力,更新粒子j的狀態(tài)信息,Endfor,Endfo

15、r,第（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è)處理器異步讀寫全局存儲(chǔ)器，令全局讀寫開(kāi)銷為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,1N/P,LM,N/P+12N/P,P,0,P,1,P,2,P,3,1N/P,s,0,N/P+12N/P,s,1,2N/P+13N/P,s,2,3N/P+14N/P,s,3,LM,2N/P+13N/P,

16、LM,3N/P+14N/P,(2),(4)計(jì)算Pi 中粒子j 和共享單元中粒子k 之間的作用力,并且累加;,這里 u=(i+k)%P(N/P)+1;,i=0 k=1 u=(0+1)%4N/P+1=N/p+1,k=2 u=(0+2)%4N/P+1=2N/p+1,k=3 u=(0+3)%4N/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；,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 i0,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。,則第