?BSP(Bulk Synchronous Parallel，整體同步並行)是壹種並行計算模式，由英國計算機科學家Viliant在上世紀80年代提出。BSP計算模式入下圖所示。
BSP計算模式中以下幾個概念需要了解壹下：
?在BSP模式的基礎上，我們詳細解釋壹下Pregel模型的原理。Pregel在概念模型上遵循BSP模式。整個計算過程由若幹順序運行的超級步（Super Step）組成，系統從壹個“超級步”邁向下壹個“超級步”，直到達到算法的終止條件。壹個典型的Pregel計算過程如下：
?在每個SuperStep中，頂點上的計算都是並行的，每個頂點執行相同的用於表達指定邏輯的用戶自定義函數。每個頂點都可以需修改自身以及出邊的狀態，接收前壹個SuperStep發送給它的消息，並將計算的結果或信息發送給其他頂點，這些信息會在下壹個SuperStep中被目標頂點接收。邊在這種計算模式中並不是核心對象，只用於表明消息傳遞的方向，沒有相應的計算運行在其上。詳細過程可以參考下圖，顯示了兩個SuperStep之間的內容。
?算法結束的時機取決於所有的頂點是否均已經達到halt狀態。首先在剛開始的時候，所有的頂點都處於active狀態，所有的active頂點都會參與到SuperStep中的相應計算。頂點通過將其自身的status設置成inactive來表示它已不再active，以此表明在下壹次的SuperStep中，該頂點不再需要執行相應的計算。除非該頂點接收到其他頂點傳送的消息，否則Pregel框架不會再接下來的SuperStep中執行該頂點的計算。如果頂點在接收到消息後進入active狀態，那麽在隨後的計算中該頂點必須顯式的deactive。整個計算在所有頂點都達到inactive狀態，並且沒有消息傳送時結束。整個狀態轉換如下圖所示。
?接下來展示壹個以Pregel計算最大值的例子。假設圖中存在A/B/C/D四個頂點，其中每個頂點的數據表示當前頂點的值。在計算的每個SuperStep中），每個頂點將接收其他頂點傳過來的值（初始SuperStep除外），並判斷當前頂點的值是否小於傳遞過來的值。若小於，更新當前頂點的值，並將該頂點狀態設置為active狀態，同時將當前頂點的最新值傳遞出去；若不小於，則什麽都不做，並將當前頂點的狀態設置為inactive。直到所有的頂點狀態均變成inactive，計算結束。整個過程入下圖所示。
以上圖為例，我們詳細介紹壹下Pregel模型的執行過程。
?以上就是圖計算模型Pregel的全部內容，以後有時間還會再詳細介紹其他幾種常見的圖計算模型，如GAS。具體實現可以參見 Flink Gelly 提供的叠代計算模式。
?Pregel模型雖然簡單，那就是對於鄰居數很多的頂點，它需要處理的消息非常龐大，所以對於符合冪律分布的自然圖，對於那些關聯關系非常多的頂點，這種模型在計算的時候很容易崩潰。