維基百科

整體同步並行

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

一個BSP超級步驟。進程缺乏線性次序並且可以按任何方式映射到處理器。

歷史

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

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

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

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

模型

BSP計算機構成自：

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

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

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

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

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

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

通信

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

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

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

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

參數 依賴於下列因素：

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

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

屏障

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

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

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

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

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

BSP算法的代價

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

 ，

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

 ，

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

 ，

這裡的 是超級步驟的數目。 、 和 通常建模為函數，隨著問題大小而變化。BSP算法的這三個特徵通常採用漸進符號，比如 。

其他特點

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

擴展和使用

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

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

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

參閱

引用

  1. ^ 1.0 1.1 1.2 Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, Volume 33 Issue 8, Aug. 1990 [1]
  2. ^ 2.0 2.1 Valiant, L. G. (2011). A bridging model for multi-core computing （頁面存檔備份，存於網際網路檔案館）. Journal of Computer and System Sciences, 77(1), 154-166 [2]
  3. ^ A Bridging Model for High Performance Cloud Computing by Bill McColl in 18th SIAM Conference on Parallel Processing for Scientific Computing (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 （頁面存檔備份，存於網際網路檔案館）.
  4. ^ Alpert, R., & Philbin, J. (1997). cBSP: Zero-cost synchronization in a modified BSP model. NEC Research Institute, 4 Independence Way, Princeton NJ, 8540, [3] （頁面存檔備份，存於網際網路檔案館）.
  5. ^ 5.0 5.1 Apache Hama. [2019-12-11]. （原始內容存檔於2021-03-08）. 
  6. ^ BSML: Bulk Synchronous Parallel ML. [2023-02-15]. （原始內容存檔於2022-10-17）. 
  7. ^ BSPlib. [2019-12-11]. （原始內容存檔於2020-02-22）. 
  8. ^ Pregel. [2019-12-11]. （原始內容存檔於2019-02-14）. 
  9. ^ The Paderborn University BSP (PUB) Library - Design, Implementation and Performance Heinz Nixdorf Institute, Departement of Computer Science, University of Paderborn, Germany, technical report （頁面存檔備份，存於網際網路檔案館）.
  10. ^ Jonathan Hill: The Oxford BSP Toolset （頁面存檔備份，存於網際網路檔案館）, 1998.
  11. ^ Wijnand J. Suijlen: BSPonMPI （頁面存檔備份，存於網際網路檔案館）, 2006.
  12. ^ MulticoreBSP for C: a high-performance library for shared-memory parallel programming by A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen in International Journal of Parallel Programming, in press (2013), doi:10.1109/TPDS.2013.31.
  13. ^ An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming by A. N. Yzelman & Rob H. Bisseling in Concurrency and Computation: Practice and Experience 24(5), pp. 533-553 (2012), doi:10.1002/cpe.1843

外部連結


取自「https://zh.wikipedia.org/w/index.php?title=整体同步并行&oldid=81888841」