并行計算模型課件

2022/12/16

ParallelAlgorithms

Chapter

1

FoundationofParallelAlgorithmsSpring,

20182022/12/12

ParallelAlgorithms2022/12/16主要內容1.1并行計算機體系結構并行計算機的分類并行計算機的互連方式1.2并行計算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關性與可并行化并行算法的表示并行算法的復雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2022/12/12主要內容1.1并行計算機體系結構2022/12/161.1并行計算機的體系結構:并行計算機分類Flynn分類（1966年）

(1)單指令流單數據流機SISD，即傳統(tǒng)的單處理機(2)單指令流多數據流機SIMD(3)多指令流單數據流機MISD，實際中不存在的機器(4)多指令流多數據流機MIMD并行機的結構模型－實際的機器體系結構－SIMD(SingleInstructionMultipleData,單指令流多數據流機)

－PVP(ParallelVectorProcessor,并行向量機)

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

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

－COW(ClusterofWorkstation,工作站機群)

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

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

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

(3)樹形連接TC(TreeConnected)二叉樹，胖樹2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡

(4)樹網連接MT(Meshoftree)

2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡(5)金字塔連接(Pyramid)(6)超立方連接HC(HypercubeConnected)3－立方，4－立方(7)立方環(huán)連接CCC(CubeConnected-Cycles)(8)洗牌交換連接SE(ShuffleExchange)(9)蝶形連接(ButterflyConnected)2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡:嵌入將網絡中的各節(jié)點映射到另一個網絡中去用膨脹（Dilation）系數來描述嵌入的質量，它是指被嵌入網絡中的一條鏈路在所要嵌入的網絡中對應所需的最大鏈路數如果該系數為1，則稱為完美嵌入。環(huán)網可完美嵌入到2-D環(huán)繞網中超立方網可完美嵌入到2－D環(huán)繞網中2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡:嵌入Ringonto2-Dtorus

Hypercubeonto2-Dtorus2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式動態(tài)互連網絡(非固定連接)(1)總線Bus(2)交叉開關CrossbarSwitcher：一種高帶寬網絡(3)多級互連網絡MultistageInterconnectionNetwork一種大型開關網絡

2022/12/121.1并行計算機的體系結構:互連方式2022/12/16主要內容1.1并行計算機體系結構并行計算機的分類并行計算機的互連方式1.2并行計算模型

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

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

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

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

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

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

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

優(yōu)缺點

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

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

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

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

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

2022/12/121.2并行計算模型:LogP模型優(yōu)缺2022/12/161.2并行計算模型:各種計算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結構SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計算模式同步異步異步異步異步同步方式自動同步路障同步路障同步隱式同步路障同步模型參數單位時間步d,讀/寫時間B,同步時間p,處理器數g,帶寬因子l,同步間隔L,通信延遲o,額外開銷g,帶寬因子P,處理器數l,信包長度s,發(fā)送建立時間h,通信延遲計算粒度細粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫共享變量讀/寫共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間2022/12/121.2并行計算模型:各種計算模型比較2022/12/16主要內容1.1并行計算機體系結構并行計算機的分類并行計算機的互連方式1.2并行計算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關性與可并行化并行算法的表示并行算法的復雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2022/12/12主要內容1.1并行計算機體系結構2022/12/161.3并行算法的一般概念:定義和分類并行算法

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

VLSI并行算法：在VLSI計算模型上開發(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并行算法的一般概念:并行算法的復雜度串行算法的度量一些記號平均情形復雜度、最壞情形復雜度2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的復雜度并行算法復雜性的度量運行時間t(n)：計算時間tc和選路(路由)時間tr處理器數目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)反映算法的并行性對運行時間的改進程度。

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

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

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

(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴我們：設計并行算法時應盡可能將每個時間步的工作量均勻地分攤給p臺處理器，使各處理器處于活躍狀態(tài)。2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示例1令n=2k(k>=0)，求n個數和的并行算法。算法運行時間：t(n)=O(logn)總運算量:由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適用于實時應用問題。當問題的計算負載或規(guī)模固定時，我們必須通過增加處理器數目來降低計算時間；設f是算法中不能并行的串行部分比例，Ws和Wp分別是串行和并行部分的工作量，則總工作量W=fW+(1-f)W=Ws+Wp；Amdahl’slaw表明：加速比受到算法中串行工作量的限制。公式推導2022/12/121.3并行算法的一般概念:加速比性能2022/12/161.3并行算法的一般概念:加速比性能定律Gustafson’sLaw:BaseonFixedExecutionTime適用于要求精度高的應用，通過加大計算量來提高計算精度。Gustafson’sLaw表明：隨著處理器數目的增加，串行執(zhí)行部分f不再是并行算法的瓶頸。放大問題工作量或規(guī)模的加速公式推導：

與p成線性關系。2022/12/121.3并行算法的一般概念:加速比性能2022/12/161.3并行算法的一般概念:加速比性能定律Sun&Ni’sLaw:BaseonMemoryBounding充分利用存儲空間等計算資源，盡量增大問題規(guī)模以產生更好/更精確的解。是Amdahl定律和Gustafson定律的推廣。公式推導：設單機上的存儲器容量為M，其工作負載W=fW+(1-f)W當并行系統(tǒng)有p個結點時，存儲容量擴大了pM，用G(p)表示系統(tǒng)的存儲容量增加p倍時工作負載的增加量。則存儲容量擴大后的工作負載為W=fW+(1-f)G(p)W，所以，存儲受限的加速為特別地：當G(p)=1時，為Amdahl定律；當G(p)=p時，為Gustafson定律；2022/12/121.3并行算法的一般概念:加速比性能2022/12/161.3并行算法的一般概念:并行算法的同步同步概念同步是在時間上強使各執(zhí)行進程在某一點必須互相等待，確保各進程的正常順序和對共享可寫數據的正確訪問；可用軟件、硬件和固件的辦法來實現。同步語句示例算法1.3APRAM上的求和算法輸入：A=(a0,…,an-1),處理器數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算法的時間復雜度：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分布存儲多計算機使用：send(X,i)//處理器P發(fā)送X給處理器Pireceive(Y,j)//處理器P等待從Pj接收數據并存入LM中的Y通訊語句示例算法1.5分布存儲多計算機上矩陣向量乘法,通訊鏈為環(huán)

輸入：處理器數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并行算法的一般概念:并行算法的通訊計算過程圖示2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的通訊算法的復雜度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主要內容1.1并行計算機體系結構并行計算機的分類并行計算機的互連方式1.2并行計算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關性與可并行化并行算法的表示并行算法的復雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2022/12/12主要內容1.1并行計算機體系結構2022/12/161.1并行計算機的體系結構:并行計算機分類Flynn分類（1966年）

(1)單指令流單數據流機SISD，即傳統(tǒng)的單處理機(2)單指令流多數據流機SIMD(3)多指令流單數據流機MISD，實際中不存在的機器(4)多指令流多數據流機MIMD并行機的結構模型－實際的機器體系結構－SIMD(SingleInstructionMultipleData,單指令流多數據流機)

－PVP(ParallelVectorProcessor,并行向量機)

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

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

－COW(ClusterofWorkstation,工作站機群)

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

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

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

(3)樹形連接TC(TreeConnected)二叉樹，胖樹2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡

(4)樹網連接MT(Meshoftree)

2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡(5)金字塔連接(Pyramid)(6)超立方連接HC(HypercubeConnected)3－立方，4－立方(7)立方環(huán)連接CCC(CubeConnected-Cycles)(8)洗牌交換連接SE(ShuffleExchange)(9)蝶形連接(ButterflyConnected)2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡:嵌入將網絡中的各節(jié)點映射到另一個網絡中去用膨脹（Dilation）系數來描述嵌入的質量，它是指被嵌入網絡中的一條鏈路在所要嵌入的網絡中對應所需的最大鏈路數如果該系數為1，則稱為完美嵌入。環(huán)網可完美嵌入到2-D環(huán)繞網中超立方網可完美嵌入到2－D環(huán)繞網中2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式靜態(tài)互連網絡:嵌入Ringonto2-Dtorus

Hypercubeonto2-Dtorus2022/12/121.1并行計算機的體系結構:互連方式2022/12/161.1并行計算機的體系結構:互連方式動態(tài)互連網絡(非固定連接)(1)總線Bus(2)交叉開關CrossbarSwitcher：一種高帶寬網絡(3)多級互連網絡MultistageInterconnectionNetwork一種大型開關網絡

2022/12/121.1并行計算機的體系結構:互連方式2022/12/16主要內容1.1并行計算機體系結構并行計算機的分類并行計算機的互連方式1.2并行計算模型

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

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

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

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

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

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

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

優(yōu)缺點

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

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

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

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

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

2022/12/121.2并行計算模型:LogP模型優(yōu)缺2022/12/161.2并行計算模型:各種計算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結構SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計算模式同步異步異步異步異步同步方式自動同步路障同步路障同步隱式同步路障同步模型參數單位時間步d,讀/寫時間B,同步時間p,處理器數g,帶寬因子l,同步間隔L,通信延遲o,額外開銷g,帶寬因子P,處理器數l,信包長度s,發(fā)送建立時間h,通信延遲計算粒度細粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫共享變量讀/寫共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間2022/12/121.2并行計算模型:各種計算模型比較2022/12/16主要內容1.1并行計算機體系結構并行計算機的分類并行計算機的互連方式1.2并行計算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關性與可并行化并行算法的表示并行算法的復雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2022/12/12主要內容1.1并行計算機體系結構2022/12/161.3并行算法的一般概念:定義和分類并行算法

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

VLSI并行算法：在VLSI計算模型上開發(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并行算法的一般概念:并行算法的復雜度串行算法的度量一些記號平均情形復雜度、最壞情形復雜度2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的復雜度并行算法復雜性的度量運行時間t(n)：計算時間tc和選路(路由)時間tr處理器數目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)反映算法的并行性對運行時間的改進程度。

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

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

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

(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴我們：設計并行算法時應盡可能將每個時間步的工作量均勻地分攤給p臺處理器，使各處理器處于活躍狀態(tài)。2022/12/121.3并行算法的一般概念:并行算法的2022/12/161.3并行算法的一般概念:并行算法的WT表示例1令n=2k(k>=0)，求n個數和的并行算法。算法運行時間：t(n)=O(logn)總運算量:由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適用于實時應用問題。當問題的計算負載或規(guī)模固定時，我們必須通過增加處理器數目來降低計算時間；設f是算法中不能并行的串行部分比例，Ws和Wp分別是串行和并行部分的工作量，則總工作量W=fW+(1-f)W=Ws+Wp；Amdahl’slaw表明：加速比受到算法中串行工作量的限制。公式推導2022/12/121.3并行算法的一般概念:加速比性能202