并行計(jì)算綜述

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

2、行求解應(yīng)用問(wèn)題的目的。problemIWillIIIh-probleminstructions1.1.2 并行計(jì)算的主要研究目標(biāo)和內(nèi)容對(duì)于具體的應(yīng)用問(wèn)題，采用并行計(jì)算技術(shù)的主要目的在于兩個(gè)方面：(1)加速求解問(wèn)題的速度。提高求解問(wèn)題的規(guī)模。當(dāng)前，如圖1.2和圖1.3所示，組成并行機(jī)的三個(gè)要素為：?結(jié)點(diǎn)(node)。每個(gè)結(jié)點(diǎn)由多個(gè)處理器構(gòu)成，可以直接輸入輸出(I/O)。?互聯(lián)網(wǎng)絡(luò)（interconnectnetwork）。所有結(jié)點(diǎn)通過(guò)互聯(lián)網(wǎng)絡(luò)相互連接相互通信。?內(nèi)存（memory）。內(nèi)存由多個(gè)存儲(chǔ)模塊組成，這些模塊可以如圖1.2所示，與結(jié)點(diǎn)對(duì)稱(chēng)地分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)，或者，如圖1.3所示，位于各

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

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

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

6、享存儲(chǔ)和數(shù)據(jù)并行兩種編程模式。表4.5三種并行編程環(huán)境主要特征一覽表特征消息傳遞共享存儲(chǔ)數(shù)據(jù)并行典型代表MPI、PVMOpenMPHPF可移植性所有流行并行機(jī)SMP、DSMSMP、DSM、MPP并行粒度進(jìn)程級(jí)大粒度線程級(jí)細(xì)粒度進(jìn)程級(jí)細(xì)粒度并行操作方式升少異步松散同步數(shù)據(jù)存儲(chǔ)模式分體式仔儲(chǔ)共學(xué)存儲(chǔ)共學(xué)存儲(chǔ)數(shù)據(jù)分配方式顯式半隱式學(xué)習(xí)入門(mén)難度較難容易偏易可擴(kuò)展性好較差本書(shū)的主要目的是全面介紹消息傳遞并行編程環(huán)境MPI,因此，在以后的篇幅中，將不再討論共享存儲(chǔ)和數(shù)據(jù)并行編程環(huán)境。消息傳遞并行機(jī)模型由于當(dāng)前流行的各類(lèi)SMP、DSM、MPP和微機(jī)機(jī)群等并行機(jī)均支持消息傳遞并行程序設(shè)計(jì)，因此，有必要對(duì)這些具

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

8、準(zhǔn)函數(shù)庫(kù)，而構(gòu)成該函數(shù)庫(kù)的所有函數(shù)就構(gòu)成了用戶面對(duì)的消息傳遞并行編程環(huán)境。圖4.1消息傳遞進(jìn)程拓?fù)浣Y(jié)構(gòu)和并行機(jī)模型如果將圖4.1的每個(gè)P/M模塊替換成處理器，且規(guī)定每個(gè)處理器只能分配用戶程序的一個(gè)進(jìn)程，則所得的理想并行機(jī)模型就是消息傳遞并行機(jī)模型。不難看出，消息傳遞并行程序設(shè)計(jì)所依賴的并行機(jī)模型實(shí)際上屬于典型的分布式存儲(chǔ)并行機(jī)，且每臺(tái)處理器只能分配用戶程序的一個(gè)進(jìn)程?；谠摬⑿袡C(jī)模型，用戶可以自由地調(diào)用消息傳遞函數(shù)庫(kù)中的函數(shù)來(lái)組織具體的并行程序設(shè)計(jì)，且程序研制成功后，便可以在任何支持該并行機(jī)模型隱含的進(jìn)程拓?fù)浣Y(jié)構(gòu)的所有具體并行機(jī)上運(yùn)行。這里，有必要說(shuō)明的是，消息傳遞分布式存儲(chǔ)并行機(jī)模型和具體并

9、行機(jī)體系結(jié)構(gòu)沒(méi)有必然的聯(lián)系。無(wú)論將該模型映射到何種類(lèi)型的并行機(jī)（SMP、DSM、cluster、constellationMPP）,用戶面對(duì)的都是該模型隱含的進(jìn)程拓?fù)浣Y(jié)構(gòu)，只是各類(lèi)具體并行機(jī)實(shí)現(xiàn)的消息傳遞函數(shù)庫(kù)的方式不同，但用戶無(wú)須知道這些細(xì)節(jié)。例如，在共享存儲(chǔ)SMP、DSM并行機(jī)中，消息傳遞是通過(guò)共享數(shù)據(jù)緩存區(qū)來(lái)實(shí)現(xiàn)的；在MPP并行機(jī)中，消息傳遞是通過(guò)網(wǎng)絡(luò)通信來(lái)實(shí)現(xiàn)的；在機(jī)群和星群并行機(jī)中，消息傳遞在SMP、DSM并行機(jī)內(nèi)部是通過(guò)共享數(shù)據(jù)緩存區(qū)實(shí)現(xiàn)的，而在SMP、DSM并行機(jī)之間是通過(guò)網(wǎng)絡(luò)通信來(lái)實(shí)現(xiàn)的。因此，無(wú)論哪種類(lèi)型的具體并行機(jī)，呈現(xiàn)在消息傳遞并行程序設(shè)計(jì)用戶面前的必然是圖4.1所示的分

10、布式存儲(chǔ)并行機(jī)模型。4.5.2標(biāo)準(zhǔn)消息彳遞界面MPI1994年6月，全球工業(yè)、政府和科研應(yīng)用部門(mén)聯(lián)合推出消息傳遞并行編程環(huán)境的標(biāo)準(zhǔn)用戶界面（MPI）,它將消息傳遞并行編程環(huán)境分解為兩個(gè)部分，第一是構(gòu)成該環(huán)境的所有消息傳遞函數(shù)的標(biāo)準(zhǔn)接口說(shuō)明，它們是根據(jù)并行應(yīng)用程序?qū)ο鬟f功能的不同要求而制定的，不考慮該函數(shù)能否具體實(shí)現(xiàn)；第二是各并行機(jī)廠商提供的對(duì)這些函數(shù)的具體實(shí)現(xiàn)。這樣,用戶只需學(xué)習(xí)MPI庫(kù)函數(shù)的標(biāo)準(zhǔn)接口，設(shè)計(jì)MPI并行程序，便可在支持MPI并行編程環(huán)境的具體并行機(jī)上執(zhí)行該程序。通常意義下所說(shuō)的MPI系統(tǒng)就是指所有這些具有標(biāo)準(zhǔn)接口說(shuō)明的消息傳遞函數(shù)所構(gòu)成的函數(shù)庫(kù)。在標(biāo)準(zhǔn)串行程序設(shè)計(jì)語(yǔ)言（C、F

11、ortran、C+）的基礎(chǔ)上，再加入實(shí)現(xiàn)進(jìn)程間通信的MPI消息傳遞庫(kù)函數(shù)，就構(gòu)成了MPI并行程序設(shè)計(jì)所依賴的并行編程環(huán)境。MPI吸收了眾多消息傳遞系統(tǒng)的優(yōu)點(diǎn)，例如P4、PVM、Express、PARMACS等，是目前國(guó)內(nèi)外最流行的并行編程環(huán)境之一。當(dāng)前，大量工業(yè)、科學(xué)與工程計(jì)算部門(mén)（例如氣象、石油、地震、空氣動(dòng)力學(xué)、核物理等）的科研與工程軟件已經(jīng)移植到MPI平臺(tái)。MPI是一個(gè)消息傳遞接口的標(biāo)準(zhǔn)，用于開(kāi)發(fā)基于消息傳遞的并行程序，其目的是為用戶提供一個(gè)實(shí)際可用的、可移植的、高效的和靈活的消息傳遞接口。MPI這個(gè)名稱(chēng)包括三個(gè)方面的含義：MPI是一個(gè)庫(kù)，而不是一種語(yǔ)言。許多人認(rèn)為MPI是一種并行設(shè)計(jì)語(yǔ)

12、言，這種看法并不準(zhǔn)確。按照并行語(yǔ)言的分類(lèi)，可以把Fortran+MPI、C+MPI看做是在原來(lái)的串行語(yǔ)言基礎(chǔ)之上擴(kuò)展而來(lái)的并行語(yǔ)言。MPI庫(kù)可以和具體語(yǔ)言進(jìn)行綁定，形成并行設(shè)計(jì)語(yǔ)言。從語(yǔ)法上說(shuō)，C/C十+和Fortran等語(yǔ)言對(duì)MPI庫(kù)的調(diào)用規(guī)則，與調(diào)用一般的函數(shù)/過(guò)程沒(méi)有區(qū)別；MPI是一種標(biāo)準(zhǔn)或者規(guī)范，而不特指某一個(gè)對(duì)它的具體實(shí)現(xiàn)。到目前為止，所有的并行計(jì)算機(jī)都提供對(duì)MPI的支持，用MPI書(shū)寫(xiě)的并行程序可以不加修改的在所有并行機(jī)上運(yùn)行；MPI是一種消息傳遞編程模型，并且成為了這種編程模型的代表和事實(shí)上的標(biāo)準(zhǔn)。MPI庫(kù)作為可移植的消息傳遞函數(shù)庫(kù)，具有以下一些特點(diǎn)：MPI提供緩沖區(qū)管理的函數(shù)，用

13、戶可以決定由系統(tǒng)對(duì)發(fā)送、接受緩沖區(qū)的管理，還是用戶參與其管理，以便控制系統(tǒng)緩沖區(qū)空間，提高系統(tǒng)的安全性；MPI不但支持語(yǔ)言本身所提供的各種結(jié)構(gòu)，而且允許用戶構(gòu)造自己的復(fù)雜結(jié)構(gòu)體和數(shù)據(jù)類(lèi)型，使得進(jìn)程間的通信更加便捷易用；MPI為任務(wù)間的通信提供多種方式，大量的通信接口能夠滿足科學(xué)與工程算的需要；MPI提供可靠的數(shù)據(jù)傳輸機(jī)制，發(fā)送的消息能夠保證被對(duì)方正確接受，用戶不必自行檢查傳輸錯(cuò)誤、傳輸超時(shí)等。也就是說(shuō)MPI的通信對(duì)用戶而言是透明的；MPI通過(guò)通信域保證通信的安全性，不同通信域內(nèi)的并行任務(wù)之間的通信不會(huì)相互干擾和混淆；MPI具有高度的可重構(gòu)性，允許多個(gè)用戶同時(shí)使用并行處理設(shè)備。由于MPI是一個(gè)庫(kù)而不是一種語(yǔ)言，因此MPI必須和某個(gè)語(yǔ)言結(jié)合起來(lái)才能使用，這稱(chēng)之為MPI的語(yǔ)言綁定。MPI1.0版于1994年推出，并同時(shí)獲得了各并行機(jī)產(chǎn)商的具體實(shí)現(xiàn)；MPI2.0版于1998月推出，它在1.0版的基礎(chǔ)上，增加了如下的消