并行计算机的抽象模型课件

並行電腦的抽象模型一、時間與空間複雜性電腦求解一個規模為s的問題的演算法複雜性取決於：執行時間存儲空間時間複雜性：時間複雜性g(s)為O(f(s))，可讀作“數量級為f(s)”，如存在正的常量c和s0，則對所有s>s0的非負值就有g(s)≤cf(s)。空間複雜性為問題規模s的函數。漸近空間複雜性(asymptoticspacecom—plexity)主要與大問題的數據存儲有關，而程式(代碼)存儲的需求和輸入數據的存儲不考慮在內。串行演算法的時間複雜性簡稱為串行複雜性;並行演算法的時間複雜性就稱為並行複雜性;並行複雜性應比串行複雜性低，至少是相近。只考慮確定性演算法。NP完全性：P類(即多項式類)：具有多項式複雜性演算法的問題集，如果存在一多項式p(s)，對任何問題規模s的時間複雜性為O(p(s))，則某演算法即具有多項式複雜性。NP類(即不確定性多項式類)：能以多項式時間，用不確定性演算法求解的問題集。P

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

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

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

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

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

第一步，對應於每個輸出的n乘積項用n個PE在O(1)時間內進行計算。第二步，這些乘積項用O(logn)時間相加產生一個輸出。所用的PE總數為n3，結果存在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)要執行的程式。所有n3個PE對n3乘法進行並行運算。但對完成(n3-n2)加法最多只有n3／2個PE處於工作狀態。為了將PE數降為n3／logn，可採用nXnXn／logn的PE陣列。每個PE負責計算logn個乘積項並將它們求和。第一步很容易改寫產生n／logn個部分和，每一個部分和由logn次乘法和(logn-1)次加法完成。我們有數組C(i，j，k)，0≤i，j≤n-1，0≤k≤n／logn-1，它們可在log(n／logn)時間內完成求和，所以將第一步和第二步所花的時間相加，我們就得到總執行時間為2logn-1+log(n／logn)，在n比較大時近似為O(logn)。例題2：PRAM步中的計算複雜性

假設有三個PRAM演算法A，B和C，當在一個有n個處理器的PRAM電腦上執行時，各自的時間複雜性為A--7n，B--(nlogn)／4C--nloglogn。根據大O標誌：演算法A最快：(O(n))，C次之：O(nloglogn)，B為最慢：O(nlogn)。而實際上，當機器的處理器數小於、等於1024時，有logn<log1024=10以及loglogn≤loglog1024<4。如果，處理器數小於1024時：演算法B最快，其次是C，而A則是最慢的。與物理模型的差異

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

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

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

關於BSP模型的實際優點和評論：比起PRAM模型來，BSP模型更為現實除了用於進程管理的並行性開銷外，它考慮了所有其他開銷。五.VLSI複雜性模型基本概念VLSI複雜性模型

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

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

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

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

要求：在一個每行和每列處理單元(PE)都有廣播匯流排的網格系統上做n×n矩陣乘法C＝A×B如何計算晶片面積A和計算時間T？分析：二維網格結構如下圖所示。PE間的通信通過廣播匯流排實現。每個PE佔據一單位面積：總晶片面積為O(n2)。廣播匯流排需要O(n2)導線面積。nX