并行計算綜述

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

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

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

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

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

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

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

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

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

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

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

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

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

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