BSP模型

BSP模型

BSP(Bulk Synchronous Parallel，整體同步並行計算模型)是英國計算機科學家Viliant在上世紀80年代提出的一種並行計算模型。

基本介紹

  • 中文名：BSP模型
  • 外文名：Bulk Synchronous Parallel Computing Model
  • 全名：整體同步並行計算模型
  • 別名：大同步模型
背景及簡介,BSP模型,Hama的BSP實現原理,典型BSP程式,結語與展望,

背景及簡介

整體同步並行計算模型(Bulk Synchronous Parallel Computing Model，簡稱BSP模型)，又名大同步模型或BSP模型，由哈佛大學Viliant和牛津大學Bill McColl提出。
BSP的創始人是英國著名的計算機科學家Viliant，他希望像馮·諾伊曼體系結構那樣，架起電腦程式語言和體系結構間的橋樑，故又稱作橋模型(Bridge Model)。該模型使用了三個屬性描述：模組(Components)、選路器（Router）和同步路障器執行時間L。
BSP 模型最早作為一 個並行計算領域中軟體和硬體之間 的“ 過渡模型” 而提 出的。 它的設計目標是為 現有 和未來 可能出現的各種 並行體系結構提供一個獨立於具體體系結構、 具有可擴展並行性能的軟體開發的良好的理論模型基礎。
一個 BSP 並行計算機由一組通過通訊網路互連的處理器——記憶體單元組成。它主要有三個部分:
  • 一組具有局 部記憶體的分散式處理器;
  • 全局數據通訊 網路 ;
  • 支持所有處理單元間全局路障同步的機制。
BSP 模型 自Viliant提出後也經歷了一定的發展變化。最初的 BSP 模型山採用隨機記憶體映射和並行寬鬆度來支持直接的遠程記憶體訪問, 並且採用以L為間隔的周期性檢測來進行路障同步。 這一“ 跛腳 ” BSP模型被認為是對 PRAM 模型 不切實際的假設的改進。目前, 我們所討論 的 BSP 模型。, 一般不假設採用隨機記憶體映射來 實現共享記憶體, 每個超步結束後 由各個處理器執行路障同步原語進行全局同步，來代替周期性的同步檢測

BSP模型

BSP模型圖需要做以下解釋：1.Processors指的是並行計算進程，它對應到集群中的多個結點，每個結點可以有多個Processor；2.LocalComputation就是單個Processor的計算，每個Processor都會切分一些結點作計算；3.Communication指的是Processor之間的通訊。接觸的圖計算往往需要做些遞歸或是使用全局變數，在BSP模型中，對圖結點的訪問分布到了不同的Processor中，並且往往哪怕是關係緊密具有局部聚類特點的結點也未必會分布到同個Processor或同一個集群結點上，所有需要用到的數據都需要通過Processor之間的訊息傳遞來實現同步；4.BarrierSynchronization又叫障礙同步或柵欄同步。每一次同步也是一個超步的完成和下一個超步的開始；5.Superstep超步，這是BSP的一次計算疊代，拿圖的廣度優先遍歷來舉例，從起始結點每往前步進一層對應一個超步。6.程式該什麼時候結束呢？這個其實是程式自己控制，一個作業可以選出一個Proceessor作為Master，每個Processor每完成一個Superstep都向Master反饋完成情況，Master在N個Superstep之後發現所有Processor都沒有計算可做了，便通知所有Processor結束並退出任務。
BSP模型BSP模型

Hama的BSP實現原理

ApacheHama可以說是一個利用Hadoop的基礎設施自封裝的一個BSP計算模型的實現，它雖然跟Hadoop有關但是不使用Hadoop集群，而是用的自身的集群。依賴ZooKeeper分散式鎖作為作業的調度控制，可以用HDFS/Local/HBase等檔案系統作輸入輸出。
(一)基本結構
Hama的BSP實現原理Hama的BSP實現原理
S和Zookeeper都可以是獨立的集群。啟動從BSPMaster開始，如果是master會啟動BSPMaster、GroomServer兩個進程，如果只是計算結點則只會啟動GroomServer，啟動/關閉腳本都是Master機器遠程在GroomServer機器上執行。下面分別解釋下幾個基本概念：
  • BSPMaster即集群的主，負責了集群各GroomServer結點的管理與作業的調度，就我所知它還存在單點的問題。相當於Hadoop的JobTracker或HDFS的NameNode；
  • BSPGroomServer即計算結點，GroomServer是物理上的概念，也相當於是BSPPeer的宿主，負責了BSPPeer對外的訊息通訊、機器狀態報告等，相當於Hadoop的TaskTracker或HDFS的DataNode，在集群中往往和DataNode一一對應的部署（底層機制就是Hadoop的TaskTracker）；
  • BSPPeer即BSP中的Processor，當作業過來的時候，任務jar包和配置會被同步過來，GroomServer就啟動一個獨立JVM進程來執行一個BSPPeer實例，就像TaskTracker的作法一樣。BSPPeer是分散式計算中的邏輯計算單元；
  • BSPJobClient作業客戶端，職責是將作業所需jar以及配置提交給BSPMaster；
  • Zookeeper分散式鎖。用於實現BarrierSynchronisation機制。在ZK上，進入BSPPeer主要有進入Barrier和離開Barrier操作，所有進入Barrier的Peer會在zk上創建一個EPHEMERAL的node（/bsp/JobID/SuperstepNO./TaskID），最後一個進入Barrier的Peer同時還會創建一個readynode(/bsp/JobID/SuperstepNO./ready)，Peer進入阻塞狀態等待zk上所有task的node都刪除後退出Barrier。
(二)輸入與輸出
Hama的輸入輸出檔案格式、分塊、檔案傳輸等機制都跟HDFS是一樣的，也都是K-V對，派生自Writable。輸入的K-V對為結點（VertexWritable）和鄰接結點集合(VertexArrayWritable)。
(三)訊息通訊
圖計算涉及到大量訊息傳遞，Hama不完全是實時傳送，訊息的傳輸發生在Peer進入同步階段後，並且對同一個目標GroomServer的訊息進行了合併，兩個物理結點之間每一次超步其實只會發生一次傳輸。
BSPWW庫函式BSPWW庫函式
(四)圖算法運用
Hama其實只提供了一個圖計算框架，算法都是需要自己去實現的。理想的情況是圖檔案分塊，Peer盡可載入本地檔案作計算，這樣即加快了圖載入時間也減少了網路傳輸。不過事實是可能不能這樣假設，為使結構盡更簡單，對圖的切割往往只是將結點用簡單的Hash算法分布到Peer上，不能對圖作任何局部聚類的假設。

典型BSP程式

void spmd.start(int nprocs){    bsp_begin(nprocs);        printf("\nStarted%d out of%d.",bsp_pid(),bsp_nprocs());    bsp_end(); } int nprocs; void main() {     bsp_init(spmd_start);     nprocs=ReadInteger();     printf("\n Try to spawn%d BSP prcess",nprocs);          spmd_start (nprocs);     printf("I'm prcess%d",bsp_pid());  }

結語與展望

近年來,BSP模型的研究在國際上越來越受到人們 的重 視, 但是它 的研究尚處於起步階段。 相對於傳統串列計算,BSP 模型尚有許多問題有待進一步研究, 例如 BSP 程 序求精、程式變 換最佳化技術、 容錯性、 模組化問題 等。 作為一個獨立於體系 結構、 具有可擴展並行性能的並行程式模型,BSP模型無疑將 在並行計算領域具有重要意義。

相關詞條

熱門詞條

聯絡我們