并行計算綜述

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

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

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

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

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

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

7、體并行機的體系結構進行抽象，設計一個理想的消息傳遞并行機模型。基于該模型，用戶可以在不考慮具體并行機體系結構的條件下，組織消息傳遞并行程序設計，從而簡化并行程序設計，增強程序的可移植性。圖4.1給出了一個理想的消息傳遞進程拓撲結構。其中，“P”表示MPI進程，“M”表示每個進程的局部內存空間，多個“P/M”進程/內存模塊通過互聯(lián)網(wǎng)絡相互連接，構成一個分布式存儲的進程拓撲結構。在該結構中，各個進程之間可以直接通信，但是各個進程只能直接訪問自身的局部內存空間，對其他進程的局部內存空間的訪問只能調用消息傳遞函數(shù)，通過進程間通信才能實現(xiàn)。因此，該進程拓撲結構的核心是連接進程的互聯(lián)網(wǎng)絡，也就是消息傳遞標

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

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

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

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

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

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