并行計(jì)算模型課件

2022/12/16

ParallelAlgorithms

Chapter

1

FoundationofParallelAlgorithmsSpring,

20182022/12/12

ParallelAlgorithms2022/12/16主要內(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表示加速比性能定律并行算法的同步和通訊2022/12/12主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2022/12/161.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(SingleInstructionMultipleData,單指令流多數(shù)據(jù)流機(jī))

－PVP(ParallelVectorProcessor,并行向量機(jī))

－SMP(SymmetricMultiprocessor,對稱多處理機(jī))

－MPP(MassivelyParallelProcessor,大規(guī)模并行處理機(jī))

－COW(ClusterofWorkstation,工作站機(jī)群)

－DSM(DistributedSharedMemory,分布共享存儲多處理機(jī))

注：SIMD是專用并行機(jī)，后5種屬于MIMD并行機(jī)。2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算2022/12/16SISDcomputer-VonNeumann'smodel1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類SIMDcomputer2022/12/12SISDcomputer-VonN2022/12/16Symmetricmultiprocessor–MIMD-SM1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類Massivelyparallelprocessor–MIMD-DM2022/12/12Symmetricmultiproce2022/12/16Clusterofworkstations–MIMD-DM1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2022/12/12Clusterofworkstati2022/12/16VPVPVP…交叉開關(guān)SM(a)PVPP/CP/CP/C…總線或交叉開關(guān)SM(b)SMP,物理上單一地址空間P/CP/CP/C…定制網(wǎng)絡(luò)LMLMLM(c)MPP,物理/邏輯上多地址空間P/CP/CP/C…定制網(wǎng)絡(luò)LMLMLM虛擬分布共享存儲(DSM)(d)DSM(MPP/Cluster),邏輯上單一地址空間結(jié)構(gòu)模型－物理機(jī)模型P/CP/CP/C…定制/標(biāo)準(zhǔn)網(wǎng)絡(luò)LMLMLM(e)Cluster/COW,物理/邏輯上多地址空間1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2022/12/12VPVPVP…交叉開關(guān)SM(a)PVP2022/12/16SMPMPPMPP…WANLMDSMSM(h)Grid(ClusterofClusters)SMPSMPSMP…SAN/LANSMSMSMMPPMPPMPP…SAN/LANDSMDSMDSM(f)SMP-Cluster(g)DSM-Cluster結(jié)構(gòu)模型－物理機(jī)模型1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2022/12/12SMPMPPMPP…WANLMDSMSM2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)(固定連接)

connectedgraphvertices=processingnodesedges=communicationlinks(1)一維線性連接LA(1-DLinearArray)—一維陣列不帶環(huán)繞的1-DLA，帶環(huán)繞的1-DLA(2)網(wǎng)孔連接MC(MeshConnected)—二維陣列不帶環(huán)繞的MC，帶環(huán)繞的MC2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)

(3)樹形連接TC(TreeConnected)二叉樹，胖樹2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)

(4)樹網(wǎng)連接MT(Meshoftree)

2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)(5)金字塔連接(Pyramid)(6)超立方連接HC(HypercubeConnected)3－立方，4－立方(7)立方環(huán)連接CCC(CubeConnected-Cycles)(8)洗牌交換連接SE(ShuffleExchange)(9)蝶形連接(ButterflyConnected)2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò):嵌入將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個網(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)中2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò):嵌入Ringonto2-Dtorus

Hypercubeonto2-Dtorus2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式動態(tài)互連網(wǎng)絡(luò)(非固定連接)(1)總線Bus(2)交叉開關(guān)CrossbarSwitcher：一種高帶寬網(wǎng)絡(luò)(3)多級互連網(wǎng)絡(luò)MultistageInterconnectionNetwork一種大型開關(guān)網(wǎng)絡(luò)

2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/16主要內(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表示加速比性能定律并行算法的同步和通訊2022/12/12主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2022/12/161.2并行計(jì)算模型:PRAM模型描述由Fortune和Wyllie1978年提出，稱為并行隨機(jī)存取機(jī)器PRAM，又稱SIMD-SM模型。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。假設(shè)SM的容量無限有限/無限個功能相同的處理器本地指令和SM的R/W操作都取單位時間結(jié)構(gòu)圖ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory2022/12/121.2并行計(jì)算模型:PRAM模型描述2022/12/161.2并行計(jì)算模型:PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計(jì)算能力比較PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW。令Tm是在模型M上的運(yùn)行時間，則：1979年，Eckstain曾經(jīng)使用二叉樹方法來解決沖突問題解決讀沖突：只允許一個PE從共享存儲單元取內(nèi)容。解決寫沖突：用樹作一種競賽機(jī)構(gòu)，確保僅有一個PE在寫。2022/12/121.2并行計(jì)算模型:PRAM模型分類2022/12/161.2并行計(jì)算模型:PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競爭、通訊延遲等因素推廣存儲競爭模型：將Memory分成一些模塊，每個模塊一次可處理一個訪問，可以在模塊級處理存儲器的競爭。延遲模型：考慮了信息的產(chǎn)生到能夠使用之間的通信延遲

。局部PRAM模型：考慮了存儲帶寬，假定每個PE均有無限局存，而訪問全局存儲器是十分昂貴的。

分層存儲模型：將存儲器視為分層的存儲模塊，每個模塊由其大小及傳送時間表征。異步PRAM模型2022/12/121.2并行計(jì)算模型:PRAM模型優(yōu)點(diǎn)2022/12/161.2并行計(jì)算模型:SIMD-IN模型描述又稱SIMD-DM模型，分布式存儲，處理器通過互連網(wǎng)絡(luò)相連，用傳遞數(shù)據(jù)方式實(shí)現(xiàn)通訊，算法時間復(fù)雜性考慮計(jì)算和選路(時間)，結(jié)構(gòu)圖如下：

常見模型SIMD-LC一維線性連接SIMD-MC網(wǎng)孔連接SIMD-TC樹形連接SIMD-MT樹網(wǎng)連接SIMD-HC超立方連接SIMD-CCC立方環(huán)連接SIMD-SE洗牌交換連接2022/12/121.2并行計(jì)算模型:SIMD-IN模2022/12/161.2并行計(jì)算模型:異步APRAM模型描述又稱分相（Phase）PRAM或MIMD-SM。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(2)全局寫(3)局部操作(4)同步

2022/12/121.2并行計(jì)算模型:異步APRAM模2022/12/161.2并行計(jì)算模型:異步APRAM模型計(jì)算過程由同步障分開的全局相組成

，*號表示局部操作。2022/12/121.2并行計(jì)算模型:異步APRAM模2022/12/161.2并行計(jì)算模型:異步APRAM模型計(jì)算時間

設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加而增加；同步路障時間為B=B(p)非降函數(shù)。令為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計(jì)算時間為

優(yōu)缺點(diǎn)

易編程和分析算法的復(fù)雜度，其上并行算法比較有限，不適合MIMD-DM模型。

2022/12/121.2并行計(jì)算模型:異步APRAM模2022/12/161.2并行計(jì)算模型:BSP模型描述由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。

模型參數(shù)p：處理器數(shù)(帶有存儲器)L：同步障時間(Barriersynchronizationtime)g：選路器吞吐率（帶寬因子）發(fā)送一個消息所用的時間，帶寬因子(timesteps/packet)=1/bandwidth2022/12/121.2并行計(jì)算模型:BSP模型描述2022/12/161.2并行計(jì)算模型:BSP模型計(jì)算過程由若干超級步組成，每個超級步計(jì)算模式為右圖優(yōu)缺點(diǎn)

強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條消息的傳遞等。2022/12/121.2并行計(jì)算模型:BSP模型計(jì)算過2022/12/161.2并行計(jì)算模型:LogP模型描述由Culler(1993)年提出的，是一種分布存儲的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L(Latency)：通迅延遲o(overhead)：通訊額外開銷g(gap)：g=1/bandwidth,處理器可連續(xù)進(jìn)行消息發(fā)送或接收的最小時間間隔P：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量

2022/12/121.2并行計(jì)算模型:LogP模型描述2022/12/161.2并行計(jì)算模型:LogP模型優(yōu)缺點(diǎn)捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)洹⒙酚?、協(xié)議，可以應(yīng)用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。BSPvs.LogPBSPLogP：BSP塊同步BSP子集同步BSP進(jìn)程對同步＝LogPBSP可以常數(shù)因子模擬LogP，LogP可以對數(shù)因子模擬BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程設(shè)環(huán)境，LogP更好地利用了機(jī)器資源BSP似乎更簡單、方便和符合結(jié)構(gòu)化編程

2022/12/121.2并行計(jì)算模型:LogP模型優(yōu)缺2022/12/161.2并行計(jì)算模型:各種計(jì)算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結(jié)構(gòu)SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計(jì)算模式同步異步異步異步異步同步方式自動同步路障同步路障同步隱式同步路障同步模型參數(shù)單位時間步d,讀/寫時間B,同步時間p,處理器數(shù)g,帶寬因子l,同步間隔L,通信延遲o,額外開銷g,帶寬因子P,處理器數(shù)l,信包長度s,發(fā)送建立時間h,通信延遲計(jì)算粒度細(xì)粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫共享變量讀/寫共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間2022/12/121.2并行計(jì)算模型:各種計(jì)算模型比較2022/12/16主要內(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表示加速比性能定律并行算法的同步和通訊2022/12/12主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2022/12/161.3并行算法的一般概念:定義和分類并行算法

一組可同時執(zhí)行且可互相協(xié)作的諸進(jìn)程的集合。分類

VLSI并行算法：在VLSI計(jì)算模型上開發(fā)的并行算法

2022/12/121.3并行算法的一般概念:定義和分類2022/12/161.3并行算法的一般概念:并行算法的表示par-do語句

fori=1tonpar-do

或fori=1tondoinparallel......endforendforforall語句

forallPi,where0≤i≤kdo...endfor2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的復(fù)雜度串行算法的度量一些記號平均情形復(fù)雜度、最壞情形復(fù)雜度2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的復(fù)雜度并行算法復(fù)雜性的度量運(yùn)行時間t(n)：計(jì)算時間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)為求解問題的最快的串行算法在最壞情形下所需的運(yùn)行時間，tp(n)為求解同一問題的并行算法在最壞情形下的運(yùn)行時間。注：(1)加速比Sp(n)反映算法的并行性對運(yùn)行時間的改進(jìn)程度。

(2)若Sp(n)=p(n)，則達(dá)到線性加速；若Sp(n)>p(n)，則為超線性加速(一般出現(xiàn)在某些特殊的應(yīng)用中，如并行搜索等)。并行效率Ep(n)：Ep(n)=Sp(n)/p(n)，0<Ep(n)<=1注：反映了并行系統(tǒng)中處理器的利用程度。工作量(或運(yùn)算量)W(n)：并行算法所執(zhí)行的總操作步數(shù)。(與處理器的數(shù)目無關(guān))2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示Brent定理(1974JACM)

令W(n)是一并行算法A在運(yùn)行時間T(n)內(nèi)執(zhí)行的運(yùn)算量，則A使用p臺處理器可在時間t(n)=O(W(n)/p+T(n))內(nèi)執(zhí)行完成。證明：設(shè)時刻并行算法A做的工作量為Wi(即在(i-1,i]時段內(nèi)的工作量)==>用p臺處理器去完成并行算法A的第i時刻工作量，需時間

==>用p臺處理器模擬并行算法A的總時間為2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示Brent定理注：(1)揭示了并行算法工作量和運(yùn)行時間的關(guān)系；

(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴我們：設(shè)計(jì)并行算法時應(yīng)盡可能將每個時間步的工作量均勻地分?jǐn)偨op臺處理器，使各處理器處于活躍狀態(tài)。2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示例1令n=2k(k>=0)，求n個數(shù)和的并行算法。算法運(yùn)行時間：t(n)=O(logn)總運(yùn)算量:由Brent定理知:t(n)=O(n/p+logn)

2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:加速比性能定律Amdahl’sLaw:BaseonFixedProblemSize適用于實(shí)時應(yīng)用問題。當(dāng)問題的計(jì)算負(fù)載或規(guī)模固定時，我們必須通過增加處理器數(shù)目來降低計(jì)算時間；設(shè)f是算法中不能并行的串行部分比例，Ws和Wp分別是串行和并行部分的工作量，則總工作量W=fW+(1-f)W=Ws+Wp；Amdahl’slaw表明：加速比受到算法中串行工作量的限制。公式推導(dǎo)2022/12/121.3并行算法的一般概念:加速比性能2022/12/161.3并行算法的一般概念:加速比性能定律Gustafson’sLaw:BaseonFixedExecutionTime適用于要求精度高的應(yīng)用，通過加大計(jì)算量來提高計(jì)算精度。Gustafson’sLaw表明：隨著處理器數(shù)目的增加，串行執(zhí)行部分f不再是并行算法的瓶頸。放大問題工作量或規(guī)模的加速公式推導(dǎo)：

與p成線性關(guān)系。2022/12/121.3并行算法的一般概念:加速比性能2022/12/161.3并行算法的一般概念:加速比性能定律Sun&Ni’sLaw:BaseonMemoryBounding充分利用存儲空間等計(jì)算資源，盡量增大問題規(guī)模以產(chǎn)生更好/更精確的解。是Amdahl定律和Gustafson定律的推廣。公式推導(dǎo)：設(shè)單機(jī)上的存儲器容量為M，其工作負(fù)載W=fW+(1-f)W當(dāng)并行系統(tǒng)有p個結(jié)點(diǎn)時，存儲容量擴(kuò)大了pM，用G(p)表示系統(tǒng)的存儲容量增加p倍時工作負(fù)載的增加量。則存儲容量擴(kuò)大后的工作負(fù)載為W=fW+(1-f)G(p)W，所以，存儲受限的加速為特別地：當(dāng)G(p)=1時，為Amdahl定律；當(dāng)G(p)=p時，為Gustafson定律；2022/12/121.3并行算法的一般概念:加速比性能2022/12/161.3并行算法的一般概念:并行算法的同步同步概念同步是在時間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待，確保各進(jìn)程的正常順序和對共享可寫數(shù)據(jù)的正確訪問；可用軟件、硬件和固件的辦法來實(shí)現(xiàn)。同步語句示例算法1.3APRAM上的求和算法輸入：A=(a0,…,an-1),處理器數(shù)p

輸出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendfor算法的時間復(fù)雜度：O(n/p+p)

2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的同步2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的通訊通訊共享存儲多處理器使用：

globalread(X,Y)//將SM中的X讀入LM中的Yglobalwrite(U,V)//將LM中的U寫入SM中的V分布存儲多計(jì)算機(jī)使用：send(X,i)//處理器P發(fā)送X給處理器Pireceive(Y,j)//處理器P等待從Pj接收數(shù)據(jù)并存入LM中的Y通訊語句示例算法1.5分布存儲多計(jì)算機(jī)上矩陣向量乘法,通訊鏈為環(huán)

輸入：處理器數(shù)p,A按列劃分為p個B=Ai=A[1..n,(i-1)r+1..ir],x劃分為w=xi=x[(i-1)r+1..ir],r=n/p,i=1~p

輸出：P1保存乘積AX

Begin(1)Computez=Bw(2)ifi=1theny=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的通訊計(jì)算過程圖示2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的通訊算法的復(fù)雜度2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的通訊2022/12/121.3并行算法的一般概念:并行算法的2022/12/16

EndofChapter1

2022/12/12

EndofChapter1

2022/12/16

ParallelAlgorithms

Chapter

1

FoundationofParallelAlgorithmsSpring,

20182022/12/12

ParallelAlgorithms2022/12/16主要內(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表示加速比性能定律并行算法的同步和通訊2022/12/12主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2022/12/161.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(SingleInstructionMultipleData,單指令流多數(shù)據(jù)流機(jī))

－PVP(ParallelVectorProcessor,并行向量機(jī))

－SMP(SymmetricMultiprocessor,對稱多處理機(jī))

－MPP(MassivelyParallelProcessor,大規(guī)模并行處理機(jī))

－COW(ClusterofWorkstation,工作站機(jī)群)

－DSM(DistributedSharedMemory,分布共享存儲多處理機(jī))

注：SIMD是專用并行機(jī)，后5種屬于MIMD并行機(jī)。2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算2022/12/16SISDcomputer-VonNeumann'smodel1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類SIMDcomputer2022/12/12SISDcomputer-VonN2022/12/16Symmetricmultiprocessor–MIMD-SM1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類Massivelyparallelprocessor–MIMD-DM2022/12/12Symmetricmultiproce2022/12/16Clusterofworkstations–MIMD-DM1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2022/12/12Clusterofworkstati2022/12/16VPVPVP…交叉開關(guān)SM(a)PVPP/CP/CP/C…總線或交叉開關(guān)SM(b)SMP,物理上單一地址空間P/CP/CP/C…定制網(wǎng)絡(luò)LMLMLM(c)MPP,物理/邏輯上多地址空間P/CP/CP/C…定制網(wǎng)絡(luò)LMLMLM虛擬分布共享存儲(DSM)(d)DSM(MPP/Cluster),邏輯上單一地址空間結(jié)構(gòu)模型－物理機(jī)模型P/CP/CP/C…定制/標(biāo)準(zhǔn)網(wǎng)絡(luò)LMLMLM(e)Cluster/COW,物理/邏輯上多地址空間1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2022/12/12VPVPVP…交叉開關(guān)SM(a)PVP2022/12/16SMPMPPMPP…WANLMDSMSM(h)Grid(ClusterofClusters)SMPSMPSMP…SAN/LANSMSMSMMPPMPPMPP…SAN/LANDSMDSMDSM(f)SMP-Cluster(g)DSM-Cluster結(jié)構(gòu)模型－物理機(jī)模型1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2022/12/12SMPMPPMPP…WANLMDSMSM2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)(固定連接)

connectedgraphvertices=processingnodesedges=communicationlinks(1)一維線性連接LA(1-DLinearArray)—一維陣列不帶環(huán)繞的1-DLA，帶環(huán)繞的1-DLA(2)網(wǎng)孔連接MC(MeshConnected)—二維陣列不帶環(huán)繞的MC，帶環(huán)繞的MC2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)

(3)樹形連接TC(TreeConnected)二叉樹，胖樹2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)

(4)樹網(wǎng)連接MT(Meshoftree)

2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)(5)金字塔連接(Pyramid)(6)超立方連接HC(HypercubeConnected)3－立方，4－立方(7)立方環(huán)連接CCC(CubeConnected-Cycles)(8)洗牌交換連接SE(ShuffleExchange)(9)蝶形連接(ButterflyConnected)2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò):嵌入將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個網(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)中2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò):嵌入Ringonto2-Dtorus

Hypercubeonto2-Dtorus2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/161.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式動態(tài)互連網(wǎng)絡(luò)(非固定連接)(1)總線Bus(2)交叉開關(guān)CrossbarSwitcher：一種高帶寬網(wǎng)絡(luò)(3)多級互連網(wǎng)絡(luò)MultistageInterconnectionNetwork一種大型開關(guān)網(wǎng)絡(luò)

2022/12/121.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式2022/12/16主要內(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表示加速比性能定律并行算法的同步和通訊2022/12/12主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2022/12/161.2并行計(jì)算模型:PRAM模型描述由Fortune和Wyllie1978年提出，稱為并行隨機(jī)存取機(jī)器PRAM，又稱SIMD-SM模型。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。假設(shè)SM的容量無限有限/無限個功能相同的處理器本地指令和SM的R/W操作都取單位時間結(jié)構(gòu)圖ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory2022/12/121.2并行計(jì)算模型:PRAM模型描述2022/12/161.2并行計(jì)算模型:PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計(jì)算能力比較PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW。令Tm是在模型M上的運(yùn)行時間，則：1979年，Eckstain曾經(jīng)使用二叉樹方法來解決沖突問題解決讀沖突：只允許一個PE從共享存儲單元取內(nèi)容。解決寫沖突：用樹作一種競賽機(jī)構(gòu)，確保僅有一個PE在寫。2022/12/121.2并行計(jì)算模型:PRAM模型分類2022/12/161.2并行計(jì)算模型:PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競爭、通訊延遲等因素推廣存儲競爭模型：將Memory分成一些模塊，每個模塊一次可處理一個訪問，可以在模塊級處理存儲器的競爭。延遲模型：考慮了信息的產(chǎn)生到能夠使用之間的通信延遲

。局部PRAM模型：考慮了存儲帶寬，假定每個PE均有無限局存，而訪問全局存儲器是十分昂貴的。

分層存儲模型：將存儲器視為分層的存儲模塊，每個模塊由其大小及傳送時間表征。異步PRAM模型2022/12/121.2并行計(jì)算模型:PRAM模型優(yōu)點(diǎn)2022/12/161.2并行計(jì)算模型:SIMD-IN模型描述又稱SIMD-DM模型，分布式存儲，處理器通過互連網(wǎng)絡(luò)相連，用傳遞數(shù)據(jù)方式實(shí)現(xiàn)通訊，算法時間復(fù)雜性考慮計(jì)算和選路(時間)，結(jié)構(gòu)圖如下：

常見模型SIMD-LC一維線性連接SIMD-MC網(wǎng)孔連接SIMD-TC樹形連接SIMD-MT樹網(wǎng)連接SIMD-HC超立方連接SIMD-CCC立方環(huán)連接SIMD-SE洗牌交換連接2022/12/121.2并行計(jì)算模型:SIMD-IN模2022/12/161.2并行計(jì)算模型:異步APRAM模型描述又稱分相（Phase）PRAM或MIMD-SM。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(2)全局寫(3)局部操作(4)同步

2022/12/121.2并行計(jì)算模型:異步APRAM模2022/12/161.2并行計(jì)算模型:異步APRAM模型計(jì)算過程由同步障分開的全局相組成

，*號表示局部操作。2022/12/121.2并行計(jì)算模型:異步APRAM模2022/12/161.2并行計(jì)算模型:異步APRAM模型計(jì)算時間

設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加而增加；同步路障時間為B=B(p)非降函數(shù)。令為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計(jì)算時間為

優(yōu)缺點(diǎn)

易編程和分析算法的復(fù)雜度，其上并行算法比較有限，不適合MIMD-DM模型。

2022/12/121.2并行計(jì)算模型:異步APRAM模2022/12/161.2并行計(jì)算模型:BSP模型描述由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。

模型參數(shù)p：處理器數(shù)(帶有存儲器)L：同步障時間(Barriersynchronizationtime)g：選路器吞吐率（帶寬因子）發(fā)送一個消息所用的時間，帶寬因子(timesteps/packet)=1/bandwidth2022/12/121.2并行計(jì)算模型:BSP模型描述2022/12/161.2并行計(jì)算模型:BSP模型計(jì)算過程由若干超級步組成，每個超級步計(jì)算模式為右圖優(yōu)缺點(diǎn)

強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條消息的傳遞等。2022/12/121.2并行計(jì)算模型:BSP模型計(jì)算過2022/12/161.2并行計(jì)算模型:LogP模型描述由Culler(1993)年提出的，是一種分布存儲的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L(Latency)：通迅延遲o(overhead)：通訊額外開銷g(gap)：g=1/bandwidth,處理器可連續(xù)進(jìn)行消息發(fā)送或接收的最小時間間隔P：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量

2022/12/121.2并行計(jì)算模型:LogP模型描述2022/12/161.2并行計(jì)算模型:LogP模型優(yōu)缺點(diǎn)捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。BSPvs.LogPBSPLogP：BSP塊同步BSP子集同步BSP進(jìn)程對同步＝LogPBSP可以常數(shù)因子模擬LogP，LogP可以對數(shù)因子模擬BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程設(shè)環(huán)境，LogP更好地利用了機(jī)器資源BSP似乎更簡單、方便和符合結(jié)構(gòu)化編程

2022/12/121.2并行計(jì)算模型:LogP模型優(yōu)缺2022/12/161.2并行計(jì)算模型:各種計(jì)算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結(jié)構(gòu)SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計(jì)算模式同步異步異步異步異步同步方式自動同步路障同步路障同步隱式同步路障同步模型參數(shù)單位時間步d,讀/寫時間B,同步時間p,處理器數(shù)g,帶寬因子l,同步間隔L,通信延遲o,額外開銷g,帶寬因子P,處理器數(shù)l,信包長度s,發(fā)送建立時間h,通信延遲計(jì)算粒度細(xì)粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫共享變量讀/寫共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間2022/12/121.2并行計(jì)算模型:各種計(jì)算模型比較2022/12/16主要內(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表示加速比性能定律并行算法的同步和通訊2022/12/12主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2022/12/161.3并行算法的一般概念:定義和分類并行算法

一組可同時執(zhí)行且可互相協(xié)作的諸進(jìn)程的集合。分類

VLSI并行算法：在VLSI計(jì)算模型上開發(fā)的并行算法

2022/12/121.3并行算法的一般概念:定義和分類2022/12/161.3并行算法的一般概念:并行算法的表示par-do語句

fori=1tonpar-do

或fori=1tondoinparallel......endforendforforall語句

forallPi,where0≤i≤kdo...endfor2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的復(fù)雜度串行算法的度量一些記號平均情形復(fù)雜度、最壞情形復(fù)雜度2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的復(fù)雜度并行算法復(fù)雜性的度量運(yùn)行時間t(n)：計(jì)算時間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)為求解問題的最快的串行算法在最壞情形下所需的運(yùn)行時間，tp(n)為求解同一問題的并行算法在最壞情形下的運(yùn)行時間。注：(1)加速比Sp(n)反映算法的并行性對運(yùn)行時間的改進(jìn)程度。

(2)若Sp(n)=p(n)，則達(dá)到線性加速；若Sp(n)>p(n)，則為超線性加速(一般出現(xiàn)在某些特殊的應(yīng)用中，如并行搜索等)。并行效率Ep(n)：Ep(n)=Sp(n)/p(n)，0<Ep(n)<=1注：反映了并行系統(tǒng)中處理器的利用程度。工作量(或運(yùn)算量)W(n)：并行算法所執(zhí)行的總操作步數(shù)。(與處理器的數(shù)目無關(guān))2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示Brent定理(1974JACM)

令W(n)是一并行算法A在運(yùn)行時間T(n)內(nèi)執(zhí)行的運(yùn)算量，則A使用p臺處理器可在時間t(n)=O(W(n)/p+T(n))內(nèi)執(zhí)行完成。證明：設(shè)時刻并行算法A做的工作量為Wi(即在(i-1,i]時段內(nèi)的工作量)==>用p臺處理器去完成并行算法A的第i時刻工作量，需時間

==>用p臺處理器模擬并行算法A的總時間為2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示Brent定理注：(1)揭示了并行算法工作量和運(yùn)行時間的關(guān)系；

(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴我們：設(shè)計(jì)并行算法時應(yīng)盡可能將每個時間步的工作量均勻地分?jǐn)偨op臺處理器，使各處理器處于活躍狀態(tài)。2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示例1令n=2k(k>=0)，求n個數(shù)和的并行算法。算法運(yùn)行時間：t(n)=O(logn)總運(yùn)算量:由Brent定理知:t(n)=O(n/p+logn)

2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:加速比性能定律Amdahl’sLaw:BaseonFixedProblemSize適用于實(shí)時應(yīng)用問題。當(dāng)問題的計(jì)算負(fù)載或規(guī)模固定時，我們必須通過增加處理器數(shù)目來降低計(jì)算時間；設(shè)f是算法中不能并行的串行部分比例，Ws和Wp分別是串行和并行部分的工作量，則總工作量W=fW+(1-f)W=Ws+Wp；Amdahl’slaw表明：加速比受到算法中串行工作量的限制。公式推導(dǎo)2022/12/121.3并行算法的一般概念:加速比性能202