MPI程序設(shè)計ch1.ppt

1、Y.Xu Copyright USTC,2020/8/11,Parallel Algorithms Chapter 1 Foundation of Parallel Algorithms,2020/8/11,Y.Xu Copyright USTC,主要內(nèi)容,1.1 并行計算機體系結(jié)構(gòu) 并行計算機的分類 并行計算機的互連方式 1.2 并行計算模型 PRAM模型 異步APRAM模型 BSP模型 LogP模型 1.3 并行算法的一般概念 并行算法的定義和分類 并行算法的表示 并行算法的復(fù)雜度 并行算法的WT表示 加速比性能定律 并行算法的同步和通訊,2020/8/11,Y.Xu Copyright

2、USTC,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 Instruction Multiple Data, 單指令流多數(shù)據(jù)流機) PVP (Parallel Vector Processor, 并行向量機) SMP (Symmetric Multiprocessor, 對稱多處理機) MPP (Massively Paralle

3、l Processor, 大規(guī)模并行處理機) COW (Cluster of Workstation, 工作站機群) DSM (Distributed Shared Memory, 分布共享存儲多處理機) 注：SIMD是專用并行機，后5種屬于MIMD并行機。,2020/8/11,Y.Xu Copyright USTC,結(jié)構(gòu)模型物理機模型,1.1 并行計算機的體系結(jié)構(gòu): 并行計算機分類,2020/8/11,Y.Xu Copyright USTC,結(jié)構(gòu)模型物理機模型,1.1 并行計算機的體系結(jié)構(gòu): 并行計算機分類,2020/8/11,Y.Xu Copyright USTC,1.1 并行計算機的體系

4、結(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,2020/8/11,Y.Xu Copyright USTC,1.1 并行計算機的體系結(jié)構(gòu): 互連方式,靜態(tài)互連網(wǎng)絡(luò) (3)樹形連接TC(Tree Connected) 二叉樹， 胖樹,2020/8/11,Y

5、.Xu Copyright USTC,1.1 并行計算機的體系結(jié)構(gòu): 互連方式,靜態(tài)互連網(wǎng)絡(luò) (4)樹網(wǎng)連接MT(Mesh of tree),2020/8/11,Y.Xu Copyright USTC,1.1 并行計算機的體系結(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),2020/8/11,Y.Xu C

6、opyright USTC,1.1 并行計算機的體系結(jié)構(gòu): 互連方式,動態(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ò),2020/8/11,Y.Xu Copyright USTC,主要內(nèi)容,1.1 并行計算機體系結(jié)構(gòu) 并行計算機的分類 并行計算機的互連方式 1.2 并行計算模型 PRAM模型 SIMD-IN模型 異步APRAM模型 BSP模型 LogP模型 1.3 并行算法的一般概念 并行算法的定義和分類 并行算法的表示 并行算

7、法的復(fù)雜度 并行算法的WT表示 加速比性能定律 并行算法的同步和通訊,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: PRAM模型,描述 由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計算。 假設(shè) SM的容量無限 有限/無限個功能相同的處理器 本地指令和SM的R/W操作都取單位時間 結(jié)構(gòu)圖,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: PRAM模型,分類 PRAM-CRCW并發(fā)讀并發(fā)寫 CPRAM-CRCW(Common P

8、RAM-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,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: PRAM模型,優(yōu)點 適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機的通訊、同步等細節(jié)。 缺點 不適合M

9、IMD并行機，忽略了SM的競爭、通訊延遲等因素,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: SIMD-IN模型,描述 又稱SIMD-DM模型，分布式存儲，處理器通過互連網(wǎng)絡(luò)相連，用傳遞數(shù)據(jù)方式實現(xiàn)通訊，算法時間復(fù)雜性考慮計算和選路(時間)，結(jié)構(gòu)圖如下： 常見模型 SIMD-LC 一維線性連接 SIMD-MC 網(wǎng)孔連接 SIMD-TC 樹形連接 SIMD-MT 樹網(wǎng)連接 SIMD-HC 超立方連接 SIMD-CCC 立方環(huán)連接 SIMD-SE 洗牌交換連接,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: 異步APRAM模

10、型,描述 又稱分相（Phase）PRAM或MIMD-SM。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。 指令類型 (1)全局讀 (2)全局寫 (3)局部操作 (4)同步,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: 異步APRAM模型,計算過程 由同步障分開的全局相組成,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: 異步APRAM模型,計算時間 設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加

11、而增加；同步路障時間為B=B(p)非降函數(shù)。 令 為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計算時間為 優(yōu)缺點 易編程和分析算法的復(fù)雜度，其上并行算法比較有限，不適合MIMD-DM模型。,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: BSP模型,描述 由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。 模型參數(shù) p：處理器數(shù)(帶有存儲器) L：同步障時間(Barrier synchronization time) g：帶寬因子(time steps/packet)=1/b

12、andwidth,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: BSP模型,計算過程 由若干超級步組成， 每個超級步計算模式為右圖 優(yōu)缺點 強調(diào)了計算和通訊的分離， 提供了一個編程環(huán)境，易于 程序復(fù)雜性分析。但需要顯 式同步機制，限制至多h條 消息的傳遞等。,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: LogP模型,描述 由Culler(1993)年提出的，是一種分布存儲的、點到點通訊的多處理機模型，其中通訊由一組參數(shù)描述，實行隱式同步。 模型參數(shù) L：network latency o：communication

13、overhead g：gap=1/bandwidth P：#processors 注：L和g反映了通訊網(wǎng)絡(luò)的容量,2020/8/11,Y.Xu Copyright USTC,1.2 并行計算模型: LogP模型,優(yōu)缺點 捕捉了MPC的通訊瓶頸，隱藏了并行機的網(wǎng)絡(luò)拓撲、路由、協(xié)議，可以應(yīng)用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進行算法描述、設(shè)計和分析。 BSP vs. LogP BSPLogP：BSP塊同步BSP子集同步BSP進程對同步LogP BSP可以常數(shù)因子模擬LogP，LogP可以對數(shù)因子模擬BSP BSPLogP + Barriers Overhead BSP提供了更方便的

14、程設(shè)環(huán)境，LogP更好地利用了機器資源 BSP似乎更簡單、方便和符合結(jié)構(gòu)化編程,2020/8/11,Y.Xu Copyright USTC,主要內(nèi)容,1.1 并行計算機體系結(jié)構(gòu) 并行計算機的分類 并行計算機的互連方式 1.2 并行計算模型 PRAM模型 SIMD-IN模型 異步APRAM模型 BSP模型 LogP模型 1.3 并行算法的一般概念 并行算法的定義和分類 并行算法的表示 并行算法的復(fù)雜度 并行算法的WT表示 加速比性能定律 并行算法的同步和通訊,2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 定義和分類,并行算法 一組可同時執(zhí)行且可互相協(xié)作

15、的諸進程的集合。 分類 VLSI并行算法：在VLSI計算模型上開發(fā)的并行算法,2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 并行算法的表示,par-do語句 for i=1 to n par-do 或 for i=1 to n do in parallel . . . . . . end for end for for all語句 for all Pi, where 0ik do . . . end for,2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 并行算法的復(fù)雜度,串行算法的度量 一些記號 平均情形復(fù)

16、雜度、最壞情形復(fù)雜度,2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 并行算法的復(fù)雜度,并行算法復(fù)雜性的度量 運行時間t(n)：計算時間tc和選路(路由)時間tr 處理器數(shù)目p(n) 成本c(n)：c(n)=t(n)p(n) 成本最優(yōu)性：若c(n)等于在最壞情形下串行算法所需要的時間，則并行算法是成本最優(yōu)的。 加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)為求解問題的最快的串行算法在最壞情形下所需的運行時間，tp(n)為求解同一問題的并行算法在最壞情形下的運行時間。 注：(1)加速比Sp(n)反映算法的并行性對運行時間的改進程度。

17、 (2)若Sp(n)=p(n)，則達到線性加速；若Sp(n)p(n)，則為超線性加速(一般出現(xiàn)在某些特殊的應(yīng)用中，如并行搜索等)。 并行效率Ep(n)：Ep(n)=Sp(n)/p(n)， 0Ep(n)=1 注：反映了并行系統(tǒng)中處理器的利用程度。 工作量(或運算量) W(n)：并行算法所執(zhí)行的總操作步數(shù)。(與處理器的數(shù)目無關(guān)),2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 并行算法的WT表示,Brent定理 令W(n)是一并行算法A在運行時間T(n)內(nèi)執(zhí)行的運算量，則A使用p臺處理器可在時間t(n)=O(W(n)/p +T(n)內(nèi)執(zhí)行完成。 證明：設(shè)時

18、刻 并行算法A做的工作量為Wi(即在(i-1, i時段內(nèi)的工作量) =用p臺處理器去完成并行算法A的第i時刻工作量，需時間 =用p臺處理器模擬并行算法A的總時間為,2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 并行算法的WT表示,Brent定理 注： (1)揭示了并行算法工作量和運行時間的關(guān)系； (2)提供了并行算法的WT(Work-Time)表示方法； (3)告訴我們：設(shè)計并行算法時應(yīng)盡可能將每個時間步的工作量均勻地分攤給p臺處理器，使各處理器處于活躍狀態(tài)。,2020/8/11,Y.Xu Copyright USTC,1.3 并行算法的一般概念: 加速比性能定律,Amdahls Law: Base on Fixed Problem Size 適用于實時應(yīng)用問題。當(dāng)問題的計算負載或規(guī)模固定時，我們必須通過增加處理器數(shù)目來降低計算時間； 設(shè) f 是算法中不能并行的串行部