并行計(jì)算模型

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