檢視整體同步並行的原始碼

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

==歷史==

BSP 是哈佛大學計算機科學家 Leslie Valiant 佇一九八空年代開發的，決定性文章發表佇一九九空年。

佇一九九空年至一九九二年間，Leslie Valiant 佇咧普林斯頓佮哈佛，佮牛津大學的 Bill McColl 致使分布式內存 BSP 編程模型的工課。佇咧一九九二年至一九九七年間，McColl 咧牛津領導一个大型的研究組開發矣各種 BSP 編程庫、語言佮工具，閣有偌種大規模並行 BSP 算法。隨著興趣佮勢頭的增長，McColl 來領導著源自牛津、哈佛、佛羅里達、普利斯頓、貝爾實驗室、哥倫比亞佮烏特勒支的一个組織為 BSP 編程開發並佇一九九六年出版矣 BSPlib 標準。

Valiant 佇二空空年代開發矣 BSP 模型的一个擴展，佇二空一一年出版做 Multi-BSP 模型。

佇二零一七年，McColl 開發矣 BSP 模型的一个主要新擴展，提供矣佇 AI、分析佮 HPC 的大規模並行中的錯誤容忍和 tail 吞忍。

==模型==

BSP 計算構成自：

一 . 部件（component）： 比如講處理器，𪜶勝任處理佮局部內存事務，
二 . 網路：伊咧成對的這種部件之間路由消息，
三 . 屏障（barrier）： 伊是允准所有或者是固定的部件來進行仝步化的硬體設施。

這通常解說為會當佮進無仝的計算執行緒的一組處理器，逐个處理器配備快速局部內存閣用通信網路互相連起來。BSP 算法嚴重依賴第三个特徵；計算是一系列的全局「超級步驟」中行的，伊由三部份構成：

一 . 並且發計算：所有參與處理器會當進行本地計算，就是講逐个處理器干焦會當利用佇這个處理器的快速本地內存內存儲的數值。計算佮所有其他的計算異步發生但是會當經過通信來接（overlap）。
二 . 通批：處理器互相之間交換數據來促成遠程數據存儲能力。
三 . 仝步：做一个處理器到位一个屏障點的時陣，伊一直等待到所有的處理加上仝款這个屏障。

計算佮通信活動毋免佇咧時間上依次安排。通信用的採用單爿的「put」和「get」直接遠程內底訪問（DRMA）調用的形式，毋免成對的雙爿「send」和「receive」消息傳達調用。屏障仝步化終結超級步驟：伊確保所有的單爿通信攏正確尾結。是因為雙爿通信的系統佇每改消息發送中隱式包含這款同步化代價。屏障仝步的方法依賴佇咧 BSP 計算機的硬體設施。佇咧 Valiant 的上蓋初論文中，這个設施周期的檢查當前超級步數的尾溜敢是予全局性地的有達到。這个檢查的周期指示講 $ L $。

這个模型展示佇正爿的示意圖內底。進程袂當做有特定的線性次序（對倒爿至正爿抑是反爿）， 並且會當按任何方式影射著處理器。

BSP 模型通過對問題的超額分解佮對處理器的超額認訂，猶閣有真適合對分布式內存計算啟用自動內存管理。計算予分開進入比實有的物理處理器閣較濟的邏輯進程當中，而且進程隨機的被指派到處理器。這款策略佇統計上會當證實會致使最佳的負載平衡，對著工課佮通信二者攏是按呢。

==通批==

佇足濟而且編程系統當中，通批被認為是講佇咧個體行動的層面：發送佮接收一个消息，內存到內存傳送等等。這是歹做的共，因為佇咧並行編程當中會有足濟同時通信行動，啊若𪜶的交互典型的是複雜的。特別是，真歹講出任何單一通批行動欲完成到底愛愛開偌濟時間唅。

BSP 模型認為通信行動是全體性的。按呢做的效果是會當予出一組數據通批欲開的時間的上限。BSP 共一个超級步驟的所有通信行動認作一个單元，兼假定所有一个體信息來發送作為由固定的大細的這个單元的一部份。

有夠步驟的到來佮出外信息的上大數目指示 $ h $。通批網路送數據的能力通過參數 $ g $ 來掠著，定義一个處理器開了時間 $ hg $ 來遞送大細為一的 $ h $ 一个消息。

發送長度 $ m $ 的消息顯然愛比大細為一的消息用的時更加長。猶毋過，BSP 模型無區分長度 $ m $ 的一个消息佮長度一的 $ m $ 一个消息。二者的情況下代價攏計為 $ mg $。

參數 $ g $ 依賴佇下列的因素：

* 佇通信網路內底用來交陪的協議。
* 處理器佮通信網路二者所做的緩衝區管理。
* 佇網路內底使用的路由策略。
* BSP 運行的時系統。

實際上，對每一个並行計算機 $ g $ 確定攏是經驗性的。注意 $ g $ 毋是規格化（normalise）的單字遞送時間，是咧連紲交通條件下的單字遞送時間。

==屏障==

BSP 模型的單邊通批要求屏障仝步。屏障是藏佇的有代價的，但是避免死鎖或者是活鎖的可能性，因為袂當建立循環的數據依賴。檢測並且處理𪜶的工具是無需要的。

屏障仝步的代價受著幾个欲素的影響：

* 參與入來的並行計算的完成時間上的變化所施加的代價。比如講伊，除了一个以外的所有進程攏完成矣𪜶佇咧這个超級步內底的工課，並等待最後的彼个進程，伊猶是有真濟工課愛做完成。一个實現會當做的上好的代誌嘿確保所有進程工課佇大概仝款的問題大細上。
* 所有處理器達到全局一致性狀態的代價。這依賴佇通信網路，但是嘛依賴敢有專門硬體用仝步化，閣依賴佇咧處理器處理斷去的方式。

屏障仝步的代價指示為 $ l $。注意若 BSP 計算機的同步化機制是 Valiant 建議的按呢，著 $ l < L $。實際上，$ l $ 值的確定是經驗性的。

屏障佇大型的計算機頂懸會是代價衝甲掠袂牢，並且隨著閣較大的規模才來漸漸增加。已經有關於對現存算法中去除仝步點的大量文獻，包括佇 BSP 計算佮此外的語境之下。比如講，誠濟算法允准對超級步數的全局結束的局部檢測，簡單的通過將局部信息比已經收著的消息的數目。佮上細漢的要求的通信延遲，這個驅使全局同步的代價還有辦。毋過對將來的超級計算機架構佮網路相連紲，這个上細漢延遲預期閣會進一步增加；BSP 模型，佮其他並行計算模型做伙，需要適應對這種趨勢。Multi-BSP 是因為 BSP 的一種解決方案。

==BSP 算法的代價==

超級步數的代價確定自三項之和：上長的運行的局部計算的代價，佇咧處理器之間全局通信的代價，佮佇咧超級步數結束處屏障仝步的代價。$ p $ 一个處理器的有夠步數的代價是：


: $ max _ { i=一 } ^ { p } ( w _ { i } ) + max _ { i=一 } ^ { p } ( h _ { i } g ) + l $，

遮的 $ w _ { i } $ 這是進程 $ i $ 中局部計算的代價，而且 $ h _ { i } $ 這是進程 $ i $ 發送抑是接收的消息的數目。注意遮假定了仝構處理器。閣較捷看著的表達式來寫：


: $ w + hg + l $，

遮的 $ w $ 和 $ h $ 號上大值。算法的代價是每一个超級步數的代價的總和：


: $ W + Hg + Sl=\ sum _ { s=一 } ^ { S } w _ { s } + g \ sum _ { s=一 } ^ { S } h _ { s } + Sl $，

遮的 $ S $ 是超級步驟的數目。$ W $、$ H $ 和 $ S $ 通常起模做函數，隨著問題大細來變化。BSP 算法的這三个特徵通常採用漸漸進符號，比如講 $ H \ in O ( n / p ) $。

==其他的特色==

* 若是一个處理加減會使接收 / 發送消息的數目是 h 條，遐爾仔該模型就是「h-Relation」的。若是一个超級步內底某一个處理器的計算無完成，按呢後一个超級步就被分予該處理器繼續進行。
* 所有 PRAM 上的算法攏會佇咧 BSP 上模擬，彼每一个 BSP 處理器所會當模擬的 PRAM 數目就成做並行寬鬆度（Slackness）。
* BSP 放棄矣程序局部性原理，對而且簡化的程序佮實現的設計。這點佇咧並行計算中往往是一个好的特點，注意著一个大規模的計算中可能需要足濟處理器，毋過實際上阮煞無可能提供遐爾濟處理器，所以一个處理器可能會去予影射著濟濟的虛擬進程，現此時，附帶的程序局部性原理顛倒會束縛處理器對存儲器的訪問。
* 選路器使用 P 二 P 的方式進行通信，對咧有效的避免網路窒起來。

==擴展佮使用==

著 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

[[分類: 待校正]]