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 bullet,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,并行計(jì)算機(jī)體系結(jié)構(gòu),并行計(jì)算機(jī)的分類,并行計(jì)算機(jī)的互連方式,1.2,并行計(jì)算模型,PRAM,模型,異步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定義和分類,相關(guān)性與可并行化,并行算法的表示,并行算法的復(fù)雜度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通訊,2023/8/6主要內(nèi)容1.1 并行計(jì)算機(jī)體系結(jié)構(gòu),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,并行計(jì)算機(jī)分類,Flynn,分類（,1966,年）,(1),單指令流單數(shù)據(jù)流機(jī),SISD,，即傳統(tǒng)的單處理機(jī),(2),單指令流多數(shù)據(jù)流機(jī),SIMD,(3),多指令流單數(shù)據(jù)流機(jī),MISD,，實(shí)際中不存在的機(jī)器,(4),多指令流多數(shù)據(jù)流機(jī),MIMD,并行機(jī)的結(jié)構(gòu)模型,實(shí)際的機(jī)器體系結(jié)構(gòu),SIMD(Single Instruction Multiple Data,單指令流多數(shù)據(jù)流機(jī),),PVP (Parallel Vector Processor,并行向量機(jī),),SMP (Symmetric Multiprocessor,對稱多處理機(jī),),MPP (Massively Parallel Processor,大規(guī)模并行處理機(jī),),COW(Cluster of Workstation,工作站機(jī)群,),DSM (Distributed Shared Memory,分布共享存儲(chǔ)多處理機(jī),),注：,SIMD,是專用并行機(jī)，后,5,種屬于,MIMD,并行機(jī)。,2023/8/61.1 并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分,2024/10/21,SISD computer-Von Neumanns model,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,并行計(jì)算機(jī)分類,SIMD computer,2023/8/6SISD computer-Von Neu,2024/10/21,Symmetric multiprocessor,MIMD-SM,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,并行計(jì)算機(jī)分類,Massively parallel processor,MIMD-DM,2023/8/6Symmetric multiprocess,2024/10/21,Cluster of workstations,MIMD-DM,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,并行計(jì)算機(jī)分類,2023/8/6Cluster of workstation,2024/10/21,VP,VP,VP,交叉開關(guān),SM,(a)PVP,P/C,P/C,P/C,總線或交叉開關(guān),SM,(b)SMP,物理上單一地址空間,P/C,P/C,P/C,定制網(wǎng)絡(luò),LM,LM,LM,(c)MPP,物理,/,邏輯上多地址空間,P/C,P/C,P/C,定制網(wǎng)絡(luò),LM,LM,LM,虛擬分布共享存儲(chǔ),(DSM),(d)DSM(MPP/Cluster),邏輯上單一地址空間,結(jié)構(gòu)模型,物理機(jī)模型,P/C,P/C,P/C,定制,/,標(biāo)準(zhǔn)網(wǎng)絡(luò),LM,LM,LM,(e)Cluster/COW,物理,/,邏輯上多地址空間,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,并行計(jì)算機(jī)分類,2023/8/6VPVPVP交叉開關(guān)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)模型,物理機(jī)模型,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,并行計(jì)算機(jī)分類,2023/8/6SMPMPPMPPWANLMDSMSM(h,2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡(luò),(,固定連接,),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 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡(luò),(3),樹形連接,TC(Tree Connected),二叉樹，胖樹,2023/8/61.1 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡(luò),(4),樹網(wǎng)連接,MT(Mesh of tree),2023/8/61.1 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡(luò),(5),金字塔連接,(Pyramid),(6),超立方連接,HC(Hypercube Connected),3,立方，,4,立方,(7),立方環(huán)連接,CCC(Cube Connected-Cycles),(8),洗牌交換連接,SE(Shuffle Exchange),(9),蝶形連接,(Butterfly Connected),2023/8/61.1 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡(luò),:,嵌入,將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個(gè)網(wǎng)絡(luò)中去,用膨脹（,Dilation,）系數(shù)來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡(luò)中的一條鏈路在所要嵌入的網(wǎng)絡(luò)中對應(yī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 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,靜態(tài)互連網(wǎng)絡(luò),:,嵌入,Ring onto 2-D torus,Hypercube onto 2-D torus,2023/8/61.1 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài),2024/10/21,1.1,并行計(jì)算機(jī)的體系結(jié)構(gòu),:,互連方式,動(dòng)態(tài)互連網(wǎng)絡(luò),(,非固定連接,),(1),總線,Bus,(2),交叉開關(guān),Crossbar Switcher,：一種高帶寬網(wǎng)絡(luò),(3),多級互連網(wǎng)絡(luò),Multistage Interconnection Network,一種大型開關(guān)網(wǎng)絡(luò),2023/8/61.1 并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式動(dòng)態(tài),2024/10/21,主要內(nèi)容,1.1,并行計(jì)算機(jī)體系結(jié)構(gòu),并行計(jì)算機(jī)的分類,并行計(jì)算機(jī)的互連方式,1.2,并行計(jì)算模型,PRAM,模型,異步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定義和分類,相關(guān)性與可并行化,并行算法的表示,并行算法的復(fù)雜度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通訊,2023/8/6主要內(nèi)容1.1 并行計(jì)算機(jī)體系結(jié)構(gòu),2024/10/21,1.2,并行計(jì)算模型,:,PRAM,模型,描述,由,Fortune,和,Wyllie1978,年提出，稱為并行隨機(jī)存取機(jī)器,PRAM,，又稱,SIMD-SM,模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過,SM,的,R/W,交換數(shù)據(jù)，隱式同步計(jì)算。,假設(shè),SM,的容量無限,有限,/,無限個(gè)功能相同的處理器,本地指令和,SM,的,R/W,操作都取單位時(shí)間,結(jié)構(gòu)圖,Control Unit,Interconnection Network,P,LM,P,LM,P,LM,P,LM,Shared Memory,2023/8/61.2 并行計(jì)算模型:PRAM模型描述Co,2024/10/21,1.2,并行計(jì)算模型,:,PRAM,模型,分類,PRAM-CRCW,并發(fā)讀并發(fā)寫,CPRAM-CRCW(Common PRAM-CRCW),：僅允許寫入相同數(shù)據(jù),PPRAM-CRCW(Priority PRAM-CRCW),：僅允許優(yōu)先級最高的處理器寫入,APRAM-CRCW(Arbitrary PRAM-CRCW),：允許任意處理器自由寫入,PRAM-CREW,并發(fā)讀互斥寫,PRAM-EREW,互斥讀互斥寫,計(jì)算能力比較,PRAM-CRCW,是最強(qiáng)的計(jì)算模型，,PRAM-EREW,可,logp,倍模擬,PRAM-CREW,和,PRAM-CRCW,。令,Tm,是在模型,M,上的運(yùn)行時(shí)間，則：,1979,年，,Eckstain,曾經(jīng)使用二叉樹方法來解決沖突問題,解決讀沖突：只允許一個(gè),PE,從共享存儲(chǔ)單元取內(nèi)容。,解決寫沖突：用樹作一種競賽機(jī)構(gòu)，確保僅有一個(gè),PE,在寫。,2023/8/61.2 并行計(jì)算模型:PRAM模型分類,2024/10/21,1.2,并行計(jì)算模型,:,PRAM,模型,優(yōu)點(diǎn),適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié),。,缺點(diǎn),不適合,MIMD,并行機(jī)，忽略了,SM,的競爭、通訊延遲等因素,推廣,存儲(chǔ)競爭模型：,將,Memory,分成一些模塊，每個(gè)模塊一次可處理一個(gè)訪問，可以在模塊級處理存儲(chǔ)器的競爭。,延遲模型：,考慮了信息的產(chǎn)生到能夠使用之間的通信延遲,。,局部,PRAM,模型：,考慮了存儲(chǔ)帶寬，假定每個(gè),PE,均有無限局存，而訪問全局存儲(chǔ)器是十分昂貴的。,分層存儲(chǔ)模型：,將存儲(chǔ)器視為分層的存儲(chǔ)模塊，每個(gè)模塊由其大小及傳送時(shí)間表征。,異步,PRAM,模型,2023/8/61.2 并行計(jì)算模型:PRAM模型優(yōu)點(diǎn),2024/10/21,1.2,并行計(jì)算模型,:,SIMD-IN,模型,描述,又稱,SIMD-DM,模型，分布式存儲(chǔ)，處理器通過互連網(wǎng)絡(luò)相連，用傳遞數(shù)據(jù)方式實(shí)現(xiàn)通訊，算法時(shí)間復(fù)雜性考慮計(jì)算和選路,(,時(shí)間,),，結(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 并行計(jì)算模型:SIMD-IN模型描,2024/10/21,1.2,并行計(jì)算模型,:,異步,APRAM,模型,描述,又稱分相（,Phase,）,PRAM,或,MIMD-SM,。每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序；無全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過,SM,進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。,指令類型,(,1),全局讀,(2),全局寫,(3),局部操作,(4),同步,2023/8/61.2 并行