并行計算模型

抽象的計算模型并行計算模型01PRAM模型LogP模型BDM模型BSP模型C3模型目錄03050204基本信息并行計算模型通常指從并行算法的設(shè)計和分析出發(fā)，將各種并行計算機（至少某一類并行計算機）的基本特征抽象出來，形成一個抽象的計算模型。從更廣的意義上說，并行計算模型為并行計算提供了硬件和軟件界面，在該界面的約定下，并行系統(tǒng)硬件設(shè)計者和軟件設(shè)計者可以開發(fā)對并行性的支持機制，從而提高系統(tǒng)的性能。PRAM模型類型PRAM模型的缺點PRAM模型的優(yōu)點PRAM模型類型PRAM（ParallelRandomAccessMachine，隨機存取并行機器）模型，也稱為共享存儲的SIMD模型，是一種抽象的并行計算模型，它是從串行的RAM模型直接發(fā)展起來的。在這種模型中，假定存在一個容量無限大的共享存儲器，有有限個或無限個功能相同的處理器，且他們都具有簡單的算術(shù)運算和邏輯判斷功能，在任何時刻各處理器都可以通過共享存儲單元相互交互數(shù)據(jù)。根據(jù)處理器對共享存儲單元同時讀、同時寫的限制，PRAM模型可以分為下面幾種：·不允許同時讀和同時寫（Exclusive-ReadandExclusive-Write）的PRAM模型，簡稱為PRAM-EREW；·允許同時讀但不允許同時寫（Concurrent-ReadandExclusive-Write）的PRAM模型，簡稱為PRAM-CREW；·允許同時讀和同時寫（Concurrent-ReadandConcurrent-Write）的PRAM模型，簡稱為PRAM-CRCW。顯然，允許同時寫是不現(xiàn)實的，于是又對PRAM-CRCW模型做了進一步約定，于是形成了下面幾種模型：·只允許所有的處理器同時寫相同的數(shù)，此時稱為公共（common）的PRAM-CRCW，簡稱為CPRAM-CRCW；·只允許最優(yōu)先的處理器先寫，此時稱為優(yōu)先（Priority）的PRAM-CRCW，簡稱為PPRAM-CRCW；·允許任意處理器自由寫，此時稱為任意（Arbitrary）的PRAM-CRCW，簡稱為APRAM-CRCW。PRAM模型的優(yōu)點PRAM模型特別適合于并行算法的表達(dá)、分析和比較，使用簡單，很多關(guān)于并行計算機的底層細(xì)節(jié)，比如處理器間通信、存儲系統(tǒng)管理和進程同步都被隱含在模型中；易于設(shè)計算法和稍加修改便可以運行在不同的并行計算機系統(tǒng)上；根據(jù)需要，可以在PRAM模型中加入一些諸如同步和通信等需要考慮的內(nèi)容。PRAM模型的缺點(1)模型中使用了一個全局共享存儲器，且局存容量較小，不足以描述分布主存多處理機的性能瓶頸，而且共享單一存儲器的假定，顯然不適合于分布存儲結(jié)構(gòu)的MIMD機器；(2)PRAM模型是同步的，這就意味著所有的指令都按照鎖步的方式操作，用戶雖然感覺不到同步的存在，但同步的存在的確很耗費時間，而且不能反映現(xiàn)實中很多系統(tǒng)的異步性；(3)PRAM模型假設(shè)了每個處理器可在單位時間訪問共享存儲器的任一單元，因此要求處理機間通信無延遲、無限帶寬和無開銷，假定每個處理器均可以在單位時間內(nèi)訪問任何存儲單元而略去了實際存在的，合理的細(xì)節(jié)，比如資源競爭和有限帶寬，這是不現(xiàn)實的；(4)PRAM模型假設(shè)處理機有限或無限，對并行任務(wù)的增大無開銷；(5)未能描述所線程技術(shù)和流水線預(yù)取技術(shù)，而這兩種技術(shù)又是當(dāng)今并行體系結(jié)構(gòu)用的最普遍的技術(shù)。BSP模型對BSP模型的評價BSP模型的特點BSP模型BSP模型的特點BSP模型是個分布存儲的MIMD計算模型，其特點是：·它將處理器和路由器分開，強調(diào)了計算任務(wù)和通信任務(wù)的分開，而路由器僅僅完成點到點的消息傳遞，不提供組合、復(fù)制和廣播等功能，這樣做既掩蓋具體的互連絡(luò)拓?fù)?，又簡化了通信協(xié)議；·采用障礙同步的方式以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負(fù)擔(dān)；·在分析BSP模型的性能時，假定局部操作可以在一個時間步內(nèi)完成，而在每一個超級步中，一個處理器至多發(fā)送或接收h條消息（稱為h-relation）。假定s是傳輸建立時間，所以傳送h條消息的時間為gh+s，如果，則L至少應(yīng)該大于等于gh。很清楚，硬件可以將L設(shè)置盡量?。ɡ缡褂昧魉€或大的通信帶寬使g盡量?。?，而軟件可以設(shè)置L的上限（因為L越大，并行粒度越大）。在實際使用中，g可以定義為每秒處理器所能完成的局部計算數(shù)目與每秒路由器所能傳輸?shù)臄?shù)據(jù)量之比。如果能夠合適的平衡計算和通信，則BSP模型在可編程性方面具有主要的優(yōu)點，而直接在BSP模型上執(zhí)行算法（不是自動的編譯它們），這個優(yōu)點將隨著g的增加而更加明顯；·為PRAM模型所設(shè)計的算法，都可以采用在每個BSP處理器上模擬一些PRAM處理器的方法來實現(xiàn)。理論分析證明，這種模擬在常數(shù)因子范圍內(nèi)是最佳的，只要并行寬松度（ParallelSlackness），即每個BSP處理器所能模擬的PRAM處理器的數(shù)目足夠大。對BSP模型的評價·在并行計算時，Valiant試圖也為軟件和硬件之間架起一座類似于馮·諾伊曼機的橋梁，它論證了BSP模型可以起到這樣的作用，正是因為如此，BSP模型也常叫做橋模型；·一般而言，分布存儲的MIMD模型的可編程性比較差，但在BSP模型中，如果計算和通信可以合適的平衡（例如g=1），則它在可編程方面呈現(xiàn)出主要的優(yōu)點；·在BSP模型上，曾直接實現(xiàn)了一些重要的算法（如矩陣乘、并行前序運算、FFT和排序等），他們均避免了自動存儲管理的額外開銷；·BSP模型可以有效的在超立方體絡(luò)和光交叉開關(guān)互連技術(shù)上實現(xiàn)，顯示出，該模型與特定的技術(shù)實現(xiàn)無關(guān)，只要路由器有一定的通信吞吐率；·在BSP模型中，超級步的長度必須能夠充分的適應(yīng)任意的h-relation，這一點是人們最不喜歡的；·在BSP模型中，在超級步開始發(fā)送的消息，即使絡(luò)延遲時間比超級步的長度短，它也只能在下一個超級步才能使用；·BSP模型中的全局障礙同步假定是用特殊的硬件支持的，這在很多并行機中可能沒有相應(yīng)的硬件；·Valiant所提出的編程模擬環(huán)境，在算法模擬時的常數(shù)可能不是很小的，如果考慮到進程間的切換（可能不LogP模型描述LogP模型的不足之處LogP模型的特點LogP模型描述根據(jù)技術(shù)發(fā)展的趨勢，20世紀(jì)90年代末和未來的并行計算機發(fā)展的主流之一是巨量并行機，即MPC（MassivelyParallelComputers），它由成千個功能強大的處理器/存儲器節(jié)點，通過具有有限帶寬的和相當(dāng)大的延遲的互連絡(luò)構(gòu)成。所以我們建立并行計算模型應(yīng)該充分考慮到這個情況，這樣基于模型的并行算法才能在現(xiàn)有和將來的并行計算機上有效的運行。根據(jù)已有的編程經(jīng)驗，現(xiàn)有的共享存儲、消息傳遞和數(shù)據(jù)并行等編程方式都很流行，但還沒有一個公認(rèn)的和占支配地位的編程方式，因此應(yīng)該尋求一種與上面的編程方式無關(guān)的計算模型。而根據(jù)現(xiàn)有的理論模型，共享存儲PRAM模型和互連絡(luò)的SIMD模型對開發(fā)并行算法還不夠合適，因為它們既沒有包含分布存儲的情況，也沒有考慮通信和同步等實際因素，從而也不能精確的反映運行在真實的并行計算機上的算法的行為，所以，1993年D.Culer等人在分析了分布式存儲計算機特點的基礎(chǔ)上，提出了點對點通信的多計算機模型，它充分說明了互聯(lián)絡(luò)的性能特性，而不涉及到具體的絡(luò)結(jié)構(gòu)，也不假定算法一定要用現(xiàn)實的消息傳遞操作進行描述。LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信絡(luò)由4個主要參數(shù)來描述：（1）L(Latency)表示源處理機與目的處理機進行消息（一個或幾個字）通信所需要的等待或延遲時間的上限，表示絡(luò)中消息的延遲。（2）o(overhead)表示處理機準(zhǔn)備發(fā)送或接收每個消息的時間開銷（包括操作系統(tǒng)核心開銷和絡(luò)軟件開銷），在這段時間里處理不能執(zhí)行其它操作。LogP模型的特點(1)抓住了絡(luò)與處理機之間的性能瓶頸。g反映了通信帶寬，單位時間內(nèi)最多有L/g個消息能進行處理機間傳送。(2)處理機之間異步工作，并通過處理機間的消息傳送來完成同步。(3)對多線程技術(shù)有一定反映。每個物理處理機可以模擬多個虛擬處理機(VP)，當(dāng)某個VP有訪問請求時，計算不會終止，但VP的個數(shù)受限于通信帶寬和上下文交換的開銷。VP受限于絡(luò)容量，至多有L/g個VP。(4)消息延遲不確定，但延遲不大于L。消息經(jīng)歷的等待時間是不可預(yù)測的，但在沒有阻塞的情況下，最大不超過L。(5)LogP模型鼓勵編程人員采用一些好的策略，如作業(yè)分配，計算與通信重疊以及平衡的通信模式等。(6)可以預(yù)估算法的實際運行時間。LogP模型的不足之處（1）對絡(luò)中的通信模式描述的不夠深入。如重發(fā)消息可能占滿帶寬、中間路由器緩存飽和等未加描述。（2）LogP模型主要適用于消息傳遞算法設(shè)計，對于共享存儲模式，則簡單地認(rèn)為遠(yuǎn)地讀操作相當(dāng)于兩次消息傳遞，未考慮流水線預(yù)取技術(shù)、Cache引起的數(shù)據(jù)不一致性以及Cache命中率對計算的影響。（3）未考慮多線程技術(shù)的上下文開銷。（4）LogP模型假設(shè)用點對點消息路由器進行通信，這增加了編程者考慮路由器上相關(guān)通信操作的負(fù)擔(dān)。C3模型C3模型的不足之處C3模型的特點C3模型C3模型的特點(1)用Cl和Cp來度量絡(luò)的擁擠對算法性能的影響；(2)考慮了不同路由和不同發(fā)送或接收原語對通信的影響；(3)不需要用戶指定調(diào)度細(xì)節(jié)，就可以評估超步的時間復(fù)雜性；(4)類似于H-PRAM模型的層次結(jié)構(gòu)，C3模型給編程者提供了K級路由算法的思路，即系統(tǒng)被分為K級子系統(tǒng)，各級子系統(tǒng)的操作相互獨立，用超步代替了H-PRAM中的SubPRAM進行分割。C3模型的不足之處(1)Cl度量的前題假設(shè)為同一通信對中的2個處理機要分別位于絡(luò)對分后的不同子絡(luò)內(nèi)；(2)模型假設(shè)了絡(luò)帶寬等于處理機帶寬，這影響了正確描述可擴展系統(tǒng)；(3)在K級算法中，處理機間順序可以由多種排列，但C3模型不能區(qū)分不同排列的難易程度。BDM模型BDM模型的不足BDM模型的特點BDM模型BDM模型的特點(1)用M反映出空間局部性特點，提供了一種評價共享主存算法的