整體同步並行計算模型(Bulk Synchronous Parallel Computing Model)，又名大同步模型或BSP模型，由哈佛大學Viliant和牛津大學Bill McColl提出。BSP的創始人是英國著名的計算機科學家Valiant，他希望像馮·諾伊曼體系結構那樣，架起電腦程式語言和體系結構間的橋樑，故又稱作橋模型(Bridge Model)。該模型使用了三個屬性描述：模組(Components)、選路器（Router）和同步路障器執行時間。
基本介紹
- 中文名：整體同步並行計算模型
- 外文名：Bulk Synchronous Parallel Computing Model
- 學科：計算機科學
- 別名：BSP模型
- 提出者：Viliant
- 屬性描述：模組、選路器、路障器執行時間
定義,特點,參數,有關術語,
定義
整體同步並行計算模型（BSP模型）是由美國 Havard 大學的 L.G.Valiant教授在 1992 年作為一種並行計算模型提出的。BSP模型類似於一個並行隨機存取模型，與之不同的是，他並不強調通信和同步。分析一個BSP算法的重要部分在於量化同歩和通信的需求。BSP模型把並行計算抽象為H個模組：處理器集合、傳送訊息的全局通訊網路、各處理器間的路障同步機制。BSP模型中並行計算的基本執行單元是超級步。一個BSP程式包含多個超級步，通過訊息機制實現超級步中各個計算任務間的信息傳遞。在各超級步中，每個處理器均執行本地計算，並通過選路器接收和傳送訊息；然後進行全局檢查，確定所有的處理器是否都己經完成該超級步；若是，則進入到下一超級步，否則下一個周期被分配給未完成的超級步。BSP模型疊代執行每一個超級步直到滿足終止條件或者達到一定的超級步數強制終止。每一個超級步由本地計算，全局通信和路障同步蘭個階段組成。一個BSP程式通常有n個任務並行執行，一個處理器（計算節點）上存在若干個並行執行的任務，任務由若干個順序執行的超級步組成。
特點
整體同步並行計算模型主要有以下幾個特點：
- 創新的給出超步的概念，每一個超步均代表 BSP 模型中一次完整的並行計算過程，整個運算過程包含若干個串列超步，超步包含本地計算過程、運算節點間通訊過程和同步過程。超步中的三個階段是嚴格串列的，即所有處理機本地計算結束後統一進行通訊過程，最後執行同步階段。除此之外，每個運算單元在一個超步內只能傳遞或接收一次數據。該模型的實現中，所有的處理機 processor 節點由一個 Master 節點進行協調，來完成上述三個階段。
- BSP放棄了程式局部性原理，從而簡化的程式與實現的設計。這一點在並行計算中往往是一個好的特點，注意到一個大規模的計算中可能需要很多處理器，但實際上我們卻不可能提供那么多處理器，於是一個處理器可能會被映射到多個虛擬進程，此時，附帶的程式局部性原理反而會束縛處理器對存儲器的訪問。
- 選路器使用P2P的方式進行通信，從而有效的避免了擁塞。BSP模型將處理器和路由器分開，即將汁算任務和通信任務分開。路由器僅僅完成點到點的訊息傳遞，並不提供組合、複製和廣播等功能，這樣做既掩蓋了互連網的具體拓撲結構，又簡化了通信協定。採用路障同步的方式實現的全局同步是在可控的粗粒度級別，從而提供了一種有效的方式執行緊耕契約步式並行算法，而程式設計師並不需要太多的負擔。
參數
BSP 模型包括以下四個主要參數：
- L：時間周期（period）
- g：路由（router）的吞吐量，即訊息傳送或接收所需時間
- p：物理處理器數量
- v：虛擬處理器數量
每經過L時間，Master 節點就會檢查超步內所有處理機上的任務是否已經執行完畢。如果均執行結束，就開始下一個超步過程或結束程式的運行；如果沒有結束，就會申請另一個L周期，直到所有任務都執行完畢。通常，時間周期L可以看作兩個連續超步間最小的時間間隔。軟體層面和硬體層面對時間周期的要求正好相反，軟體層面要求時間周期L大一些，這樣在編程過程中方便實現擴展性；而硬體方面則要求時間周期L儘可能的小，以提升執行的效率。為了提高處理器利用率，設計程式時應使每個超步內所有處理器的處理時間儘可能接近 L，使得每個運算單元完成自己的任務後不必長時間等待其他運算單元，儘快開始執行下一超步的任務。
通常路由網路傳遞訊息具有 h-relation 限制，即每個組件最多接收或傳送 h 條訊息。h-relation 限制是對通訊過程的抽象描述，假設每個處理機最多傳送 out 個訊息到其他處理機，且每個處理機最多從其他處理機接收 in 個訊息，那么 h-relation 限制可以描述為ℎ = 𝑜𝑢𝑡 @ 𝑖𝑛，其中@表示一種二維運算，通常為取最大值操作和加法操作。傳統BSP 模型的超步中，嚴格遵循計算階段在前，通訊階段在後的順序，並且障礙同步階段是阻塞的。所以，相鄰超步間是嚴格串列的。Rodrı́guez C 等人給出了“異步超步”（A-BSP）的概念，即去除超步內的障礙同步階段，使多個超步之間可以異步運行，從而提升整個程式的並行程度以及運算單元的利用率。但是，該模型中超步結束之後需要進行阻塞式通訊，這樣就隱含了一個同步過程。
有關術語
本地計算；一個或多個處理器參與本地計算。計算發生在每一個參與計算的節點上，每個節點只使用存儲在本地存儲器上的數據，該些數據是在程式啟動時載入數據階段或上一個超級步的全局通信時放在本地存儲器上的數據。每台處理器上的計算是獨立的，從這個意義上看節點間的執行是異步的。
全局通信；某個處理器向其他處理器發出通信請求，每個處理器傳送或等待訊息。訊息在節點之間進行交換。這種交換是單方面的以點對點的方式進行的。
路障同步；當一個任務執行完本地計算到達同步點時，它會等待其他所有的任務完成計算。本超級步中所有的數據通信在本次同步後生效，並提供給下一個超級步使用。當所有的通信結束後，確保每個處理器均執行完當前超級步中所有的計算和通信，並且通信過程中各處理器間的數據交換均已完成，然後進入到下一輪疊代。這種同步方式可避免死鎖和數據競爭問題。
