并行計(jì)算模型通常指從并行算法的設(shè)計(jì)和分析出發(fā)，將各種并行計(jì)算機(jī)（至少某一類并行計(jì)算機(jī)）的基本特征抽象出來(lái)，形成一個(gè)抽象的計(jì)算模型。

PRAM模型

PRAM（Parallel Random Access Machine，隨機(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-Read and Exclusive-Write）的PRAM模型，簡(jiǎn)稱為PRAM-EREW；
允許同時(shí)讀但不允許同時(shí)寫（Concurrent-Read and Exclusive-Write）的PRAM模型，簡(jiǎn)稱為PRAM-CREW；
允許同時(shí)讀和同時(shí)寫（Concurrent-Read and Concurrent-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。
往存儲(chǔ)器中寫的實(shí)際內(nèi)容是所有處理器寫的數(shù)的和，此時(shí)稱為求和（Sum）的PRAM-CRCE，將稱為SPRAM-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ú)開(kāi)銷，假定每個(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ú)開(kāi)銷；

(5)未能描述所線程技術(shù)和流水線預(yù)取技術(shù)，而這兩種技術(shù)又是當(dāng)今并行體系結(jié)構(gòu)用的最普遍的技術(shù)。

BSP模型

BSP模型基本原理

BSP模型是一種異步MIMD-DM模型（DM: distributed memory，SM: shared memory），BSP模型支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步，該模型基于一個(gè)master協(xié)調(diào)，所有的worker同步(lock-step)執(zhí)行, 數(shù)據(jù)從輸入的隊(duì)列中讀取，該模型的架構(gòu)如圖所示：

另外，BSP并行計(jì)算模型可以用 p/s/g/I 4個(gè)參數(shù)進(jìn)行描述：

P為處理器的數(shù)目(帶有存儲(chǔ)器)。

s為處理器的計(jì)算速度。

g為每秒本地計(jì)算操作的數(shù)目/通信網(wǎng)絡(luò)每秒傳送的字節(jié)數(shù)，稱之為選路器吞吐率，視為帶寬因子 (time steps/packet)=1/bandwidth。

i為全局的同步時(shí)間開(kāi)銷,稱之為全局同步之間的時(shí)間間隔 (Barrier synchronization time)。

那么假設(shè)有p臺(tái)處理器同時(shí)傳送h個(gè)字節(jié)信息，則gh就是通信的開(kāi)銷。同步和通信的開(kāi)銷都規(guī)格化為處理器的指定條數(shù)。

BSP計(jì)算模型不僅是一種體系結(jié)構(gòu)模型，也是設(shè)計(jì)并行程序的一種方法。BSP程序設(shè)計(jì)準(zhǔn)則是整體同步(bulk synchrony)，其獨(dú)特之處在于超步(superstep)概念的引入。一個(gè)BSP程序同時(shí)具有水平和垂直兩個(gè)方面的結(jié)構(gòu)。從垂直上看,一個(gè)BSP程序由一系列串行的超步(superstep)組成,如圖所示:

這種結(jié)構(gòu)類似于一個(gè)串行程序結(jié)構(gòu)。從水平上看，在一個(gè)超步中，所有的進(jìn)程并行執(zhí)行局部計(jì)算。一個(gè)超步可分為三個(gè)階段，如圖所示：

本地計(jì)算階段，每個(gè)處理器只對(duì)存儲(chǔ)本地內(nèi)存中的數(shù)據(jù)進(jìn)行本地計(jì)算。

全局通信階段，對(duì)任何非本地?cái)?shù)據(jù)進(jìn)行操作。

柵欄同步階段，等待所有通信行為的結(jié)束。

BSP模型特點(diǎn)

1. BSP模型將計(jì)算劃分為一個(gè)一個(gè)的超步(superstep)，有效避免死鎖。

2. 它將處理器和路由器分開(kāi)，強(qiáng)調(diào)了計(jì)算任務(wù)和通信任務(wù)的分開(kāi)，而路由器僅僅完成點(diǎn)到點(diǎn)的消息傳遞，不提供組合、復(fù)制和廣播等功能，這樣做既掩蓋具體的互連網(wǎng)絡(luò)拓?fù)?，又?jiǎn)化了通信協(xié)議；

3. 采用障礙同步的方式以硬件實(shí)現(xiàn)的全局同步是在可控的粗粒度級(jí)，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無(wú)過(guò)分的負(fù)擔(dān)；

4. 在分析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盡量?。?，而軟件可以設(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的增加而更加明顯；

5. 為PRAM模型所設(shè)計(jì)的算法，都可以采用在每個(gè)BSP處理器上模擬一些PRAM處理器的方法來(lái)實(shí)現(xiàn)。

BSP模型的評(píng)價(jià)

1. 在并行計(jì)算時(shí)，Valiant試圖也為軟件和硬件之間架起一座類似于馮·諾伊曼機(jī)的橋梁，它論證了BSP模型可以起到這樣的作用，正是因?yàn)槿绱?，BSP模型也常叫做橋模型。

2. 一般而言，分布存儲(chǔ)的MIMD模型的可編程性比較差，但在BSP模型中，如果計(jì)算和通信可以合適的平衡（例如g=1），則它在可編程方面呈現(xiàn)出主要的優(yōu)點(diǎn)。

3. 在BSP模型上，曾直接實(shí)現(xiàn)了一些重要的算法（如矩陣乘、并行前序運(yùn)算、FFT和排序等），他們均避免了自動(dòng)存儲(chǔ)管理的額外開(kāi)銷。

4. BSP模型可以有效的在超立方體網(wǎng)絡(luò)和光交叉開(kāi)關(guān)互連技術(shù)上實(shí)現(xiàn)，顯示出，該模型與特定的技術(shù)實(shí)現(xiàn)無(wú)關(guān)，只要路由器有一定的通信吞吐率。

5. 在BSP模型中，超級(jí)步的長(zhǎng)度必須能夠充分的適應(yīng)任意的h-relation，這一點(diǎn)是人們最不喜歡的。

6. 在BSP模型中，在超級(jí)步開(kāi)始發(fā)送的消息，即使網(wǎng)絡(luò)延遲時(shí)間比超級(jí)步的長(zhǎng)度短，該消息也只能在下一個(gè)超級(jí)步才能被使用。

7. BSP模型中的全局障礙同步假定是用特殊的硬件支持的，但很多并行機(jī)中可能沒(méi)有相應(yīng)的硬件。

BSP與MapReduce對(duì)比

執(zhí)行機(jī)制：MapReduce是一個(gè)數(shù)據(jù)流模型，每個(gè)任務(wù)只是對(duì)輸入數(shù)據(jù)進(jìn)行處理，產(chǎn)生的輸出數(shù)據(jù)作為另一個(gè)任務(wù)的輸入數(shù)據(jù)，并行任務(wù)之間獨(dú)立地進(jìn)行，串行任務(wù)之間以磁盤和數(shù)據(jù)復(fù)制作為交換介質(zhì)和接口。

BSP是一個(gè)狀態(tài)模型，各個(gè)子任務(wù)在本地的子圖數(shù)據(jù)上進(jìn)行計(jì)算、通信、修改圖的狀態(tài)等操作，并行任務(wù)之間通過(guò)消息通信交流中間計(jì)算結(jié)果，不需要像MapReduce那樣對(duì)全體數(shù)據(jù)進(jìn)行復(fù)制。

迭代處理：MapReduce模型理論上需要連續(xù)啟動(dòng)若干作業(yè)才可以完成圖的迭代處理，相鄰作業(yè)之間通過(guò)分布式文件系統(tǒng)交換全部數(shù)據(jù)。BSP模型僅啟動(dòng)一個(gè)作業(yè)，利用多個(gè)超步就可以完成迭代處理，兩次迭代之間通過(guò)消息傳遞中間計(jì)算結(jié)果。由于減少了作業(yè)啟動(dòng)、調(diào)度開(kāi)銷和磁盤存取開(kāi)銷，BSP模型的迭代執(zhí)行效率較高。

數(shù)據(jù)分割：基于BSP的圖處理模型，需要對(duì)加載后的圖數(shù)據(jù)進(jìn)行一次再分布的過(guò)程，以確定消息通信時(shí)的路由地址。例如，各任務(wù)并行加載數(shù)據(jù)過(guò)程中，根據(jù)一定的映射策略，將讀入的數(shù)據(jù)重新分發(fā)到對(duì)應(yīng)的計(jì)算任務(wù)上（通常是放在內(nèi)存中），既有磁盤I/O又有網(wǎng)絡(luò)通信，開(kāi)銷很大。但是一個(gè)BSP作業(yè)僅需一次數(shù)據(jù)分割，在之后的迭代計(jì)算過(guò)程中除了消息通信之外，不再需要進(jìn)行數(shù)據(jù)的遷移。而基于MapReduce的圖處理模型，一般情況下，不需要專門的數(shù)據(jù)分割處理。但是Map階段和Reduce階段存在中間結(jié)果的Shuffle過(guò)程，增加了磁盤I/O和網(wǎng)絡(luò)通信開(kāi)銷。

MapReduce的設(shè)計(jì)初衷：解決大規(guī)模、非實(shí)時(shí)數(shù)據(jù)處理問(wèn)題。"大規(guī)模"決定數(shù)據(jù)有局部性特性可利用（從而可以劃分）、可以批處理；"非實(shí)時(shí)"代表響應(yīng)時(shí)間可以較長(zhǎng)，有充分的時(shí)間執(zhí)行程序。而B(niǎo)SP模型在實(shí)時(shí)處理有優(yōu)異的表現(xiàn)。這是兩者最大的一個(gè)區(qū)別。

BSP模型的實(shí)現(xiàn)

1.Pregel

Google的大規(guī)模圖計(jì)算框架，首次提出了將BSP模型應(yīng)用于圖計(jì)算，具體請(qǐng)看Pregel——大規(guī)模圖處理系統(tǒng)，不過(guò)至今未開(kāi)源。

2.Apache Giraph

ASF社區(qū)的Incubator項(xiàng)目，由Yahoo!貢獻(xiàn)，是BSP的java實(shí)現(xiàn)，專注于迭代圖計(jì)算（如pagerank，最短連接等），每一個(gè)job就是一個(gè)沒(méi)有reducer過(guò)程的hadoop job。

3.Apache Hama

也是ASF社區(qū)的Incubator項(xiàng)目，與Giraph不同的是它是一個(gè)純粹的BSP模型的java實(shí)現(xiàn)，并且不單單是用于圖計(jì)算，意在提供一個(gè)通用的BSP模型的應(yīng)用框架。

4.GraphLab

CMU的一個(gè)迭代圖計(jì)算框架，C++實(shí)現(xiàn)的一個(gè)BSP模型應(yīng)用框架，不過(guò)對(duì)BSP模型做了一定的修改，比如每一個(gè)超步之后并不設(shè)置全局同步點(diǎn)，計(jì)算可以完全異步進(jìn)行，加快了任務(wù)的完成時(shí)間。

5.Spark

加州大學(xué)伯克利分校實(shí)現(xiàn)的一個(gè)專注于迭代計(jì)算的應(yīng)用框架，用Scala語(yǔ)言寫就，提出了RDD（彈性分布式數(shù)據(jù)集）的概念，每一步的計(jì)算數(shù)據(jù)都從上一步結(jié)果精簡(jiǎn)而來(lái)，大大降低了網(wǎng)絡(luò)傳輸，同時(shí)保證了血統(tǒng)的純正性（即出錯(cuò)只需返回上一步即可），增強(qiáng)了容錯(cuò)功能。Spark論文里也基于此框架實(shí)現(xiàn)了BSP模型（叫Bagel）。值得一提的是國(guó)內(nèi)的豆瓣也基于該思想用Python實(shí)現(xiàn)了這樣一個(gè)框架叫Dpark，并且已經(jīng)開(kāi)源。https://github.com/douban/dpark

6.Trinity

這是微軟的一個(gè)圖計(jì)算平臺(tái)，C#開(kāi)發(fā)的，它是為了提供一個(gè)專用的圖計(jì)算應(yīng)用平臺(tái)，包括底層的存儲(chǔ)到上層的應(yīng)用，應(yīng)該是可以實(shí)現(xiàn)BSP模型的，文章發(fā)在SIGMOD13上，可恨的是也不開(kāi)源。主頁(yè)

7.GoldenOrb

另一個(gè)BSP模型的java實(shí)現(xiàn)，是對(duì)Pregel的一個(gè)開(kāi)源實(shí)現(xiàn)，應(yīng)用在hadoop上。
官網(wǎng)：（要FQ）
源碼：https://github.com/jzachr/goldenorb

8.Phoebus

Erlang語(yǔ)言實(shí)現(xiàn)的BSP模型，也是對(duì)Pregel的一個(gè)開(kāi)源實(shí)現(xiàn)。https://github.com/xslogic/phoebus

9.Rubicon

Pregel的開(kāi)源實(shí)現(xiàn)。https://launchpad.net/rubicon

10.Signal/Collect

也是一個(gè)Scala版的BSP模型實(shí)現(xiàn)。

11.PEGASUS

在hadoop上實(shí)現(xiàn)的一個(gè)java版的BSP模型，發(fā)表在SIGKDD2011上。~pegasus/index.htm

LogP模型

根據(jù)技術(shù)發(fā)展的趨勢(shì)，20世紀(jì)90年代末和未來(lái)的并行計(jì)算機(jī)發(fā)展的主流之一是巨量并行機(jī)，即MPC（Massively Parallel Computers），它由成千個(gè)功能強(qiáng)大的處理器/存儲(chǔ)器節(jié)點(diǎn)，通過(guò)具有有限帶寬的和相當(dāng)大的延遲的互連網(wǎ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模型和互連網(wǎng)絡(luò)的SIMD模型對(duì)開(kāi)發(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)網(wǎng)絡(luò)的性能特性，而不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用現(xiàn)實(shí)的消息傳遞操作進(jìn)行描述。

LogP模型是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通信的多處理機(jī)模型，其中通信網(wǎng)絡(luò)由4個(gè)主要參數(shù)來(lái)描述：

（1）L(Latency) 表示源處理機(jī)與目的處理機(jī)進(jìn)行消息（一個(gè)或幾個(gè)字）通信所需要的等待或延遲時(shí)間的上限，表示網(wǎng)絡(luò)中消息的延遲。

（2）o(overhead)表示處理機(jī)準(zhǔn)備發(fā)送或接收每個(gè)消息的時(shí)間開(kāi)銷（包括操作系統(tǒng)核心開(kāi)銷和網(wǎng)絡(luò)軟件開(kāi)銷），在這段時(shí)間里處理不能執(zhí)行其它操作。

（3）g(gap)表示一臺(tái)處理機(jī)連續(xù)兩次發(fā)送或接收消息時(shí)的最小時(shí)間間隔，其倒數(shù)即微處理機(jī)的通信帶寬。

（4）P(Processor)處理機(jī)/存儲(chǔ)器模塊個(gè)數(shù)

假定一個(gè)周期完成一次局部操作，并定義為一個(gè)時(shí)間單位，那么，L，o和g都可以表示成處理器周期的整數(shù)倍。

LogP模型的特點(diǎn)

(1)抓住了網(wǎng)絡(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ù)受限于通信帶寬和上下文交換的開(kāi)銷。VP受限于網(wǎng)絡(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ì)網(wǎng)絡(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ù)的上下文開(kāi)銷。