傳統計算機是串列結構，每一時刻只能按一條指令對一個數據進行操作，在傳統計算機上設計的算法稱為串列算法。並行算法是用多台處理器聯合求解問題的方法和步驟，其執行過程是將給定的問題首先分解成若干個儘量相互獨立的子問題，然後使用多台計算機同時求解它，從而最終求得原問題的解。
基本介紹
- 中文名：並行運算器
- 外文名：Parallel arithmetic
- 定義：多台處理器聯合求解問題的方法
- 分類：PRAM模型和BSP模型
- 系統：計算機
- 學科：計算機技術
概述,模型,
概述
傳統計算機是串列結構，每一時刻只能按一條指令對一個數據進行操作，在傳統計算機上設計的算法稱為串列算法。並行算法是用多台處理器聯合求解問題的方法和步驟，其執行過程是將給定的問題首先分解成若干個儘量相互獨立的子問題，然後使用多台計算機同時求解它，從而最終求得原問題的解。
為利用並行運算，通常計算問題表現為以下特徵：
(1)將工作分離成離散部分，有助於同時解決。例如，對於分治法設計的串列算法，可以將各個獨立的子問題並行求解，最後合併成整個問題的解，從而轉化為並行算法；
(2)隨時並及時地執行多個程式指令；
(3)多計算資源下解決問題的耗時要少於單個計算資源下的耗時。
模型
並行運算模型通常是指從並行算法的設計和分析出發，將各種並行運算機(至少某一類並行運算機)的基本特徵抽象出來，形成一個抽象的計算模型。從更廣的意義上說，並行運算模型為並行運算提供了硬體和軟體界面，在該界面的約定下，並行系統硬體設計者和軟體設計者可以開發對並行性的支持機制，從而提高系統的性能。
並行算法設計是基於並行運算模型的，下面簡要介紹目前常見的兩種並行運算模型。
1．PRAM模型
PRAM(Parallel Random Access Machine，隨機存取並行機器)模型，也稱為共享存儲的SIMD(單指令流多數據流)模型，是一種抽象的並行運算模型，它是從串列的RAM模型直接發展起來的。在這種模型中，假定有一個無限大容量的共享存儲器，並且有多個功能相同的處理器，且它們都具有簡單的算術運算和邏輯判斷功能，在任意時刻各個處理器可以訪問共享存儲單元。
2．BSP模型
BSP(Bulk Synchronous Parallel，整體同步並行)模型是個分布存儲的MIMD(多指令流多數據流)計算模型，由哈佛大學的Viliant和牛津大學的Bill McColl提出。
一台BSP計算機由”個處理器/存儲器(節點)組成，通過通信網路進行互聯。
一個BSP程式有理個進程，每個駐留在一個節點上，程式按嚴格的超步(可以理解為並行運算中子問題的求解)順序執行．如圖4．11所示，超步問採用路障同步，每個超步分成如下有序的3個部分。
(1)計算：一個或多個處理器執行若干局部計算操作，操作的所有數據只能是局部存儲器中的數據。一個進程的計算與其他進程無關。
(2)通信：處理器之間的相互交換數據，通信總是以點對點的方式進行。
(3)同步：確保通信過程中交換的數據被傳送到目的處理器上，並使一個超步中的計算和通信操作必須全部完成之後，才能開始下一個超步中的任何動作。
BSP模型總的執行時間等於各超步執行時間之和。
圖1