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