并行計算綜述

1、什么是并行計算并行計算(parallel computing )是指，在并行機上，將一個應用分解成多個子任務，分配給 不同的處理器，各個處理器之間相互協(xié)同，并行地執(zhí)行子任務，從而達到加速求解速度， 或者增大求解應用問題規(guī)模的目的。由此，為了成功開展并行計算，必須具備三個基本條件：(1) 并行機。并行機至少包含兩臺或兩臺以上處理機，這些處理機通過互連網(wǎng)絡相互連接， 相互通信。(2) 應用問題必須具有并行度。也就是說，應用可以分解為多個子任務，這些子任務可以并 行地執(zhí)行。將一個應用分解為多個子任務的過程，稱為并行算法的設計。(3) 并行編程。在并行機提供的并行編程環(huán)境上，具體實現(xiàn)并行算法，編制并行

2、程序，并運 行該程序，從而達到并行求解應用問題的目的。problemIiiiniiiii 111tNDt2t1probleminstnictlonB-K i I并行計算的主要研究目標和內(nèi)容對于具體的應用問題，采用并行計算技術的主要目的在于兩個方面:(1) 加速求解問題的速度。(2) 提高求解問題的規(guī)模。組成并行機的三個要素為：?結點(node)。每個結點由多個處理器構成，可以直接輸入輸出(I/O)互聯(lián)網(wǎng)絡(interconnect network)。所有結點通過互聯(lián)網(wǎng)絡相互連接相互通 信。? 內(nèi)存（ memory ）。內(nèi)存由多個存儲模塊組成，這些模塊可以與結點對稱地分 布在互聯(lián)網(wǎng)絡的兩側，或者

3、位于各個結點的內(nèi)部。并行編程模型1.共享內(nèi)存模型a）在共享編程模型中，任務間共享統(tǒng)一的可以異步讀寫的地址空間。b）共享內(nèi)存的訪問控制機制可能使用鎖或信號量。c）這個模型的優(yōu)點是對于程序員來說數(shù)據(jù)沒有身份的區(qū)分，不需要特別清楚任務間的單數(shù)據(jù)通信。程序開發(fā)也相應的得以簡化。d）在性能上有個很突出的缺點是很難理解和管理數(shù)據(jù)的本地性問題。2. 線程模型在并行編程的線程模型中，單個處理器可以有多個并行的執(zhí)行路徑。3. 消息傳遞模型消息傳遞模型有以下三個特征：1）計算時任務集可以用他們自己的內(nèi)存。多任務可以在相同的物理處理 器上，同時可以訪問任意數(shù)量的處理器。2）任務之間通過接收和發(fā)送消息來進行數(shù)據(jù)通信。

4、3）數(shù)據(jù)傳輸通常需要每個處理器協(xié)調操作來完成。例如，發(fā)送操作有一個 接受操作來配合。4. 數(shù)據(jù)并行模型數(shù)據(jù)并行模型有以下特性： 并行工作主要是操縱數(shù)據(jù)集。數(shù)據(jù)集一般都是像數(shù)組一樣典型的通用的數(shù) 據(jù)結構。任務集都使用相同的數(shù)據(jù)結構，但是，每個任務都有自己的數(shù)據(jù)。每個任務的工作都是相同的，例如，給每個數(shù)組元素加 4。在共享內(nèi)存體系結構上，所有的任務都是在全局存儲空間中訪問數(shù)據(jù)。在 分布式存儲體系結構上數(shù)據(jù)都是從任務的本地存儲空間中分離出來的基于消息傳遞的并行計算環(huán)境在當前并行機上，比較流行的并行編程環(huán)境可以分為三類：消息傳遞、共 享存儲和數(shù)據(jù)并行，它們的典型代表、可移植性、并行粒度、并行操作方式、

5、 數(shù)據(jù)存儲模式、數(shù)據(jù)分配方式、學習難度、可擴展性等方面的比較如下：(1) 共享存儲并行編程基于線程級細粒度并行，僅被 SMP和DSM并行機所 支持，可移植性不如消息傳遞并行編程。但是，由于它們支持數(shù)據(jù)的共享存儲， 所以并行編程的難度較小，但一般情形下，當處理機個數(shù)較多時，其并行性能 明顯不如消息傳遞編程。(2) 消息傳遞并行編程基于大粒度的進程級并行，具有最好的可移植性，幾 乎被當前流行的各類并行機所支持，且具有很好的可擴展性。但是，消息傳遞 并行編程只能支持進程間的分布存儲模式，即各個進程只能直接訪問其局部內(nèi) 存空間，而對其他進程的局部內(nèi)存空間的訪問只能通過消息傳遞來實現(xiàn)。因此， 學習和使用

6、消息傳遞并行編程的難度均大于共享存儲和數(shù)據(jù)并行兩種編程模 式。三種并行編程環(huán)境主要特征一覽表特征消息傳遞共享存儲數(shù)據(jù)并行典型代表MPI 、PVMOpenMPHPF可移植性所有流行并行SMP、DSMSMP 、 DSM 、機MPP并行粒度進程級大粒度線程級細粒進程級細粒度度并行操作方式l=L異步l=L異步松散同步數(shù)據(jù)存儲模分布式存儲共享存儲共享存儲式數(shù)據(jù)分配方式顯式隱式半隱式式學習入門難較難容易偏易度可擴展性好t 、/.較差一般本書的主要目的是全面介紹消息傳遞并行編程環(huán)境 MPI，因此，在以后的篇幅中，將不再討論共享存儲和數(shù)據(jù)并行編程環(huán)境。1. 消息傳遞并行機模型由于當前流行的各類 SMP、DSM

7、、MPP 和微機機群等并行機均支持消息 傳遞并行程序設計，因此，有必要對這些具體并行機的體系結構進行抽象，設 計一個理想的消息傳遞并行機模型?；谠撃Ｐ?，用戶可以在不考慮具體并行 機體系結構的條件下，組織消息傳遞并行程序設計，從而簡化并行程序設計， 增強程序的可移植性。圖1.1給出了一個理想的消息傳遞進程拓撲結構。其中，“ P”表示MPI進 程，“ M ”表示每個進程的局部內(nèi)存空間，多個“ P/M ”進程/內(nèi)存模塊通過互 聯(lián)網(wǎng)絡相互連接，構成一個分布式存儲的進程拓撲結構。在該結構中，各個進程之間可以直接通信，但是各個進程只能直接訪冋自身的局部內(nèi)存空間，對其 他進程的局部內(nèi)存空間的訪問只能調用消

8、息傳遞函數(shù)，通過進程間通信才能實 現(xiàn)。因此，該進程拓撲結構的核心是連接進程的互聯(lián)網(wǎng)絡和消息傳遞標準函數(shù) 庫，構成該函數(shù)庫的所有函數(shù)就構成了用戶面對的消息傳遞并行編程環(huán)境?；ヂ?lián)網(wǎng)絡消總傳送函數(shù)炸互聯(lián)網(wǎng)絡消總傳送函數(shù)炸I P/M圖1.1消息傳遞進程拓撲結構和并行機模型如果將圖1.1的每個P/M模塊替換成處理器，且規(guī)定每個處理器只能分配 用戶程序的一個進程，則所得的理想并行機模型就是消息傳遞并行機模型。不 難看出，消息傳遞并行程序設計所依賴的并行機模型實際上屬于典型的分布式 存儲并行機，且每臺處理器只能分配用戶程序的一個進程?；谠摬⑿袡C模型， 用戶可以自由地調用消息傳遞函數(shù)庫中的函數(shù)來組織具體的并

9、行程序設計，且 程序研制成功后，便可以在任何支持該并行機模型隱含的進程拓撲結構的所有 具體并行機上運行。這里，有必要說明的是，消息傳遞分布式存儲并行機模型和具體并行機體 系結構沒有必然的聯(lián)系。無論將該模型映射到何種類型的并行機（SMP、DSM、cluster、constellation MPP），用戶面對的都是該模型隱含的進程拓撲結構， 只是各類具體并行機實現(xiàn)的消息傳遞函數(shù)庫的方式不同，但用戶無須知道這些 細節(jié)。例如，在共享存儲SMP、DSM并行機中，消息傳遞是通過共享數(shù)據(jù)緩存 區(qū)來實現(xiàn)的；在MPP并行機中，消息傳遞是通過網(wǎng)絡通信來實現(xiàn)的；在機群和 星群并行機中，消息傳遞在SMP、DSM并行機

10、內(nèi)部是通過共享數(shù)據(jù)緩存區(qū)實現(xiàn) 的，而在SMP、DSM并行機之間是通過網(wǎng)絡通信來實現(xiàn)的。因此，無論哪種類 型的具體并行機，呈現(xiàn)在消息傳遞并行程序設計用戶面前的必然是分布式存儲 并行機模型。2. 標準消息傳遞界面MPI佃94年6月，全球工業(yè)、政府和科研應用部門聯(lián)合推出消息傳遞并行編程 環(huán)境的標準用戶界面（MPI ），它將消息傳遞并行編程環(huán)境分解為兩個部分，第 一是構成該環(huán)境的所有消息傳遞函數(shù)的標準接口說明，它們是根據(jù)并行應用程 序對消息傳遞功能的不同要求而制定的，不考慮該函數(shù)能否具體實現(xiàn)；第二是 各并行機廠商提供的對這些函數(shù)的具體實現(xiàn)。這樣，用戶只需學習 MPI 庫函數(shù) 的標準接口，設計MPI并行

11、程序，便可在支持MPI并行編程環(huán)境的具體并行機 上執(zhí)行該程序。通常意義下所說的 MPI 系統(tǒng)就是指所有這些具有標準接口說明 的消息傳遞函數(shù)所構成的函數(shù)庫。在標準串行程序設計語言(C、Fortran、C+ )的基礎上，再加入實現(xiàn)進程 間通信的 MPI 消息傳遞庫函數(shù)， 就構成了 MPI 并行程序設計所依賴的并行編程 環(huán)境。 MPI 吸收了眾多消息傳遞系統(tǒng)的優(yōu)點，例如P4、 PVM 、 Express、PARMACS 等，是目前國內(nèi)外最流行的并行編程環(huán)境之一。當前，大量工業(yè)、 科學與工程計算部門(例如氣象、石油、地震、空氣動力學、核物理等)的科 研與工程軟件已經(jīng)移植到 MPI 平臺。MPI 是一個

12、消息傳遞接口的標準， 用于開發(fā)基于消息傳遞的并行程序， 其目 的是為用戶提供一個實際可用的、可移植的、高效的和靈活的消息傳遞接口。MPI 這個名稱包括三個方面的含義：(1) MPI 是一個庫， 而不是一種語言。 許多人認為 MPI 是一種并行設計語言，這種看法并不準確。按照并行語言的分類，可以把 Fortran+MPI 、 C+MPI 看做 是在原來的串行語言基礎之上擴展而來的并行語言。 MPI 庫可以和具體語言進行 綁定，形成并行設計語言。從語法上說，C/C十+和Fortran等語言對MPI庫的調用規(guī)則，與調用一般的函數(shù) /過程沒有區(qū)別；(2) MPI 是一種標準或者規(guī)范，而不特指某一個對它

13、的具體實現(xiàn)。到目前為 止，所有的并行計算機都提供對MPI的支持，用MPI書寫的并行程序可以不加修 改的在所有并行機上運行；(3) MPI 是一種消息傳遞編程模型，并且成為了這種編程模型的代表和事實 上的標準。MPI 庫作為可移植的消息傳遞函數(shù)庫，具有以下一些特點 :(1) MPI 提供緩沖區(qū)管理的函數(shù)，用戶可以決定由系統(tǒng)對發(fā)送、接受緩沖區(qū) 的管理，還是用戶參與其管理，以便控制系統(tǒng)緩沖區(qū)空間，提高系統(tǒng)的安全性；(2) MPI 不但支持語言本身所提供的各種結構，而且允許用戶構造自己的復 雜結構體和數(shù)據(jù)類型，使得進程間的通信更加便捷易用；(3) MPI 為任務間的通信提供多種方式，大量的通信接口能夠

14、滿足科學與工 程算的需要；(4) MPI 提供可靠的數(shù)據(jù)傳輸機制，發(fā)送的消息能夠保證被對方正確接受， 用戶不必自行檢查傳輸錯誤、 傳輸超時等。 也就是說 MPI 的通信對用戶而言是透 明的；(5) MPI 通過通信域保證通信的安全性，不同通信域內(nèi)的并行任務之間的通 信不會相互干擾和混淆；(6) MPI 具有高度的可重構性，允許多個用戶同時使用并行處理設備。由于 MPI 是一個庫而不是一種語言， 因此 MPI 必須和某個語言結合起來才能 使用，這稱之為 MPI 的語言綁定。MPI 1.0 版于1994 年推出，并同時獲得了各并行機產(chǎn)商的具體實現(xiàn)； MPI 2.0 版于1998 年10 月推出，它在1.0 版的基礎上， 增加了如下的