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

1、Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,并行算法,*,/Ch1,并行算法,1,/Ch1,Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bul

2、let,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,2024/10/21,Parallel Algorithms,Chapter,1,Foundation of Parallel Algorithms,Spring,2018,2023/8/6Parallel Algorithms,2024/10/21,主要內(nèi)容,1.1,并行計算機體系結(jié)構(gòu),并行計算機的分類,并行計算機的互連方式,1.2,并行計算模型,PRAM,模型,異步,APRAM,模型,BSP,模型

3、,LogP,模型,1.3,并行算法的一般概念,并行算法的定義和分類,相關性與可并行化,并行算法的表示,并行算法的復雜度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通訊,2023/8/6主要內(nèi)容1.1 并行計算機體系結(jié)構(gòu),2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,并行計算機分類,Flynn,分類（,1966,年）,(1),單指令流單數(shù)據(jù)流機,SISD,，即傳統(tǒng)的單處理機,(2),單指令流多數(shù)據(jù)流機,SIMD,(3),多指令流單數(shù)據(jù)流機,MISD,，實際中不存在的機器,(4),多指令流多數(shù)據(jù)流機,MIMD,并行機的結(jié)構(gòu)模型,實際的機器體系結(jié)構(gòu),SIMD(Single I

4、nstruction Multiple Data,單指令流多數(shù)據(jù)流機,),PVP (Parallel Vector Processor,并行向量機,),SMP (Symmetric Multiprocessor,對稱多處理機,),MPP (Massively Parallel Processor,大規(guī)模并行處理機,),COW(Cluster of Workstation,工作站機群,),DSM (Distributed Shared Memory,分布共享存儲多處理機,),注：,SIMD,是專用并行機，后,5,種屬于,MIMD,并行機。,2023/8/61.1 并行計算機的體系結(jié)構(gòu):并行計算機

5、分,2024/10/21,SISD computer-Von Neumanns model,1.1,并行計算機的體系結(jié)構(gòu),:,并行計算機分類,SIMD computer,2023/8/6SISD computer-Von Neu,2024/10/21,Symmetric multiprocessor,MIMD-SM,1.1,并行計算機的體系結(jié)構(gòu),:,并行計算機分類,Massively parallel processor,MIMD-DM,2023/8/6Symmetric multiprocess,2024/10/21,Cluster of workstations,MIMD-DM,1.1,并

6、行計算機的體系結(jié)構(gòu),:,并行計算機分類,2023/8/6Cluster of workstation,2024/10/21,VP,VP,VP,交叉開關,SM,(a)PVP,P/C,P/C,P/C,總線或交叉開關,SM,(b)SMP,物理上單一地址空間,P/C,P/C,P/C,定制網(wǎng)絡,LM,LM,LM,(c)MPP,物理,/,邏輯上多地址空間,P/C,P/C,P/C,定制網(wǎng)絡,LM,LM,LM,虛擬分布共享存儲,(DSM),(d)DSM(MPP/Cluster),邏輯上單一地址空間,結(jié)構(gòu)模型,物理機模型,P/C,P/C,P/C,定制,/,標準網(wǎng)絡,LM,LM,LM,(e)Cluster/COW

7、,物理,/,邏輯上多地址空間,1.1,并行計算機的體系結(jié)構(gòu),:,并行計算機分類,2023/8/6VPVPVP交叉開關SM(a)PVPP/,2024/10/21,SMP,MPP,MPP,WAN,LM,DSM,SM,(h)Grid(Cluster of Clusters),SMP,SMP,SMP,SAN/LAN,SM,SM,SM,MPP,MPP,MPP,SAN/LAN,DSM,DSM,DSM,(f)SMP-Cluster,(g)DSM-Cluster,結(jié)構(gòu)模型,物理機模型,1.1,并行計算機的體系結(jié)構(gòu),:,并行計算機分類,2023/8/6SMPMPPMPPWANLMDSMSM(h,2024/10/

8、21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡,(,固定連接,),connected graph vertices=processing nodes,edges=communication links,(1),一維線性連接,LA(1-D Linear Array),一維陣列,不帶環(huán)繞的,1-D LA,，帶環(huán)繞的,1-D LA,(2),網(wǎng)孔連接,MC(Mesh Connected),二維陣列,不帶環(huán)繞的,MC,，帶環(huán)繞的,MC,2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡,(3),樹形連

9、接,TC(Tree Connected),二叉樹，胖樹,2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡,(4),樹網(wǎng)連接,MT(Mesh of tree),2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡,(5),金字塔連接,(Pyramid),(6),超立方連接,HC(Hypercube Connected),3,立方，,4,立方,(7),立方環(huán)連接,CCC(Cube Connected-Cycles),(8),

10、洗牌交換連接,SE(Shuffle Exchange),(9),蝶形連接,(Butterfly Connected),2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡,:,嵌入,將網(wǎng)絡中的各節(jié)點映射到另一個網(wǎng)絡中去,用膨脹（,Dilation,）系數(shù)來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡中的一條鏈路在所要嵌入的網(wǎng)絡中對應所需的最大鏈路數(shù),如果該系數(shù)為,1,，則稱為完美嵌入。,環(huán)網(wǎng)可完美嵌入到,2-D,環(huán)繞網(wǎng)中,超立方網(wǎng)可完美嵌入到,2,D,環(huán)繞網(wǎng)中,2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式靜態(tài),

11、2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡,:,嵌入,Ring onto 2-D torus,Hypercube onto 2-D torus,2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結(jié)構(gòu),:,互連方式,動態(tài)互連網(wǎng)絡,(,非固定連接,),(1),總線,Bus,(2),交叉開關,Crossbar Switcher,：一種高帶寬網(wǎng)絡,(3),多級互連網(wǎng)絡,Multistage Interconnection Network,一種大型開關網(wǎng)絡,2023/8/61.1 并行計算機的體系結(jié)構(gòu):互連方式動

12、態(tài),2024/10/21,主要內(nèi)容,1.1,并行計算機體系結(jié)構(gòu),并行計算機的分類,并行計算機的互連方式,1.2,并行計算模型,PRAM,模型,異步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定義和分類,相關性與可并行化,并行算法的表示,并行算法的復雜度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通訊,2023/8/6主要內(nèi)容1.1 并行計算機體系結(jié)構(gòu),2024/10/21,1.2,并行計算模型,:,PRAM,模型,描述,由,Fortune,和,Wyllie1978,年提出，稱為并行隨機存取機器,PRAM,，又稱,SIMD-SM,模型。有

13、一個集中的共享存儲器和一個指令控制器，通過,SM,的,R/W,交換數(shù)據(jù)，隱式同步計算。,假設,SM,的容量無限,有限,/,無限個功能相同的處理器,本地指令和,SM,的,R/W,操作都取單位時間,結(jié)構(gòu)圖,Control Unit,Interconnection Network,P,LM,P,LM,P,LM,P,LM,Shared Memory,2023/8/61.2 并行計算模型:PRAM模型描述Co,2024/10/21,1.2,并行計算模型,:,PRAM,模型,分類,PRAM-CRCW,并發(fā)讀并發(fā)寫,CPRAM-CRCW(Common PRAM-CRCW),：僅允許寫入相同數(shù)據(jù),PPRAM-

14、CRCW(Priority PRAM-CRCW),：僅允許優(yōu)先級最高的處理器寫入,APRAM-CRCW(Arbitrary PRAM-CRCW),：允許任意處理器自由寫入,PRAM-CREW,并發(fā)讀互斥寫,PRAM-EREW,互斥讀互斥寫,計算能力比較,PRAM-CRCW,是最強的計算模型，,PRAM-EREW,可,logp,倍模擬,PRAM-CREW,和,PRAM-CRCW,。令,Tm,是在模型,M,上的運行時間，則：,1979,年，,Eckstain,曾經(jīng)使用二叉樹方法來解決沖突問題,解決讀沖突：只允許一個,PE,從共享存儲單元取內(nèi)容。,解決寫沖突：用樹作一種競賽機構(gòu)，確保僅有一個,PE,

15、在寫。,2023/8/61.2 并行計算模型:PRAM模型分類,2024/10/21,1.2,并行計算模型,:,PRAM,模型,優(yōu)點,適合并行算法表示和復雜性分析，易于使用，隱藏了并行機的通訊、同步等細節(jié),。,缺點,不適合,MIMD,并行機，忽略了,SM,的競爭、通訊延遲等因素,推廣,存儲競爭模型：,將,Memory,分成一些模塊，每個模塊一次可處理一個訪問，可以在模塊級處理存儲器的競爭。,延遲模型：,考慮了信息的產(chǎn)生到能夠使用之間的通信延遲,。,局部,PRAM,模型：,考慮了存儲帶寬，假定每個,PE,均有無限局存，而訪問全局存儲器是十分昂貴的。,分層存儲模型：,將存儲器視為分層的存儲模塊，每

16、個模塊由其大小及傳送時間表征。,異步,PRAM,模型,2023/8/61.2 并行計算模型:PRAM模型優(yōu)點,2024/10/21,1.2,并行計算模型,:,SIMD-IN,模型,描述,又稱,SIMD-DM,模型，分布式存儲，處理器通過互連網(wǎng)絡相連，用傳遞數(shù)據(jù)方式實現(xiàn)通訊，算法時間復雜性考慮計算和選路,(,時間,),，結(jié)構(gòu)圖如下：,常見模型,SIMD-LC,一維線性連接,SIMD-MC,網(wǎng)孔連接,SIMD-TC,樹形連接,SIMD-MT,樹網(wǎng)連接,SIMD-HC,超立方連接,SIMD-CCC,立方環(huán)連接,SIMD-SE,洗牌交換連接,2023/8/61.2 并行計算模型:SIMD-IN模型描,2024/10/21,1.2,并行計算模型,:,異步,APRAM,模型,描述,又稱分相（,Phase,）,PRAM,或,MIMD-SM,。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過,SM,進行通訊；處理器間依賴關系，需在并行程序中顯式地加入同步路障。,指令類型,(,1),全局讀,(2),全局寫,(3),局部操作,(4),同步,2023/8/61.2 并行