整体同步并行计算模型

**整體同步並行計算模型**（Bulk Synchronous Parallel Computing Model），又名**大同步模型**或 **BSP 模型**，由哈佛大學萊斯利・瓦利安特提出，他希望像馮・諾伊曼體系結構那樣，架起電腦程式語言和體系結構間的橋梁，故又稱其為**橋接模型**（Bridging Model）。

## 歷史

BSP 是哈佛大學計算機科學家 Leslie Valiant 在 1980 年代開發的，決定性文章發表於 1990 年。

在 1990 年至 1992 年間，Leslie Valiant 在普林斯頓和哈佛，與牛津大學的 Bill McColl 致力於分布式內存 BSP 編程模型的工作。在 1992 年至 1997 年間，McColl 在牛津領導了一個大型研究組開發了各種 BSP 編程庫、語言和工具，還有多種大規模並行 BSP 算法。隨著興趣和勢頭的增長，McColl 接著領導了源自牛津、哈佛、佛羅里達、普利斯頓、貝爾實驗室、哥倫比亞和烏特勒支的一個組織為 BSP 編程開發並在 1996 年出版了 BSPlib 標準。

Valiant 在 2000 年代開發了 BSP 模型的一個擴展，在 2011 年出版為 Multi-BSP 模型。

在 2017 年，McColl 開發了 BSP 模型的一個主要新擴展，提供了在 AI、分析和 HPC 的大規模並行中的錯誤容忍和 tail 容忍。

## 模型

BSP 計算構成自：

1. 部件（component）：例如處理器，它們勝任處理及或局部內存事務，
2. 網絡：它在成對的這種部件之間路由消息，
3. 屏障（barrier）：它是允許所有或子集的部件進行同步化的硬體設施。

這通常解釋為可以跟進不同的計算執行緒的一組處理器，每個處理器配備了快速局部內存並用通信網絡互連起來。BSP 算法嚴重依賴第三個特徵；計算是在一系列的全局「超級步驟」中行進的，它由三部份構成：

1. 並發計算：所有參與處理器可以進行本地計算，就是說每個處理器只能利用在這個處理器的快速本地內存內存儲的數值。計算與所有其他計算異步發生但可以經由通信搭接（overlap）。
2. 通信：處理器相互之間交換數據來促成遠程數據存儲能力。
3. 同步：當一個處理器到達一個屏障點的時候，它一直等待到所有其他處理器也到達同樣這個屏障。

計算和通信活動不必須在時間上依次安排。通信典型的採用單邊的「put」和「get」直接遠程內存訪問（DRMA）調用的形式，而不用成對的雙邊「send」和「receive」消息傳遞調用。屏障同步化終結超級步驟：它確保所有單邊通信都正確終結。基於雙邊通信的系統於每次消息發送中隱式包含了這種同步化代價。屏障同步的方法依賴於 BSP 計算機的硬體設施。在 Valiant 的最初論文中，這個設施周期的檢查當前超級步驟的末端是否被全局性的到達了。這個檢查的周期指示為 $L$ 。

這個模型展示在右側的示意圖中。進程不被當作有特定的線性次序（從左至右或反之），並可以按任何方式映射到處理器。

BSP 模型通過對問題的超額分解和對處理器的超額認訂，還非常適合於對分布式內存計算啟用自動內存管理。計算被分開進入比實有的物理處理器更多的邏輯進程中，並且進程隨機的被指派到處理器。這種策略在統計上可以證實會導致最佳的負載平衡，對於工作和通信二者都是如此。

## 通信

在很多並行編程系統中，通信被認為是在個體行動的層面：發送和接收一個消息，內存到內存傳送等。這是難於共事的，因為在並行編程中會有很多同時通信行動，而它們的交互典型的是複雜的。特別是，難於說出任何單一通信行動要完成到底要得花多少時間。

BSP 模型認為通信行動是全體性的。這樣做的效果是可以給出一組數據通信要花費的時間的上限。BSP 把一個超級步驟的所有通信行動認作一個單元，並假定所有個體信息發送作為由固定大小的這個單元的一部份。

超級步驟的到來和外出信息的最大數目指示為 $h$ 。通信網絡遞送數據的能力通過參數 $g$ 來捕獲，定義一個處理器花費時間 $hg$ 來遞送大小為 1 的 $h$ 個消息。

發送長度 $m$ 的消息顯然要比大小為 1 的消息用時更長。但是，BSP 模型不區分長度 $m$ 的 1 個消息和長度 1 的 $m$ 個消息。在二者情況下代價都計為 $mg$ 。

參數 $g$ 依賴於下列因素：

* 在通信網絡內用來交互的協議。
* 處理器和通信網絡二者所做的緩衝區管理。
* 在網絡中使用的路由策略。
* BSP 運行時系統。

實際上，對於每個並行計算機 $g$ 的確定都是經驗性的。注意 $g$ 不是規格化（normalise）的單字遞送時間，而是在連續交通條件下的單字遞送時間。

## 屏障

BSP 模型的單邊通信要求屏障同步。屏障是潛在的有代價的，但是避免了死鎖或活鎖的可能性，因為不能建立循環的數據依賴。檢測並處理它們的工具是不需要的。

屏障同步的代價受到幾個要素的影響：

* 參與進來的並行計算的完成時間上的變化所施加的代價。舉例來說，除了一個之外的所有進程都完成了它們在這個超級步驟內的工作，並等待最後的那個進程，而它仍有很多工作要完成。一個實現能做的最好的事情是確保所有進程工作在大致相同的問題大小上。
* 所有處理器達到全局一致性狀態的代價。這依賴於通信網絡，但也依賴於是否有專門硬體用於同步化，並依賴於處理器處理中斷的方式。

屏障同步的代價指示為 $l$ 。注意如果 BSP 計算機的同步化機制是 Valiant 建議的那樣，則 $l<L$ 。實際上， $l$ 值的確定是經驗性的。

屏障在大型的計算機上是代價高昂的，並隨著更大的規模而逐漸增大。已有關於從現存算法中去除同步點的大量文獻，包括在 BSP 計算和此外的語境下。例如，很多算法允許對超級步驟的全局結束的局部檢測，簡單的通過將局部信息比較於已經收到了的消息的數目。相較於最小的要求的通信延遲，這驅使全局同步的代價可計為零。然而對將來的超級計算機架構和網絡互連，這個最小延遲預期還會進一步增加；BSP 模型，與其他並行計算模型一起，需要適應應對這種趨勢。Multi-BSP 是基於 BSP 的一種解決方案。

## BSP 算法的代價

超級步驟的代價確定自三項之和：最長的運行的局部計算的代價，在處理器之間全局通信的代價，和在超級步驟結束處屏障同步的代價。 $p$ 個處理器的超級步驟的代價是：

　
: $max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l$ ，

這裡的 $w_{i}$ 是進程 $i$ 中局部計算的代價，而 $h_{i}$ 是進程 $i$ 發送或接收的消息的數目。注意這裡假定了同構處理器。更常見的表達式寫為：

　
: $w+hg+l$ ，

這裡的 $w$ 和 $h$ 取了最大值。算法的代價是每個超級步驟的代價的總和：

　
: $W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl$ ，

這裡的 $S$ 是超級步驟的數目。 $W$ 、 $H$ 和 $S$ 通常建模為函數，隨著問題大小而變化。BSP 算法的這三個特徵通常採用漸進符號，比如 $H\in O(n/p)$ 。

## 其他特點

* 如果一個處理器至多可以接收 / 發送消息的數目是 h 條，那麼該模型就是「h-Relation」的。如果一個超級步中某個處理器的計算沒有完成，那麼下一個超級步就被分給該處理器繼續進行。
* 所有 PRAM 上的算法均可在 BSP 上模擬，每個 BSP 處理器所能模擬的 PRAM 數目即成為並行寬鬆度（Slackness）。
* BSP 放棄了程序局部性原理，從而簡化的程序與實現的設計。這一點在並行計算中往往是一個好的特點，注意到一個大規模的計算中可能需要很多處理器，但實際上我們卻不可能提供那麼多處理器，於是一個處理器可能會被映射到多個虛擬進程，此時，附帶的程序局部性原理反而會束縛處理器對存儲器的訪問。
* 選路器使用 P2P 的方式進行通信，從而有效的避免了網絡擁塞。

## 擴展和使用

對 BSP 的興趣近年來有所飆升，Google 通過 Pregel 這樣的技術，將它接受為大規模的圖分析的主要技術。還有就是新一代的 Apache Hadoop 將 MapReduce 模型與 Hadoop 下部構造的餘下部份拆解開來，現有活躍的開源項目在 Hadoop 頂上增加顯式的 BSP 編程，以及其他高性能並行編程模型，例如 Apache Hama 和 Apache Giraph。

BSP 已經被很多作者擴展來致力解決 BSP 在建模特定架構或計算范型上的不適合性。其中一個例子是可分解 BSP 模型。這個模型已經用於一些新建的程式語言和接口中，比如整體同步並行 ML（BSML）、BSPLib 、Apache Hama 和 Pregel。

BSPLib 標準的著名實現，是 Paderborn 大學 BSP 庫，和 Jonathan Hill 的牛津 BSP Toolset。現代實現包括：在消息傳遞接口頂上模擬 BSP 的 BSPonMPI，和以現代共享內存架構為目標的 MulticoreBSP。C 語言版 MulticoreBSP，特別知名於它的開啟嵌套 BSP 運行的能力，從而允許顯式的 Multi-BSP 編程。

## 參閱

* 並行編程模型
* 同步屏障

## 引用

## 外部連結

* BSP Worldwide （頁面存檔備份，存於網際網路檔案館）
* BSP related papers （頁面存檔備份，存於網際網路檔案館）
* BSML official website （頁面存檔備份，存於網際網路檔案館）
* Paderborn University BSP library
* BSPonMPI （頁面存檔備份，存於網際網路檔案館）
* MulticoreBSP （頁面存檔備份，存於網際網路檔案館）