《1并行計算模型分析》由會員分享，可在線閱讀，更多相關(guān)《1并行計算模型分析（39頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,并行處理及體系結(jié)構(gòu),實踐部分,聯(lián)系方式：,信息科學(xué)與工程學(xué)院計算機(jī)系,信息館413 王璿,E-mail:,研究方向：并行計算、生物計算,主要參考文獻(xiàn),1 陳國良等編著 并行算法實踐 2004年 高等教育出版社,2.Bary Wilkinson著 陸鑫達(dá)譯 并行程序設(shè)計 2002年 機(jī)械工業(yè)出版社,3.Calvin Lin等著，陸鑫達(dá)譯 并行程序設(shè)計原理 2009年 機(jī)械工業(yè)出版社,4.Brian Goetz等著，Java并發(fā)編程實戰(zhàn) 2012 機(jī)械工業(yè)出版社,問題的并行求解過程,一個物理問題并行求解的最終目

2、的是將該問題映射到并行機(jī)上，這一物理上的映射是通過不同層次上的抽象映射來實現(xiàn)的。,在并行機(jī)上求解問題，首先要寫出求解問題的并行算法。并行算法是在并行計算模型上設(shè)計出來的，而并行計算模型是從不同的并行計算機(jī)體系結(jié)構(gòu)模型中抽象出來的。然后，根據(jù)并行算法進(jìn)行并行程序設(shè)計。,為了達(dá)到將問題的并行求解算法轉(zhuǎn)化為特定的適合并行計算模型的并行算法的目的。需要解決兩方面的問題：,首先是問題的并行求解算法必須能夠?qū)栴}內(nèi)在的并行特征充分體現(xiàn)出來,，,否則并行求解算法將無法利用這些并行特征，從而使問題的高效并行求解成為不可能；,其次是并行求解模型要和并行計算模型盡量吻合，,這樣，就為問題向并行機(jī)上的高效解決提供了

3、前提。,1 并行計算模型,什么是并行計算模型？,并行計算模型是并行計算機(jī),基本特征的抽象,。并行計算模型從并行計算機(jī)中,抽取,若干個能夠反映計算特征的可以計算或者可以測量的,參數(shù),，按照,模型所定義的計算行為,構(gòu)造成本函數(shù)，從而進(jìn)行算法的性能分析，是算法設(shè)計和分析的基礎(chǔ)。,編程模型,計算模型,體系結(jié)構(gòu)模型,機(jī)器模型,用戶,系統(tǒng),1.1 PRAM模型,（,Parallel Random Access Machine,）,又稱為SIMD-SM模型（共享存儲的SIMD）。由Fortune和Wyllie1978年提出,。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計算。,

4、在PRAM中有一個,同步時鐘,，所有操作都是同步進(jìn)行的。,結(jié)構(gòu)圖,回顧：共享存儲的多處理機(jī)模型,PRAM模型特點,優(yōu)點：適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。,缺點：不適合MIMD并行機(jī)，忽略了SM的競爭、通訊延遲等因素,模型中使用了一個全局共享存儲器，且局存容量較小，,不足以描述分布主存多處理機(jī)的性能瓶頸，,而且共享單一存儲器的假定，,顯然不適合于分布存儲結(jié)構(gòu)的MIMD機(jī)器,PRAM模型是同步的，因此，,所有的指令都按照鎖步的方式,操作,，用戶雖然感覺不到同步的存在，,但同步的存在的確很耗費(fèi)時間,，,而且不能反映現(xiàn)實中很多系統(tǒng)的異步性,PRAM模型假設(shè)了每個

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

6、最長者，則APRAM上的計算時間為,優(yōu)缺點：,易編程和分析算法的復(fù)雜度，但與現(xiàn)實相差較遠(yuǎn)，其上并行算法非常有限，也不適合MIMD-DM模型。,回顧：分布式存儲多處理機(jī)模型,1.3 BSP模型,基本概念,由Valiant(1990)提出的，其含義為“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)。塊內(nèi)異步并行，塊間顯示同步。,模型參數(shù),p:處理器數(shù)(帶有存儲器）,g:路由器吞吐率,（也稱為帶寬因子 1/bandwidth）處理器模塊之間點對點傳遞消息的路由器；,L:同步障時間,全局同步之間的時間間隔,；,計算過程,由若干超級步組成，每個超級步計算模式為右圖,優(yōu)缺點,強(qiáng)調(diào)了計算和通訊

7、的分離，提供了一個編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條 消息的傳遞等。,1.4 LogP模型,基本概念,由Culler(1993)年提出的，是一種分布存儲的、點到點通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實行隱式同步。,模型參數(shù),L：network latency,o：communication overhead,g：gap=1/bandwidth,P：#processors,注：L和g反映了通訊網(wǎng)絡(luò)的容量,（1）L(Latency),表示源節(jié)點與接收節(jié)點進(jìn)行消息傳遞所需要的等待或延遲時間的上限。,（2）o(overhead),處理器發(fā)送或接收一個消息所需的處理時

8、間開銷。,（3）g(gap),表示一臺處理機(jī)連續(xù)兩次發(fā)送或接收消息時的最小時間間隔，其倒數(shù)即每個處理器的有效通信帶寬。,（4）P(Processor),處理機(jī)/存儲器模塊個數(shù),LogP模型上設(shè)計的算法和BSP模型上相似，只是算法不再有超級步的概念。所有的進(jìn)程異步地執(zhí)行，通過消息傳遞顯示地同步，處理器接收到消息后可以立即在后面計算中使用，充分利用了處理器的計算資源.,優(yōu)缺點,捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)洹⒙酚?、協(xié)議，可以應(yīng)用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計和分析。,BSP,LogP,：,BSP,塊同步,BSP,子集同步,BSP,進(jìn)程對同步,L

9、ogP,回顧：分布式共享存儲多處理機(jī)模型,1.5 分層模型,屬于分布共享存儲模型，包括均勻存儲層次UMH模型和分布存儲層次DRAM（h）模型及層次并行存儲HPM模型等。,分層計算模型可將單一模型中的功能按要求分配到模型不同的層次中，緩解單一計算模型的精確性與可用性之間的矛盾。分層后，各層次模型職能不同，目標(biāo)單一，各負(fù)其責(zé)，易于設(shè)計和實現(xiàn)。,實例：四種并行計算模型上N體問題求解算法,N體問題及其串行算法,N 體問題可以描述如下:在一定的物理空間中,分布有N個粒子,每對粒子間都存在相互作用力(如萬有引力、庫侖力等)。它們從一個初始的狀態(tài)開始,每隔一定的時間步,由于粒子間的相互作用,粒子的狀態(tài)會有一

10、個增量,需要對粒子的加速度、速度、位置信息進(jìn)行更新。下面給出N 體問題的串行算法。,r,算法1.1 N 體問題求解的串行算法,輸入:空間中N 個粒子的狀態(tài)信息,包括初始速度、位置等信息。,輸出:給出經(jīng)過一個時間步后所有N 個粒子的新的狀態(tài)信息。,Begin,(1)讀入N 個粒子的初始信息,(2)For,i=1 to N,For,j=1 to N,If,ij,Then,計算粒子j 對粒子i 的作用力,并且累加;,Endif,Endfor,Endfor,(3)For i=1 to N,根據(jù)牛頓定律,用(2)中計算出的粒子i 受到的力更新粒子i 的狀態(tài)信息,Endfor,N個天體，每個天體計算N-1

11、次受力，因此需要計算N(N-1)次受力。因此算法復(fù)雜度為O(N,2,),算法1.2 PRAM模型上N 體問題求解并行算法,Begin,(1)每個處理器讀入N/P 個粒子的初始信息,(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,計算粒子k 對粒子j 的作用力,并且累加;,Endif,Endfor,Endfor,Endfor,/粒子j 各處理器中的N/P個粒子,/k 共享存儲器中的N個粒子,原來串行算法的計算量平均分配給P個處理器。因此算法復(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 的狀態(tài)信息,Endfor,Endfor,P個處理器各自負(fù)責(zé)計算N/P個粒子的受力以及對這些粒子的狀態(tài)進(jìn)行更新。因為SM因此不考慮通訊。,假設(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 體問題求解的并行算法,Begin,(1

13、)每個處理器處理N/P 個粒子,讀入N/P 個粒子的初始狀態(tài)信息;,(2),每個處理器將其上N/P 個粒子寫入到共享單元SM中;,(3)Barrier;/*實施路障同步*/,(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;,計算Pi 中粒子j 和共享單元中粒子k 之間的作用力,并且累加;,Endfor,Endfor,Barrier;/*實施路障同步*/,Endfor,Endfor,/粒子j 各處理器自己的N/P個粒子,/k 除自己之外

14、的其他P-1個處理器,/l 共享單元中其他處理器中的N/P個粒子,/u 防止多個處理器同時讀取同一個共享單元，每個處理器對共享單元中讀取順序不同。,第（4）步處理本處理機(jī)與共享單元中粒子之間的受力。其中計算某個粒子N-1個受力時，有(P-1)N/P個要從共享單元中讀取。,(5),For all Pi Where i0,P-1 Par-Do,計算Pi 中N/P 個粒子間的作用力,并且累加;,Endfor,(6)For all Pi Where i0,P-1 Par-Do,For j=1 to N/P,根據(jù)牛頓定律,用(5)中計算出的粒子j 受到的力,更新粒子j的狀態(tài)信息,Endfor,Endfo

15、r,第（5）步處理本處理機(jī)N/P個粒子之間的受力。其中計算某個粒子N-1個受力時，有N/P個從本地存儲單元中讀取。,根據(jù)第4和5步，每個處理器的計算時間仍為O(N,2,/P)。但第4步中，每個處理器異步讀寫全局存儲器，令全局讀寫開銷為d。計算某個粒子N-1個受力時，有(P-1)N/P個要從共享單元中讀取，則需要時間為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)計算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,號處理器讀取共享存儲器的順序為s1,s2,s3,同理，P,1,號讀取順序為s2,s3,s0；P,2,號讀取順序為s3,s0,s1；,P,3,號讀取順序為s0,s1,s2,（4）,（5）處理本處理機(jī)N/P個粒子之間的受力,（5）,算法1.4 BSP模型上N 體問題并行算法,Begin,(1)每個處理器處理N/P 個粒子,讀入N/P 個粒子的初始狀態(tài)信息;,(2)For all Pi Where i0,P-1 Par-Do,計算Pi 內(nèi)部粒子間的作用力;,Pi 把其內(nèi)N/P 個粒子的狀態(tài)信息發(fā)送給其右鄰居;,Endfor,(3),Barrier,;,內(nèi)部N/P個粒子受力計算(N/P),(N/P-1)，然后將本地N/P個粒子的狀態(tài)信息發(fā)送,通訊時間為（N/P）,g。,則第