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,主要內容,1.1,并行計算機體系結構,并行計算機的分類,并行計算機的互連方式,1.2,并行計算模型,PRAM,模型,異步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定義和分類,相關性與可并行化,并行算法的表示,并行算法的復雜度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通訊,2023/8/6主要內容1.1 并行計算機體系結構,2024/10/21,1.1,并行計算機的體系結構,:,并行計算機分類,Flynn,分類（,1966,年）,(1),單指令流單數(shù)據(jù)流機,SISD,，即傳統(tǒng)的單處理機,(2),單指令流多數(shù)據(jù)流機,SIMD,(3),多指令流單數(shù)據(jù)流機,MISD,，實際中不存在的機器,(4),多指令流多數(shù)據(jù)流機,MIMD,并行機的結構模型,實際的機器體系結構,SIMD(Single Instruction 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 并行計算機的體系結構:并行計算機分,2024/10/21,SISD computer-Von Neumanns model,1.1,并行計算機的體系結構,:,并行計算機分類,SIMD computer,2023/8/6SISD computer-Von Neu,2024/10/21,Symmetric multiprocessor,MIMD-SM,1.1,并行計算機的體系結構,:,并行計算機分類,Massively parallel processor,MIMD-DM,2023/8/6Symmetric multiprocess,2024/10/21,Cluster of workstations,MIMD-DM,1.1,并行計算機的體系結構,:,并行計算機分類,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,定制網絡,LM,LM,LM,(c)MPP,物理,/,邏輯上多地址空間,P/C,P/C,P/C,定制網絡,LM,LM,LM,虛擬分布共享存儲,(DSM),(d)DSM(MPP/Cluster),邏輯上單一地址空間,結構模型,物理機模型,P/C,P/C,P/C,定制,/,標準網絡,LM,LM,LM,(e)Cluster/COW,物理,/,邏輯上多地址空間,1.1,并行計算機的體系結構,:,并行計算機分類,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,結構模型,物理機模型,1.1,并行計算機的體系結構,:,并行計算機分類,2023/8/6SMPMPPMPPWANLMDSMSM(h,2024/10/21,1.1,并行計算機的體系結構,:,互連方式,靜態(tài)互連網絡,(,固定連接,),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),網孔連接,MC(Mesh Connected),二維陣列,不帶環(huán)繞的,MC,，帶環(huán)繞的,MC,2023/8/61.1 并行計算機的體系結構:互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結構,:,互連方式,靜態(tài)互連網絡,(3),樹形連接,TC(Tree Connected),二叉樹，胖樹,2023/8/61.1 并行計算機的體系結構:互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結構,:,互連方式,靜態(tài)互連網絡,(4),樹網連接,MT(Mesh of tree),2023/8/61.1 并行計算機的體系結構:互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結構,:,互連方式,靜態(tài)互連網絡,(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 并行計算機的體系結構:互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結構,:,互連方式,靜態(tài)互連網絡,:,嵌入,將網絡中的各節(jié)點映射到另一個網絡中去,用膨脹（,Dilation,）系數(shù)來描述嵌入的質量，它是指被嵌入網絡中的一條鏈路在所要嵌入的網絡中對應所需的最大鏈路數(shù),如果該系數(shù)為,1,，則稱為完美嵌入。,環(huán)網可完美嵌入到,2-D,環(huán)繞網中,超立方網可完美嵌入到,2,D,環(huán)繞網中,2023/8/61.1 并行計算機的體系結構:互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結構,:,互連方式,靜態(tài)互連網絡,:,嵌入,Ring onto 2-D torus,Hypercube onto 2-D torus,2023/8/61.1 并行計算機的體系結構:互連方式靜態(tài),2024/10/21,1.1,并行計算機的體系結構,:,互連方式,動態(tài)互連網絡,(,非固定連接,),(1),總線,Bus,(2),交叉開關,Crossbar Switcher,：一種高帶寬網絡,(3),多級互連網絡,Multistage Interconnection Network,一種大型開關網絡,2023/8/61.1 并行計算機的體系結構:互連方式動態(tài),2024/10/21,主要內容,1.1,并行計算機體系結構,并行計算機的分類,并行計算機的互連方式,1.2,并行計算模型,PRAM,模型,異步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定義和分類,相關性與可并行化,并行算法的表示,并行算法的復雜度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通訊,2023/8/6主要內容1.1 并行計算機體系結構,2024/10/21,1.2,并行計算模型,:,PRAM,模型,描述,由,Fortune,和,Wyllie1978,年提出，稱為并行隨機存取機器,PRAM,，又稱,SIMD-SM,模型。有一個集中的共享存儲器和一個指令控制器，通過,SM,的,R/W,交換數(shù)據(jù)，隱式同步計算。,假設,SM,的容量無限,有限,/,無限個功能相同的處理器,本地指令和,SM,的,R/W,操作都取單位時間,結構圖,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-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,曾經使用二叉樹方法來解決沖突問題,解決讀沖突：只允許一個,PE,從共享存儲單元取內容。,解決寫沖突：用樹作一種競賽機構，確保僅有一個,PE,在寫。,2023/8/61.2 并行計算模型:PRAM模型分類,2024/10/21,1.2,并行計算模型,:,PRAM,模型,優(yōu)點,適合并行算法表示和復雜性分析，易于使用，隱藏了并行機的通訊、同步等細節(jié),。,缺點,不適合,MIMD,并行機，忽略了,SM,的競爭、通訊延遲等因素,推廣,存儲競爭模型：,將,Memory,分成一些模塊，每個模塊一次可處理一個訪問，可以在模塊級處理存儲器的競爭。,延遲模型：,考慮了信息的產生到能夠使用之間的通信延遲,。,局部,PRAM,模型：,考慮了存儲帶寬，假定每個,PE,均有無限局存，而訪問全局存儲器是十分昂貴的。,分層存儲模型：,將存儲器視為分層的存儲模塊，每個模塊由其大小及傳送時間表征。,異步,PRAM,模型,2023/8/61.2 并行計算模型:PRAM模型優(yōu)點,2024/10/21,1.2,并行計算模型,:,SIMD-IN,模型,描述,又稱,SIMD-DM,模型，分布式存儲，處理器通過互連網絡相連，用傳遞數(shù)據(jù)方式實現(xiàn)通訊，算法時間復雜性考慮計算和選路,(,時間,),，結構圖如下：,常見模型,SIMD-LC,一維線性連接,SIMD-MC,網孔連接,SIMD-TC,樹形連接,SIMD-MT,樹網連接,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 并行