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 并行計(jì)算機(jī)體系結(jié)構(gòu) 并行計(jì)算機(jī)的分類(lèi) 并行計(jì)算機(jī)的互連方式 1.2 并行計(jì)算模型 PRAM模型 異步APRAM模型 BSP模型 LogP模型 1.3 并行算法的一般概念 并行算法的定義和分類(lèi) 并行算法的表示 并行算法的復(fù)雜度 并行算法的WT表示 加速比性能定律 并行算法的同步和通訊,2020/8/11,Y.Xu Copyright

2、USTC,1.1 并行計(jì)算機(jī)的體系結(jié)構(gòu): 并行計(jì)算機(jī)分類(lèi),Flynn分類(lèi)（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, 對(duì)稱多處理機(jī)) MPP (Massively Paralle

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

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

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

6、opyright USTC,1.1 并行計(jì)算機(jī)的體系結(jié)構(gòu): 互連方式,動(dòng)態(tài)互連網(wǎng)絡(luò)(非固定連接) (1)總線Bus (2)交叉開(kāi)關(guān)Crossbar Switcher：一種高帶寬網(wǎng)絡(luò) (3)多級(jí)互連網(wǎng)絡(luò)Multistage Interconnection Network 一種大型開(kāi)關(guān)網(wǎng)絡(luò),2020/8/11,Y.Xu Copyright USTC,主要內(nèi)容,1.1 并行計(jì)算機(jī)體系結(jié)構(gòu) 并行計(jì)算機(jī)的分類(lèi) 并行計(jì)算機(jī)的互連方式 1.2 并行計(jì)算模型 PRAM模型 SIMD-IN模型 異步APRAM模型 BSP模型 LogP模型 1.3 并行算法的一般概念 并行算法的定義和分類(lèi) 并行算法的表示 并行算

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

8、RAM-CRCW)：僅允許寫(xiě)入相同數(shù)據(jù) PPRAM-CRCW(Priority PRAM-CRCW)：僅允許優(yōu)先級(jí)最高的處理器寫(xiě)入 APRAM-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫(xiě)入 PRAM-CREW并發(fā)讀互斥寫(xiě) PRAM-EREW互斥讀互斥寫(xiě) 計(jì)算能力比較 PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW,2020/8/11,Y.Xu Copyright USTC,1.2 并行計(jì)算模型: PRAM模型,優(yōu)點(diǎn) 適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。 缺點(diǎn) 不適合M

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

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

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

12、andwidth,2020/8/11,Y.Xu Copyright USTC,1.2 并行計(jì)算模型: BSP模型,計(jì)算過(guò)程 由若干超級(jí)步組成， 每個(gè)超級(jí)步計(jì)算模式為右圖 優(yōu)缺點(diǎn) 強(qiáng)調(diào)了計(jì)算和通訊的分離， 提供了一個(gè)編程環(huán)境，易于 程序復(fù)雜性分析。但需要顯 式同步機(jī)制，限制至多h條 消息的傳遞等。,2020/8/11,Y.Xu Copyright USTC,1.2 并行計(jì)算模型: LogP模型,描述 由Culler(1993)年提出的，是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(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 并行計(jì)算模型: LogP模型,優(yōu)缺點(diǎn) 捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲(chǔ)、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。 BSP vs. LogP BSPLogP：BSP塊同步BSP子集同步BSP進(jìn)程對(duì)同步LogP BSP可以常數(shù)因子模擬LogP，LogP可以對(duì)數(shù)因子模擬BSP BSPLogP + Barriers Overhead BSP提供了更方便的

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

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

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

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

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