并行計算機(jī)的抽象模型課件

并行計算機(jī)的抽象模型并行計算機(jī)的理論模型是從物理模型抽象的；為開發(fā)并行算法提供了一種方便的框架；用這些模型可求得并行計算機(jī)的理論性能界限；可在芯片制作前估算芯片區(qū)的VLSI復(fù)雜性和執(zhí)行時間。一、時間與空間復(fù)雜性計算機(jī)求解一個規(guī)模為s的問題的算法復(fù)雜性取決于：執(zhí)行時間存儲空間時間復(fù)雜性：時間復(fù)雜性g(s)為O(f(s))，可讀作“數(shù)量級為f(s)”，如存在正的常量c和s0，則對所有s>s0的非負(fù)值就有g(shù)(s)≤cf(s)。空間復(fù)雜性為問題規(guī)模s的函數(shù)。漸近空間復(fù)雜性(asymptoticspacecom—plexity)主要與大問題的數(shù)據(jù)存儲有關(guān)，而程序(代碼)存儲的需求和輸入數(shù)據(jù)的存儲不考慮在內(nèi)。串行算法的時間復(fù)雜性簡稱為串行復(fù)雜性;并行算法的時間復(fù)雜性就稱為并行復(fù)雜性;并行復(fù)雜性應(yīng)比串行復(fù)雜性低，至少是相近。只考慮確定性算法。NP完全性：P類(即多項式類)：具有多項式復(fù)雜性算法的問題集，如果存在一多項式p(s)，對任何問題規(guī)模s的時間復(fù)雜性為O(p(s))，則某算法即具有多項式復(fù)雜性。NP類(即不確定性多項式類)：能以多項式時間，用不確定性算法求解的問題集。P

NP確定性算法是不確定算法的特殊情況。P類問題是計算易解的，而NP-P類問題是難解的。現(xiàn)在不知道是否P＝NP或P≠NP。難解的NP類問題又稱為具有指數(shù)時間復(fù)雜性的問題。例題：多項式復(fù)雜性和指數(shù)復(fù)雜性算法：將幾個數(shù)排序的多項式時間復(fù)雜性分別為O(nlogn)，屬于P類對兩個n×n矩陣相乘算法的多項式時間復(fù)雜性分別為O(n3)，屬于P類。旅行推銷員問題復(fù)雜性為O(n22n)和背包問題的復(fù)雜性為O(2n/2)指數(shù)復(fù)雜性問題是屬NP類的：到目前為止還未發(fā)現(xiàn)這類問題的確定性多項式算法。P、NP和NPC（NP完全問題）二、并行隨機(jī)存取機(jī)模型(ParallelRandom—AccessMachine，PRAM)目的：可用來開發(fā)并行算法和分析可擴(kuò)展性及復(fù)雜性。MIMD細(xì)粒度嚴(yán)格同步零開銷共享變量在PRAM上的一個并行程序由n個進(jìn)程組成，其中第i個進(jìn)程留駐在第i個處理器上，且由一串指令所組成。在每個基本時間步(稱為周期)，每個處理器執(zhí)行一條指令。這些指令包括數(shù)據(jù)傳送、算/邏、控制流以及I/O指令，在典型的順序計算機(jī)中均有這些指令。1.同構(gòu)性規(guī)模為1的PRAM退化為傳統(tǒng)的RAM。這種機(jī)器為SISD。當(dāng)處理器多于1個時，一個PRAM將訪問多個數(shù)據(jù)流，且通常可執(zhí)行多個指令流。因此PRAM是一個MIMD機(jī)器。MIMD的特例:如果在每一周期，所有處理器必須執(zhí)行相同指令，即只有一個指令流時，則PRAM就成為單指令(流)、多數(shù)據(jù)(流)(SIMD)機(jī)器。(SPMD)計算：單程序、多數(shù)據(jù)，所有進(jìn)程執(zhí)行同一程序，而由進(jìn)程指標(biāo)加以參數(shù)化。SIMD和SPMD間的差別是，在SPMD計算中，同一周期可以執(zhí)行不同指令。2.同步性進(jìn)程同步是嚴(yán)格的。PRAM是在指令級同步的。3.交互機(jī)制這一屬性描述了并行進(jìn)程間如何相互影響行為的特性。在PRAM模型中，進(jìn)程間通過共享變量(或共享存儲器)進(jìn)行交互。4.地址空間理論P(yáng)RAM模型的一個重要特征是所有進(jìn)程對所有存儲單元均有相等的訪問時間。這種機(jī)器為均勻存儲器訪問(UMA)。在多計算機(jī)中，每個處理機(jī)有它自己的分離地址空間。這些機(jī)器被稱為具有多地址空間。多計算機(jī)的處理機(jī)間通信不是通過共享變量，而是借助消息傳遞。5.存儲器模型各種方案的主要區(qū)別在于如何協(xié)調(diào)CW的沖突。四種PRAM模型方案都與存儲器讀寫如何處理有關(guān)。(1)EREW-PRAM模型——這種模型禁止一臺以上處理機(jī)同時讀、寫同一存儲單元(Snir，1982；Karp和Ramachandran，1988)。這是限制最大的PRAM模型。(2)CREW-PRAM模型——用互斥使寫沖突避免?？梢圆⑿凶x同一存儲單元。

(3)ERCW-PRAM模型——允許互斥讀或并行寫同一存儲單元。(4)CRCW-PRAM模型——允許在同一時刻并行讀或者并行寫。寫沖突可用下述四種策略之一分解：共用——所有同時進(jìn)行的寫操作將相同數(shù)據(jù)存入熱點(diǎn)存儲單元。任選——將任何一個要寫的數(shù)保存起來，而其它的忽略不計。最小值——將處理機(jī)要寫的下標(biāo)值最小的數(shù)保存起來。優(yōu)先——對要寫的數(shù)用求和或求最大值等聯(lián)想函數(shù)加以組合。

6.原子操作原子操作的定義：一個原子操作是指有如下特性的一種操作。不可分有限更嚴(yán)格的原子操作定義：需要滿足以下的4個性質(zhì)。稱這樣的原子操作為一個事務(wù)操作。

原子性一致性隔離性持續(xù)性7.例題例題1：在一臺處理機(jī)數(shù)為n3／logn的PRAM上，用O(logn)時間完成兩個”nxn”矩陣的乘法(ViktorPrasanna，1992)設(shè)A和B為輸入矩陣，假定最初可用的PE數(shù)為n3個，后來降為n3／logn個。

假設(shè)內(nèi)存由三維陣列組成，將A、B存入其中兩個平面。假設(shè)了PE的三維地址指標(biāo)。PE(i，j，k)，0≤k≤n-1可用來計算輸出矩陣的第(i，j)項，0≤i，j≤n-1，n是2的冪。

第一步，對應(yīng)于每個輸出的n乘積項用n個PE在O(1)時間內(nèi)進(jìn)行計算。第二步，這些乘積項用O(logn)時間相加產(chǎn)生一個輸出。所用的PE總數(shù)為n3，結(jié)果存在C(i，j，0)中(0≤i，j≤n-1)。假定這里的PRAM采用的是CREW策略。Step1：1．ReadA(i，k)2．ReadB(k，j)3．ComputeA(i，k)×B(k,j)4．StoreinC(I,j,k)

Step2：

1．L←n2．RepeatL←L／2If(k<1)thenbegin

ReadA(i，k)ReadA(i，k)ComputeC(i,j,k)+C(i,j,k,k+l)StoreinC(i,j,k)EndUntil(l=1)上述是每個PE(i，j，k)要執(zhí)行的程序。所有n3個PE對n3乘法進(jìn)行并行運(yùn)算。但對完成(n3-n2)加法最多只有n3／2個PE處于工作狀態(tài)。為了將PE數(shù)降為n3／logn，可采用nXnXn／logn的PE陣列。每個PE負(fù)責(zé)計算logn個乘積項并將它們求和。第一步很容易改寫產(chǎn)生n／logn個部分和，每一個部分和由logn次乘法和(logn-1)次加法完成。我們有數(shù)組C(i，j，k)，0≤i，j≤n-1，0≤k≤n／logn-1，它們可在log(n／logn)時間內(nèi)完成求和，所以將第一步和第二步所花的時間相加，我們就得到總執(zhí)行時間為2logn-1+log(n／logn)，在n比較大時近似為O(logn)。例題2：PRAM步中的計算復(fù)雜性

假設(shè)有三個PRAM算法A，B和C，當(dāng)在一個有n個處理器的PRAM計算機(jī)上執(zhí)行時，各自的時間復(fù)雜性為A--7n，B--(nlogn)／4C--nloglogn。根據(jù)大O標(biāo)志：算法A最快：(O(n))，C次之：O(nloglogn)，B為最慢：O(nlogn)。而實(shí)際上，當(dāng)機(jī)器的處理器數(shù)小于、等于1024時，有l(wèi)ogn<log1024=10以及l(fā)oglogn≤loglog1024<4。如果，處理器數(shù)小于1024時：算法B最快，其次是C，而A則是最慢的。與物理模型的差異

實(shí)際上，這種并行計算機(jī)是不存在的。共享存儲器SIMD機(jī)是與PRAM模型最接近的結(jié)構(gòu)。更確切地說，共享存儲的同步MIMD模式運(yùn)行。四種PRAM方案中，EREW和CRCW是應(yīng)用最普遍的模型。每個CRCW算法可用一個EREW算法來模擬。CRCW算法比一個等效的EREW要快，經(jīng)證明，最好的n—處理機(jī)EREW算法要比任一個n-處理機(jī)CRCW算法慢O(logn)倍。對研究結(jié)構(gòu)規(guī)則的并行性來說，用PRAM比用實(shí)際機(jī)器模型要好得多。PRAM能指出實(shí)際并行計算機(jī)性能的上限。三、異步PRAM模型—APRAM是一個異步的PRAM模型，簡記為APRAM1.模型特點(diǎn)：由p個處理器組成；每個處理器都有其本地存儲器、局部時鐘和局部程序；處理器間的通信經(jīng)過共享全局存儲器；無全局時鐘各處理器異步地獨(dú)立執(zhí)行各自的指令；處理器任何時間依賴關(guān)系需明確地在各處理器的程序中加入同步(路)障(SynchronizationBarrier)；一條指令可在非確定但有限的時間內(nèi)完成。2、APRAM模型中的指令類型有四類指令：①全局讀將全局存儲單元中的內(nèi)容讀入局存單元中；②局部操作對局存中的數(shù)執(zhí)行操作，其結(jié)果存入局存中；③全局寫將局存單元中的內(nèi)容寫入全局存儲單元中；④同步同步是計算中的一個邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后，才能執(zhí)行其局部程序。3.APRAM模型中完成的計算

計算是由一系列用同步障分開的全局相所組成。在各全局相內(nèi)，每個處理器異步地運(yùn)行其局部程序；每個局部程序中的最后一條指令是一條同步障指令；各處理器均可異步地讀取和寫入全局存儲器，在同一相內(nèi)不允許兩個處理器訪問同一單元。不同的處理器訪問存儲單元總是由一同步障所分開，所以指令完成時間上的差異并不影響整個計算4.APRAM模型中的時間計算使用APRAM模型計算算法的時間復(fù)雜度時，假定局部操作取單位時間；全局讀／寫時間為d它定量化了通信延遲，代表讀/寫全局存儲器的平均時間，d隨機(jī)器中的處理器增加而增加；同步障的時間為B它是處理器數(shù)P的非降函數(shù)B=B(P)。在APRAM中假定上述參數(shù)服從如下關(guān)系：2≤d≤B≤P同時：B(P)∈O(dlogP)或B(P)∈O(dlogP/logd)。令tph為全局相內(nèi)各處理器指令執(zhí)行時間中最長者，則整個程序運(yùn)行時間T為各相的時間之和加上B乘以同步障次數(shù)，即:T=∑tph+B×同步障次數(shù)四.BSP模型BSP-BulkSynchronizationParallel1.BSP模型的提出：哈佛大學(xué)的LeslieValiant提出：塊同步并行(BSP)，用以克服PRAM模型的缺點(diǎn)，但保留其簡單性。一個BSP計算機(jī)由n個結(jié)點(diǎn)(處理器和存儲器對)所組成。2.特點(diǎn)：一個BSP程序有n個進(jìn)程，每個駐留在一個結(jié)點(diǎn)上?；緯r間單位是周期(或時間步)。程序按嚴(yán)格的超步序列執(zhí)行。特點(diǎn)：同步路障迫使進(jìn)程等待BSP計算機(jī)是MIMD系統(tǒng)BSP模型是超步級的松同步在一個超步中，不同進(jìn)程以不同速率異步執(zhí)行。BSP模型交互機(jī)制是共享變量或是消息傳遞。3.h關(guān)系的定義:一個h關(guān)系是任何通信操作的抽象，在其中，每個結(jié)點(diǎn)最多發(fā)出h個字到各結(jié)點(diǎn)，并且每個結(jié)點(diǎn)最多接收h個字。在一個BSP計算機(jī)中，實(shí)現(xiàn)任何h關(guān)系的時間不會超過gh個周期。g是由機(jī)器平臺決定的一個常數(shù)。

4.一個超步執(zhí)行時間的確定計算時間w處理器中完成計算操作所需的最大周期數(shù)。同步開銷為L。通信開銷為gh周期g是實(shí)現(xiàn)h關(guān)系的比例系數(shù)，常數(shù)。結(jié)論：執(zhí)行一個超步的時間為w+gh+L5.例題：在一個有n個處理器的EREWPRAM計算機(jī)上，對兩個N維向量A和B求內(nèi)積s，可指派每個處理器完成2N／n個加法和乘法（2N／n+logn）；改用BSP機(jī)器模型實(shí)現(xiàn)一個并行執(zhí)行上述內(nèi)積求解。在一個有8個處理器的BSP計算機(jī)上，用4個超步完成問題求解：超步１：每個處理器在w=2N／8周期內(nèi)計算，求出局部和。通信1次：處理器0，2，4，6將其局部和→處理器1，3，5，7。路障同步。超步２：計算１、３、５、７各自完成一次加法；通訊1次：處理器１，５中間結(jié)果送處理器３和７。路障同步超步３：計算：處理器３和處理器７，各完成一次加；通訊：處理器３→處理器７，完成一次通訊路障同步。超步4計算：處理器7完成一次加法(w＝１）產(chǎn)生最后和。不再需要任何通信或同步?？倛?zhí)行時間：2N／8+3g+3Ｌ+3個周期總之：點(diǎn)積在一個有n個處理器的BSP計算機(jī)上，執(zhí)行時間為：2N／n+logｎ(g+L+1)個周期。與PRAM計算機(jī)的2N／n+logn時間相比:多了兩項glogn和Llogn

關(guān)于BSP模型的實(shí)際優(yōu)點(diǎn)和評論：比起PRAM模型來，BSP模型更為現(xiàn)實(shí)除了用于進(jìn)程管理的并行性開銷外，它考慮了所有其他開銷。五.VLSI復(fù)雜性模型基本概念VLSI復(fù)雜性模型

背景：以ClarkThompson(1980)的研究工作為基礎(chǔ)的二維VLSI芯片的AT2模型。AT2模型：

設(shè)A是用VLSI電路芯片完成給定運(yùn)算的芯片面積，T為執(zhí)行時間，又設(shè)s為運(yùn)算問題的規(guī)模。Thompson在其博士論文中曾指出：對某些運(yùn)算存在一個下界f(s)，有AT2≥O(

f(s))1、芯片面積A的存儲界限許多計算在需要處理大型數(shù)據(jù)集時常受到存儲器的限制。計算對存儲量的需求常常決定了芯片面積A的下限。2、AT體積的I/O界限可以用乘積AT來表示I／O的下限。3、等分通信界限A1/2Ｔ

等分面積A1/2Ｔ，限定通信的下限。4、例題：矩陣相乘算法的VLSI芯片的實(shí)現(xiàn)(VictorPrasanna，1992)

要求：在一個每行和每列處理單元(PE)都有廣播總線的網(wǎng)格系統(tǒng)上做n×n矩陣乘法C＝A×B如何計算芯片面積A和計算時間T？分析：二維網(wǎng)格結(jié)構(gòu)如下圖所示。PE間的通信通過廣播總線實(shí)現(xiàn)。每個PE占據(jù)一單位面積：總芯片面積為O(n2)。廣播總線需要O(n2)