Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,,?#?,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),,,*,并行處理及體系結(jié)構(gòu),實(shí)踐部分,,,聯(lián)系方式：,信息科學(xué)與工程學(xué)院計(jì)算機(jī)系,信息館413 王璿,,E-mail:,研究方向：并行計(jì)算、生物計(jì)算,,,主要參考文獻(xiàn),1 陳國良等編著 《并行算法實(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è)出版社,,,問題的并行求解過程,一個(gè)物理問題并行求解的最終目的是將該問題映射到并行機(jī)上，這一物理上的映射是通過不同層次上的抽象映射來實(shí)現(xiàn)的。,,,在并行機(jī)上求解問題，首先要寫出求解問題的并行算法。并行算法是在并行計(jì)算模型上設(shè)計(jì)出來的，而并行計(jì)算模型是從不同的并行計(jì)算機(jī)體系結(jié)構(gòu)模型中抽象出來的。然后，根據(jù)并行算法進(jìn)行并行程序設(shè)計(jì)。,,,為了達(dá)到將問題的并行求解算法轉(zhuǎn)化為特定的適合并行計(jì)算模型的并行算法的目的。需要解決兩方面的問題：,首先是問題的并行求解算法必須能夠?qū)栴}內(nèi)在的并行特征充分體現(xiàn)出來,，,否則并行求解算法將無法利用這些并行特征，從而使問題的高效并行求解成為不可能；,其次是并行求解模型要和并行計(jì)算模型盡量吻合，,這樣，就為問題向并行機(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ī)器模型,用戶,系統(tǒng),,,,,1.1 PRAM模型,（,Parallel Random Access Machine,）,又稱為SIMD-SM模型（共享存儲(chǔ)的SIMD）。由Fortune和Wyllie1978年提出,。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過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模型是同步的，因此，,所有的指令都按照鎖步的方式,操作,，用戶雖然感覺不到同步的存在，,但同步的存在的確很耗費(fèi)時(shí)間,，,而且不能反映現(xiàn)實(shí)中很多系統(tǒng)的異步性,PRAM模型假設(shè)了每個(gè)處理器可在單位時(shí)間訪問,共享存儲(chǔ)器的任一單元，因此要求處理機(jī)間通信無延遲、,無限帶寬和無開銷，略去了實(shí)際存在,比如資源競(jìng)爭(zhēng)和有限帶寬，這是不現(xiàn)實(shí)的,,,1.2 異步APRAM模型,基本概念,又稱分相（Phase）PRAM或MIMD-SM。,每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序,；,無全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障,。,,,計(jì)算過程：由同步障分開的全局相組成,,,,計(jì)算時(shí)間,設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，,d隨著處理器數(shù)目的增加而增加；,同步路障時(shí)間為B=B(p)非降函數(shù)。,滿足關(guān)系,令 為全局相內(nèi)各處理器執(zhí)行時(shí)間最長者，則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ì)算過程,由若干超級(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,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í)間開銷。,（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í)行，通過消息傳遞顯示地同步，處理器接收到消息后可以立即在后面計(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ì)同步＝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í)例：四種并行計(jì)算模型上N體問題求解算法,N體問題及其串行算法,N 體問題可以描述如下: 在一定的物理空間中, 分布有N個(gè)粒子, 每對(duì)粒子間都存在相互作用力( 如萬有引力、庫侖力等) 。它們從一個(gè)初始的狀態(tài)開始, 每隔一定的時(shí)間步, 由于粒子間的相互作用, 粒子的狀態(tài)會(huì)有一個(gè)增量, 需要對(duì)粒子的加速度、速度、位置信息進(jìn)行更新。下面給出N 體問題的串行算法。,r,,,算法1.1 N 體問題求解的串行算法,輸入: 空間中N 個(gè)粒子的狀態(tài)信息, 包括初始速度、位置等信息。,輸出: 給出經(jīng)過一個(gè)時(shí)間步后所有N 個(gè)粒子的新的狀態(tài)信息。,,Begin,( 1) 讀入N 個(gè)粒子的初始信息,( 2) For,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 體問題求解并行算法,Begin,( 1) 每個(gè)處理器讀入N/P 個(gè)粒子的初始信息,( 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,計(jì)算粒子k 對(duì)粒子j 的作用力, 并且累加;,Endif,Endfor,Endfor,Endfor,//粒子j 各處理器中的N/P個(gè)粒子,//k 共享存儲(chǔ)器中的N個(gè)粒子,,原來串行算法的計(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 受到的力更新粒子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 體問題求解的并行算法,Begin,( 1) 每個(gè)處理器處理N/P 個(gè)粒子, 讀入N/P 個(gè)粒子的初始狀態(tài)信息;,( 2),每個(gè)處理器將其上N/P 個(gè)粒子寫入到共享單元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 共享單元中其他處理器中的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的狀態(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è)處理器異步讀寫全局存儲(chǔ)器，令全局讀寫開銷為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~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)計(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；,P,3,號(hào)讀取順序?yàn)閟0,s1,s2,（4）,（5）處理本處理機(jī)N/P個(gè)粒子之間的受力,（5）,,,算法1.4 BSP模型上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。,,則第一個(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ā)送過來的粒子信息,;,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+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 體問題并行算法,Begin,( 1) 每個(gè)處理器處理N/P 個(gè)粒子, 讀入N/P 個(gè)粒子的初始狀態(tài)信息;,( 2) For all Pi Where i∈[0, P- 1],計(jì)算Pi 內(nèi)部粒子間的作用力;,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ā)送過來的粒子信息;,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,,所有計(jì)算平均分配到P個(gè)處理器上執(zhí)行，因此計(jì)算時(shí)間為,O(N,2,/P)。,每個(gè)處理器需要進(jìn)行P-1次消息傳遞，每次傳遞N/P個(gè)粒子信息。處理器傳遞大小為N/P的信息包的開銷為2,×,o+L+ (N/P),×g。因?yàn)?每個(gè)處理器,需要與其他P-1個(gè)處理器進(jìn)行通信，,通信開銷為(P-1) ×(,2,×,o+L+ (N/P),×g)。,這樣P個(gè)處理器,總的通信開銷為,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. 通過N體問題在四個(gè)不同并行計(jì)算模型上算法設(shè)計(jì)，了解四種模型的特點(diǎn)。,,課后閱讀：,苗乾坤等.若干并行計(jì)算模型上的N體問題求解算法.計(jì)算機(jī)工程與應(yīng)用.2007,43(10):52-55,,,,內(nèi)容總結(jié),并行處理及體系結(jié)構(gòu)。在并行機(jī)上求解問題，首先要寫出求解問題的并行算法。每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序。同步路障時(shí)間為B=B(p)非降函數(shù)。由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為右圖。BSP?LogP：BSP塊同步?BSP子集同步。//k 共享存儲(chǔ)器中的N個(gè)粒子。假設(shè)：N=16 P=4。其中計(jì)算某個(gè)粒子N-1個(gè)受力時(shí)，有N/P個(gè)從本地存儲(chǔ)單元中讀取。因此，P0號(hào)處理器讀取共享存儲(chǔ)器的順序?yàn)閟1,s2,s3。同理，P1號(hào)讀取順序?yàn)閟2,s3,s0。P3號(hào)讀取順序?yàn)閟0,s1,s2。則第一個(gè)超級(jí)步內(nèi)包含計(jì)算時(shí)間和發(fā)送時(shí)間。每個(gè)超級(jí)步內(nèi)包括計(jì)算時(shí)間，通信時(shí)間和同步時(shí)間。每個(gè)處理器需要進(jìn)行P-1次消息傳遞，每次傳遞N/P個(gè)粒子信息。課后閱讀：。苗乾坤等.若干并行計(jì)算模型上的N體問題求解算法.計(jì)算機(jī)工程與應(yīng)用.2007,43(10):52-55,