作者：ArimaMisaki

目錄

1 并行計算概述. 2

1.1 基本概念. 2

1.2 存儲器的層次結(jié)構(gòu). 3

1.3 并行計算. 3

1.4 動態(tài)互連網(wǎng)絡(luò). 4

1.5 并行計算機(jī)結(jié)構(gòu)模型. 5

1.6 并行算法的基本設(shè)計策略. 6

1.7 并行編程風(fēng)范. 6

1.8 單核多線程和并發(fā)執(zhí)行. 7

1.9 拓展：并行計算機(jī)的分類. 7

1.10 并行層次和代碼粒度. 10

1.11 并行程序設(shè)計模型. 10

2并行計算模型. 11

2.1 拓展：進(jìn)程. 11

2.2 拓展：進(jìn)程模型. 11

2.3 拓展：父子進(jìn)程. 12

2.4 拓展：線程. 12

2.5 拓展：用戶線程和內(nèi)核線程. 12

2.6 POSIX線程. 13

2.7 并行算法. 13

2.8 并行計算模型. 14

2.9 并行算法一般設(shè)計過程. 15

2.10 程序性能評價與優(yōu)化. 15

3 OpenMP并行編程模型. 16

3.1 OpenMP概述. 16

3.2 OpenMP語句模式. 16

3.3 OpenMP簡單演示. 17

3.4 Schedule關(guān)于for循環(huán)的調(diào)度. 18

3.5 設(shè)置環(huán)境變量（拓展）. 19

3.6 sections制導(dǎo)指令. 20

3.7 single制導(dǎo)指令（拓展）. 20

3.8 共享任務(wù)結(jié)構(gòu). 21

3.9 OpenMP的優(yōu)點和缺點. 21

3.10 常用子句的補(bǔ)充. 22

4 MPI并行編程模型. 22

4.1 拓展：什么是MPI 22

4.2 MPI基本函數(shù). 22

4.3 消息傳遞的特點. 24

1 并行計算概述

1.1 基本概念

并行計算：并行計算機(jī)或分布式計算機(jī)（包括網(wǎng)絡(luò)計算機(jī)）等高性能計算機(jī)系統(tǒng)上所做的超級計算

計算科學(xué)：用強(qiáng)大的計算能力去理解和解決復(fù)雜問題，是確保科學(xué)領(lǐng)先地位、經(jīng)濟(jì)競爭力和國防安全等的關(guān)鍵之所在。科學(xué)發(fā)現(xiàn)的第三支柱。

計算思維：運用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計以及人類行為的理解，是21世紀(jì)中葉所有人的一種基本技能，就像現(xiàn)今人們掌握閱讀、寫作和算術(shù)技能一樣，希望每個人都能像計算機(jī)科學(xué)家那樣思考問題。

流水線：通常一條指令執(zhí)行分為不同的階段（如取指、譯碼、取數(shù)、執(zhí)行等），通過重疊指令執(zhí)行中的不同階段，可以加快指令的執(zhí)行速度。

超標(biāo)量：如果CPU種設(shè)有多條流水線，即能同時發(fā)射多條指令，這種具有可在同一時鐘周期內(nèi)發(fā)射多條指令功能的處理器就成為超標(biāo)量。

摩爾定律：“摩爾定律是由英特爾(Intel)創(chuàng)始人之一戈登·摩爾(Gordon Moore)提出來的。其內(nèi)容為:當(dāng)價格不變時,集成電路上可容納的元器件的數(shù)目,約每隔18-24個月便會增加一倍,性能也將提升一倍。換言之,每一美元所能買到的電腦性能,將每隔18-24個月翻一倍以上。這一定律揭示了信息技術(shù)進(jìn)步的速度。”

多核處理器：AMD和Intel在2005年相繼推出了各自的雙核處理器Opteron和Core Duo

拓展：多核處理器 多核CPU芯片可以看做是一個大芯片里面套了好幾個小芯片，每個小芯片都可以看做是一個獨立的CPU，對于Intel Xeon Phi（英特爾至強(qiáng)融核處理器）來說，其上面甚至集成了60多個核。 雖然多核CPU很牛，但是說到多核，可能沒有比GPU更牛的了，GPU指的是成千上萬個微核組成的處理器，其適用于大量的并行簡單計算，還有圖像處理，但是其不太適應(yīng)串行任務(wù)，而且對于編程及算法的實現(xiàn)難度過高，所以一般操作系統(tǒng)還是運行在CPU上比較好。

1.2 存儲器的層次結(jié)構(gòu)

拓展：計算機(jī)中的存儲器結(jié)構(gòu) 這實際上是計算機(jī)組成原理的知識。 存儲器一般分為多種，如主存、緩存、輔存、寄存器等等。這里圖中出現(xiàn)了Cache。Cache一般指的是高速緩存，在以前Cache一般位于CPU之外，而在現(xiàn)在大多數(shù)Cache都在CPU內(nèi)部。 Cache存儲器（電腦中為高速緩沖存儲器），是位于CPU和主存儲器DRAM（Dynamic Random Access Memory）之間，規(guī)模較小，但速度很高的存儲器，通常由SRAM（Static Random Access Memory）靜態(tài)存儲器組成。它是位于CPU與內(nèi)存間的一種容量較小但速度很高的存儲器。CPU的速度遠(yuǎn)高于內(nèi)存，當(dāng)CPU直接從內(nèi)存中存取數(shù)據(jù)時要等待一定時間周期，而Cache則可以保存CPU剛用過或循環(huán)使用的一部分?jǐn)?shù)據(jù)，如果CPU需要再次使用該部分?jǐn)?shù)據(jù)時可從Cache中直接調(diào)用，這樣就避免了重復(fù)存取數(shù)據(jù)，減少了CPU的等待時間，因而提高了系統(tǒng)的效率。Cache又分為L1Cache（一級緩存）和L2Cache（二級緩存），L1Cache主要是集成在CPU內(nèi)部，而L2Cache集成在主板上或是CPU上。 主存一般指的是內(nèi)存、寄存器，而輔存一般指外存（如磁盤、CD-ROM也就是光盤等）。各個存儲器之間用總線進(jìn)行通信，確保數(shù)據(jù)能夠從計算機(jī)的一個位置傳輸?shù)搅硗庖粋€位置。 寄存器一般處于CPU內(nèi)部，用來存放數(shù)據(jù)。對于常用的數(shù)據(jù)，一般先放在存儲器，放不下了就放到高速緩沖去，再放不下就轉(zhuǎn)移到磁盤。

1.3 并行計算

并行計算的初衷，是為了努力仿真自然世界中一個序列中含有眾多同時發(fā)生的、復(fù)雜且相關(guān)事件的事務(wù)狀態(tài)。

為了利用并行計算求解一個計算問題，通常基于以下考慮：

將計算任務(wù)分解成多個子任務(wù)，有助于同時解決

在同一個時間，由不同的執(zhí)行部件可同時執(zhí)行多個子任務(wù)

多計算資源下解決問題的耗時要少于單個計算資源下的耗時

并行計算基本上可以分為：

計算密集型

數(shù)據(jù)密集型

網(wǎng)絡(luò)密集型

1.4 動態(tài)互連網(wǎng)絡(luò)

動態(tài)網(wǎng)絡(luò)是用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動態(tài)地改變連接組態(tài)；典型的動態(tài)網(wǎng)絡(luò)包括總線、交叉開關(guān)和多級互連網(wǎng)絡(luò)等。

這種網(wǎng)絡(luò)比較普遍的是總線上面掛交換器。我們知道同一時間段中，一條總線只允許兩頭的設(shè)備進(jìn)行信息交換，而在交換完成后，交換器可以將總線的端口改變，使其連接另外一個設(shè)備。通過這種方法，可以根據(jù)我們應(yīng)用的需求，動態(tài)地選擇我們需要的設(shè)備。

典型的動態(tài)網(wǎng)絡(luò)區(qū)別如下：

拓展：并行計算機(jī)系統(tǒng)互連 不同帶寬和距離的互連技術(shù)有多種，比較常用是：廣域網(wǎng)WAN、城域網(wǎng)MAN、局域網(wǎng)WAN、個人區(qū)域網(wǎng)PAN、總線。廣域網(wǎng)一般跨國，城域網(wǎng)一般城市，局域網(wǎng)一般一棟樓，個人區(qū)域網(wǎng)一般幾臺設(shè)備。其中廣域網(wǎng)使用了交換技術(shù)，而局域網(wǎng)使用的是廣播技術(shù)。如果是使用總線的話，總線是最快的，你可以理解為總結(jié)傳輸時不需要網(wǎng)絡(luò)，直接用一條USB連接的那種。 靜態(tài)互聯(lián)網(wǎng)絡(luò)是處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點到點的連接保持不變；典型靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡(luò)、立方環(huán)、洗牌交換網(wǎng)、蝶狀網(wǎng)絡(luò)等。 換而言之，靜態(tài)互連網(wǎng)絡(luò)就是用一個鏈路把多個處理器連接起來，構(gòu)成物理意義上的并行計算機(jī)，如果某個處理器想發(fā)信息給另外一個處理器，總是能通過這條鏈路來干這種事。 相對地，我們還有動態(tài)互聯(lián)網(wǎng)絡(luò)。 互聯(lián)網(wǎng)絡(luò)中還有另外一個概念叫嵌入。其做法是將網(wǎng)絡(luò)中的各節(jié)點映射到另一個網(wǎng)絡(luò)中去。用膨脹系數(shù)來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡(luò)中的一條鏈路在所要嵌入的網(wǎng)絡(luò)中對應(yīng)所需的最大鏈路數(shù)。如果該系數(shù)為1，則稱為完美嵌入。 對于環(huán)網(wǎng)和超立方來說，兩者皆可被完美嵌入到2D環(huán)繞網(wǎng)中。

1.5 并行計算機(jī)結(jié)構(gòu)模型

PVP

PVP也叫并行向量處理機(jī)(Parallel Vector Processor)，其內(nèi)部含有為數(shù)不多、功能強(qiáng)大的定制向量處理器，以及定制的高帶寬縱橫交叉開關(guān)和高速數(shù)據(jù)訪問。其價格十分昂貴，因為其組件都需定制，一般適用于國家部門。

SMP

SMP也叫對稱多處理機(jī)。其訪存、IO都是對稱的。其用的處理器大多數(shù)是商用處理器。

目前SMP需要解決的主要問題是Cache的一致性問題。多級高速緩存可以支持?jǐn)?shù)據(jù)的局部性，而其一致性可由硬件來增強(qiáng)。大多數(shù)SMP系統(tǒng)都是基于總線連接的，占據(jù)了并行計算機(jī)市場中很大的份額。

MMP

MMP也叫`大規(guī)模并行處理機(jī)(Massively Parallel Processor)`，其規(guī)模大，性能好。

DSM

DSM又叫分布式共享存儲器(Distributed Shared Memory,DSM)。在DSM中，每個節(jié)點都有本地內(nèi)存，所有的節(jié)點都有一個共享空間。

COW

COW又叫工作站機(jī)群(Cluster of Workstation)。工作站機(jī)群的結(jié)構(gòu)技術(shù)起點比較低，可以自己將一些服務(wù)器/微型機(jī)通過以太網(wǎng)連起來，加上相應(yīng)的管理和通訊軟件來搭建自己的工作站機(jī)群。

在集群中，每個節(jié)點都有本地磁盤，除了沒有顯示器沒有鼠標(biāo)沒有鍵盤之外，基本上其他普通計算機(jī)該有的它都有。每個節(jié)點用I/O總線連向?qū)ｉT設(shè)計的多級高速網(wǎng)絡(luò)。

機(jī)群也是構(gòu)建并行計算機(jī)一種很廉價的方案，其被稱為窮人的解決方案。使用這類并行計算機(jī)跑并行程序效率很低，但是由于它的性價比和搭建的簡便性，使得近幾年常被用于做并行科學(xué)計算和并行商用計算。

需要注意的是，機(jī)群不適合用于國家級的計算，因為由上述可知，實際上機(jī)群可以理解為是很多廉價的機(jī)器并在一起，而如果要運行速度跟快，能處理的數(shù)據(jù)更多，就需要并一個很大的機(jī)群。而如果機(jī)群并得很大，就會導(dǎo)致散熱有問題。我們前面說過它們通過總線互聯(lián)的，你總不能一個計算機(jī)在東一個計算機(jī)在西，然后一條總線連著吧。肯定是統(tǒng)一放在一個地方啊。而如果要處理大型的數(shù)據(jù)，一般機(jī)群所處的機(jī)房就要三四層樓那么高，籃球場那么寬，肯定不利于散熱。

1.6 并行算法的基本設(shè)計策略

串行算法的直接并行化；如快排的自然并行化

從問題描述開始設(shè)計并行算法；如并行串匹配算法

借用已有算法求解新問題；如使用矩陣乘法算法求解所有點對間最短路徑是一個很好的范例

并行算法常用設(shè)計技術(shù)

劃分設(shè)計技術(shù)

分治設(shè)計技術(shù)

平衡樹設(shè)計技術(shù)

倍增設(shè)計技術(shù)

流水線設(shè)計技術(shù)

注意：分治法和劃分法的區(qū)別 分治法的側(cè)重點在于子問題的歸并上，而劃分法的注意力則集中在原問題的劃分上，分治是遞歸方式的劃分，它將問題分成子問題后不立即求解它，而是連續(xù)地再將其分為更小的、易于求解的子問題。

1.7 并行編程風(fēng)范

并行編程風(fēng)范是指在并行機(jī)上編程實現(xiàn)并行算法的方法。如：

相并行

分治并行

流水線并行

主從并行

工作池并行

1.8 單核多線程和并發(fā)執(zhí)行

并發(fā)執(zhí)行是指多個線程在同一硬件資源上或單處理器核上交替地執(zhí)行，在某個特定的時間點，所有活動的線程只有一個在真正執(zhí)行，但在某段時間間隔內(nèi)對外表現(xiàn)為多個線程在同時執(zhí)行。

這種做法并非真正意義上的并行多線程，在單核結(jié)構(gòu)上的應(yīng)用程序主要靠隱藏延遲的方法來提高應(yīng)用程序的性能。

影響多線程性能的常見問題有如下幾點：

線程過多、數(shù)據(jù)競爭、死鎖、Cache偽共享/Cache行乒乓現(xiàn)象。

注意：并行和并發(fā) 對于學(xué)過操作系統(tǒng)的都知道，比較容易混淆的就是并行的概念，我們所說的并行通常指的是：指兩個或多個事件在同一時刻同時發(fā)生。 我們用一個例子來說明：有兩個人一個叫小明一個叫小剛。它們每人都有兩個女朋友。對于小明來說，他喜歡的是和一號、二號一起出門約會；而對于小剛來說，他喜歡8:00和一號約會，9:00和二號約會，10:00和一號約會。 這里我們發(fā)現(xiàn)兩個人同樣都是在約會，但是小明是同一時刻同時發(fā)生，屬于并行；而小剛?cè)绻麆e人問他你怎么約會的，他會說他和兩個女生同時約會，但是實際上，它是和兩個女生交替約會，這就是宏觀和微觀的區(qū)別，其屬于并發(fā)。 一個單核處理器(CPU)同一時刻只能執(zhí)行一個程序，因此操作系統(tǒng)會負(fù)責(zé)協(xié)調(diào)多個程序交替執(zhí)行，這就是操作系統(tǒng)的并發(fā)性。但是需要注意的是我們強(qiáng)調(diào)的是單核處理器，如今的電腦一般都是多核CPU，如Intel的第八代i3處理器就是4核CPU，這意味著同一時刻可以有4個程序并行執(zhí)行，但是操作系統(tǒng)的并發(fā)性依然必不可少，因為每個人根本不可能說一臺電腦只開四個應(yīng)用程序吧。

1.9 拓展：并行計算機(jī)的分類

一臺并行計算機(jī)可以是一臺具有多個內(nèi)部處理器的單計算機(jī)，也可以是多個互聯(lián)的計算機(jī)構(gòu)成一個一體的高性能計算平臺。術(shù)語并行計算機(jī)通常是指專門設(shè)計的部件。根據(jù)不同的分類法可以分成不同類型的并行計算機(jī)。

1.9.1 費林分類法

在操作系統(tǒng)中我們知道，程序根據(jù)高級程序設(shè)計語言設(shè)計，程序設(shè)計語言在實現(xiàn)程序的功能的時候，是轉(zhuǎn)換為機(jī)器指令來告訴機(jī)器該干什么。大概在50年前Flynn(1996)創(chuàng)造了一種計算機(jī)分類方法,中文譯為費林分類法，該分類基于兩個獨立維度的計算機(jī)體系結(jié)構(gòu)，這兩個維度即數(shù)據(jù)和指令。根據(jù)以上提到這兩個維度，我們可以劃分為四大類，如圖：

Single Instruction,Single Data(SISD)

SISD機(jī)器是一種傳統(tǒng)的串行計算機(jī)，它的硬件不支持任何形式的并行計算，所有的指令都是串行執(zhí)行。并且在某個時鐘周期（時間片）內(nèi)，CPU只能處理一個數(shù)據(jù)流。因此這種機(jī)器被稱作單指令流單數(shù)據(jù)流計算機(jī)。早期的計算機(jī)都是SISD機(jī)器，如馮諾.依曼架構(gòu)，如IBM PC機(jī)，早期的巨型機(jī)和許多8位的家用機(jī)等。

Multiple Instruction,Multiple Data(MIMD)

在一個通用的多處理機(jī)系統(tǒng)中，每個處理器擁有一個獨立的程序，由每個程序為每個處理器生成一個指令流，不同的數(shù)據(jù)可能需要不同的處理，對應(yīng)賦給不同的指令。每條指令對不同數(shù)據(jù)進(jìn)行操作。Flynn將這種形式的計算機(jī)分類為多指令流多數(shù)據(jù)流計算機(jī)。

我們后面敘述的共享存儲器或消息傳遞多處理機(jī)都屬于MIMD類型。其已經(jīng)經(jīng)受了時間考驗，至今仍然廣泛地用于這種操作模式下的計算機(jī)系統(tǒng)中。例如多核CPU計算機(jī)。

Single Instruction,Multiple Data(SIMD)

如果對某些應(yīng)用而言將計算機(jī)設(shè)計成由單一程序生成指令流，但是卻有多個數(shù)據(jù)存在時，將會在性能上有很大的優(yōu)勢。打個比方，你輸入一條指令就能夠處理很多的數(shù)據(jù)，那不就是提高了性能嗎。我們熟知的Hadoop就是基于SIMD的。

SIMD是采用一個指令流處理多個數(shù)據(jù)流。這類機(jī)器在數(shù)字信號處理、圖像處理、以及多媒體信息處理等領(lǐng)域非常有效。

Intel處理器實現(xiàn)的MMXTM、SSE（Streaming SIMD Extensions）、SSE2及SSE3擴(kuò)展指令集，都能在單個時鐘周期內(nèi)處理多個數(shù)據(jù)單元。也就是說我們現(xiàn)在用的單核計算機(jī)基本上都屬于SIMD機(jī)器。

Multiple Instruction,Single Data(MISD)

MISD是采用多個指令流來處理單個數(shù)據(jù)流。由于實際情況中，采用多指令流處理多數(shù)據(jù)流才是更有效的方法，誰會去一個數(shù)據(jù)多個指令去處理呀。因此MISD只是作為理論模型出現(xiàn)，僅僅只在1971年CMU的實驗中出現(xiàn)過，也就是說，實際上并不存在SISD。

1.9.2 存儲器結(jié)構(gòu)分類法

共享存儲器多處理機(jī)

共享存儲器多處理機(jī)可以理解為一個多核的計算機(jī)或者很多個單核的共用一份內(nèi)存的計算機(jī)。當(dāng)處理器想要處理數(shù)據(jù)，它就得跑去存儲器拿數(shù)據(jù)。怎么知道數(shù)據(jù)在哪呢？通過存儲器上的地址可以知道。

在操作系統(tǒng)中我們學(xué)過，如果這個時候兩個處理器要同時在一個存儲器上拿東西，那它們一定要提前溝通好，也就是說，兩個處理器對共享空間的訪問是互斥的。它們提前溝通的工具是互聯(lián)網(wǎng)絡(luò)。

多處理機(jī)系統(tǒng)由多臺獨立的處理機(jī)組成，每臺處理機(jī)都能夠獨立執(zhí)行自己的程序和指令流，相互之間通過專門的網(wǎng)絡(luò)連接，實現(xiàn)數(shù)據(jù)的交換和通信，共同完成某項大的計算或處理任務(wù)。系統(tǒng)中的各臺處理機(jī)由統(tǒng)一的操作系統(tǒng)進(jìn)行管理，實現(xiàn)指令級以上并行，這種并行性一般是建立在程序段的基礎(chǔ)上，也就是說，多處理機(jī)的并行是作業(yè)或任務(wù)級的并行。共享存儲多處理機(jī)系統(tǒng)是指有一個可以被所有處理機(jī)訪問的存儲器系統(tǒng)。存儲器系統(tǒng)由一個或多個存儲器模塊組成，所有的存儲器模塊使用一個統(tǒng)一的編址的地址空間。處理機(jī)可以用不同的地址訪問不同的存儲器模塊。按存儲器組織方式分類，共享存儲多處理機(jī)系統(tǒng)分為集中式共享存儲器系統(tǒng)和分布式共享存儲器系統(tǒng)。

對共享存儲器多處理機(jī)進(jìn)行編程設(shè)計到在共享存儲器中存有可由每個處理器執(zhí)行的代碼。每個程序所需的數(shù)據(jù)也將存于共享存儲器中。（即程序段和數(shù)據(jù)段都在共享內(nèi)存中）。因此如果有需要的話，每個程序可以訪問所有的數(shù)據(jù)。

程序員要想使用并行計算機(jī)的每個處理器來處理一件問題，那原有的高級程序語言就無法使用了。所以為了解決此問題，程序員們開發(fā)了一種新的、高級并行程序設(shè)計語言，它具有特殊的并行程序設(shè)計構(gòu)造和語句，以聲明共享變量和并行代碼段。雖然想法很好，但是這類并行程序設(shè)計語言并不是使用很廣泛。

比較廣泛的做法是在普通的高級程序語言的基礎(chǔ)上生成并行代碼，你可以理解為嵌入式編碼（類似于嵌入式SQL）。此時使用制定好規(guī)則的編程語言，然后用預(yù)處理器命令對程序的并行部分加以說明即可；這類實踐比較著名的模型就是OpenMP。它是由編譯器命令和構(gòu)造的一個工業(yè)標(biāo)準(zhǔn)，可融入到C/C++中。

另外，我們也可以多開幾條線程，這樣的話給人的感覺也像是并行計算的樣子，不同線程中含有為各個處理器執(zhí)行的規(guī)整的高級語言代碼序列，這些代碼序列可以用來訪問共享單元。但是需要注意的是，實際上用線程的方法不是并行而是并發(fā)。

共享存儲器多處理機(jī)是很一種很不錯的并行計算機(jī)，綜上所述，其方便了對數(shù)據(jù)的共享。

消息傳遞多計算機(jī)

多處理機(jī)系統(tǒng)的形式可以通過互聯(lián)網(wǎng)絡(luò)連接多臺完整的計算機(jī)來構(gòu)成。這實際上是使用了操作系統(tǒng)中的消息傳遞。

在消息傳遞多計算機(jī)中，一臺計算機(jī)的處理器只能訪問它對應(yīng)本地的主存儲器，而無法訪問其他計算機(jī)上的主存儲器。不同的計算機(jī)之間是用互聯(lián)網(wǎng)來建立聯(lián)系的，通常來說，多個電腦之間通過互聯(lián)網(wǎng)傳遞的消息含有的可能是程序所指明的其他計算機(jī)處理器進(jìn)行計算時所需的數(shù)據(jù)。這種多處理器系統(tǒng)我們通常稱為消息傳遞多處理機(jī)(message-passing multiprocessor)，或簡稱多計算機(jī)。你可以理解為多計算機(jī)實質(zhì)上是真正意義上的分布式存儲計算機(jī)。

我們在操作系統(tǒng)常提到進(jìn)程這個概念，在多計算機(jī)上，我們可以把一個問題分成多個并發(fā)進(jìn)程，它們可在各臺計算機(jī)上分別執(zhí)行。如果有6個進(jìn)程和6個計算機(jī)，則我們可在每臺計算機(jī)上執(zhí)行一個進(jìn)程；如果進(jìn)程數(shù)大于計算機(jī)數(shù)，那么其中一臺計算機(jī)中如果是多核可以采用并行執(zhí)行，如果是單核可以采用分時方式執(zhí)行。進(jìn)程間將通過發(fā)送消息的原語來聯(lián)系對方。同樣地，發(fā)送消息可以采用兩種方式，一種是直接通信方式，一種是間接通信方式，如果感興趣可以去操作系統(tǒng)方面查找資料，這里不再細(xì)講。

消息傳遞多計算機(jī)比共享存儲器多處理機(jī)更容易在物理上進(jìn)行擴(kuò)展，也就是說它可以構(gòu)成較大規(guī)模。一般規(guī)模比較小的叫做機(jī)群（Cluster），規(guī)模比較大的叫做超級計算機(jī)（SuperComputer），規(guī)模很大的叫做數(shù)據(jù)中心（DataCenter）。

1.10 并行層次和代碼粒度

并行度：同時執(zhí)行的分進(jìn)程數(shù)

并行粒度：兩次并行或交互操作之間所執(zhí)行的計算負(fù)載

并行度與并行粒度大小常互為倒數(shù)：增大粒度會減小并行度

增加并行度會增加系統(tǒng)（同步）開銷

按發(fā)送者數(shù)量和接受者數(shù)量參與通信可將發(fā)送分為：

一對一：點到點

一對多：廣播、播散

多對一：收集、歸約

多對多：全交換、掃描、置換/移位

延伸：粒度 在并行計算執(zhí)行過程中，兩個通信之間每個處理器計算工作量大小的粗略描述，分為細(xì)粒度和粗粒度。 粒度在并行算法設(shè)計中必不可少，通常在進(jìn)程數(shù)與效率之間選擇粒度的大小，比如后面將要介紹的MPI并行程序更適合粗粒度并行，而使用CUDA并行程序就需要細(xì)粒度。

1.11 并行程序設(shè)計模型

隱式并行：讓編譯器和運行時支持系統(tǒng)自動地開拓它

數(shù)據(jù)并行：并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）

共享變量：駐留在各處理器上的進(jìn)程可以通過讀寫公共存儲器中的共享變量相互通信

消息傳遞駐留在不同處理器節(jié)點上的進(jìn)程可以通過網(wǎng)絡(luò)傳遞消息相互通信。

2并行計算模型

2.1 拓展：進(jìn)程

在只有一個用戶的PC機(jī)開機(jī)的時候，實際上會秘密啟動很多進(jìn)程。例如，啟動一個進(jìn)程用來等待進(jìn)入的電子郵件；或者啟動另一個防病毒進(jìn)程周期性地檢查是否有病毒庫更新。或者更好笑的是，一開機(jī)就是垃圾捆綁軟件，什么2345，什么網(wǎng)頁游戲，這些都是進(jìn)程。這么多進(jìn)程的活動都是需要管理的，于是有一個支持多進(jìn)程的多道程序系統(tǒng)在這里顯得就很有用了。

在任何多道程序設(shè)計系統(tǒng)中，CPU能夠很快地切換進(jìn)程，這個很快是幾百毫秒哦。這也就讓人產(chǎn)生一種并行的錯覺，在一秒鐘內(nèi)怎么開了這么多進(jìn)程？同時開的嗎？不是，實際上在一瞬間只能有一個進(jìn)程讓CPU服務(wù)，只是進(jìn)程切換地太快了，這就是偽并行。這和真正意義上的并行是有區(qū)別的，這也導(dǎo)致了此情形可以用來作為判別是否為多處理器系統(tǒng)的指標(biāo)。

2.2 拓展：進(jìn)程模型

在操作系統(tǒng)中，進(jìn)程模型簡稱進(jìn)程，但實際上和進(jìn)程有所區(qū)別。在進(jìn)程模型中，計算機(jī)上所有可運行的軟件，通常也包括操作系統(tǒng)，被組織成若干順序進(jìn)程，簡稱進(jìn)程，進(jìn)程是程序的一次執(zhí)行過程。

每個進(jìn)程都擁有自己的虛擬CPU，當(dāng)然，實際上真正的CPU在各進(jìn)程之間來回切換。在操作系統(tǒng)中時間復(fù)用技術(shù)曾經(jīng)提到過，當(dāng)一個資源在時間上復(fù)用時，不同的程序或用戶輪流使用它。實際上對于CPU來說也是如此，在時間上進(jìn)行復(fù)用的時候，不同的進(jìn)程輪流使用它。這種快速地切換是需要特定的設(shè)計的，我們稱為多道程序設(shè)計。

當(dāng)然在上述的思考中，我們僅僅討論的是單核CPU，而不是多核。如果是多核CPU，根據(jù)我們之前所說，多核CPU可以看成一個大CPU里面裝了多個小的CPU；甚至于有的電腦還不止一個CPU，對于一些并行計算機(jī)，多處理器的情況也是很常見的。

拓展：時分復(fù)用技術(shù)和空分復(fù)用技術(shù)

這是操作系統(tǒng)系統(tǒng)四大特征——并發(fā)、共享、虛擬、異步中虛擬特征的兩大技術(shù)。

2.3 拓展：父子進(jìn)程

在Unix中，通過fork函數(shù)創(chuàng)建的新進(jìn)程是原進(jìn)程的子進(jìn)程，而調(diào)用fork函數(shù)的進(jìn)程是fork函數(shù)創(chuàng)建出來的新進(jìn)程的父進(jìn)程。也就是說，通過fork函數(shù)創(chuàng)建的新進(jìn)程與原進(jìn)程是父子關(guān)系，fork就相當(dāng)于一個憑證，有fork，就有父子關(guān)系。

在Windows則沒有這些說法，所有的進(jìn)程地位都是相同的。

2.4 拓展：線程

在很久以前還沒有引入進(jìn)程之前，系統(tǒng)中的各個程序只能串行執(zhí)行。比如你想要邊聽歌邊開QQ，這是不可能做到的，只能先做一件事再做一件事。

后來引入進(jìn)程后，系統(tǒng)中的各個程序可以并發(fā)執(zhí)行。也就是說，可以同時聽歌和開QQ。但是，即使引入了進(jìn)程，也不能在QQ中同時視頻聊天和傳輸文件。這是因為操作系統(tǒng)每一次執(zhí)行都是按照進(jìn)程為單位來執(zhí)行的。

從上面的例子來看，進(jìn)程是程序的一次執(zhí)行。但是這些功能顯然不可能是由一個程序順序處理就能實現(xiàn)的。有的進(jìn)程可能需要“同時做很多事”，而傳統(tǒng)的進(jìn)程只能串行地執(zhí)行一系列程序。為此，引入了線程來提高并發(fā)度。

在傳統(tǒng)中，進(jìn)程是程序執(zhí)行流的最小單位，也就是說，CPU每次執(zhí)行任務(wù)，最少執(zhí)行一個進(jìn)程。而后在現(xiàn)在，CPU每次執(zhí)行任務(wù)，最少執(zhí)行一個線程，線程是進(jìn)程的子集。也就是說，引入線程后，線程成為了程序執(zhí)行流的最小單位。

需要知道的是，同個進(jìn)程中所有線程的內(nèi)存是共享的，如果是同個進(jìn)程中的線程做通信交換數(shù)據(jù)非常快，但是不同進(jìn)程的線程交換數(shù)據(jù)就很慢了。

2.5 拓展：用戶線程和內(nèi)核線程

用戶級線程由應(yīng)用程序通過線程庫實現(xiàn)。所有的線程管理工作都由應(yīng)用程序負(fù)責(zé)（包括線程切換）。用戶級線程中，線程切換可以在用戶態(tài)下即可完成，無需操作系統(tǒng)干預(yù)。在用戶看來，是有多個線程；但是對于操作系統(tǒng)內(nèi)核來說，并意識不到線程的存在。即用戶級線程對用戶不透明，對操作系統(tǒng)透明。

內(nèi)核級線程（Kernel-Level Thread,KTL，又稱為“內(nèi)核支持的線程”）。內(nèi)核級線程的管理工作由操作系統(tǒng)內(nèi)核完成。線程調(diào)度、切換等工作都由內(nèi)核負(fù)責(zé)，因此內(nèi)核級線程的切換必然需要在核心態(tài)下才能完成。

2.6 POSIX線程

為了實現(xiàn)可移植的線程程序，IEEE定義了線程的標(biāo)準(zhǔn)。它定義的線程包叫做pthread，大部分UNIX系統(tǒng)支持該標(biāo)準(zhǔn)。這個標(biāo)準(zhǔn)定義了超過60個函數(shù)調(diào)用。常見的幾個如下所示：

?一言蔽之：Posix線程是一種標(biāo)準(zhǔn)，我們可以在任何編程語言中使用這個標(biāo)準(zhǔn)，如Java如果要開多線程就實現(xiàn)Thread這個類，這個類中的所有方法都是按照Posix這個標(biāo)準(zhǔn)制定的。

Posix線程模型具有如下特點：

可分為用戶線程、內(nèi)核線程和輕量級進(jìn)程（LMP）

線程共享相同的內(nèi)存空間

與標(biāo)準(zhǔn)fork()相比，線程帶來的開銷很小。內(nèi)核無需單獨復(fù)制進(jìn)程的內(nèi)存空間或文件描述符等等。這就節(jié)省了大量的CPU時間。

和進(jìn)程一樣，線程將利用多CPU。如果軟件是針對多處理器系統(tǒng)設(shè)計的，則其為計算密集型應(yīng)用。

支持內(nèi)存共享無需使用繁雜的IPC和其他復(fù)雜的通信機(jī)制

2.7 并行算法

串行算法：解題方法的精確描述，是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運算。

并行算法：一些可同時執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動作從而達(dá)到給定問題的求解。

描述語言：采用偽代碼進(jìn)行描述，在程序描述語言中引入并行語句

同步：在時間上強(qiáng)使各執(zhí)行進(jìn)程在某一點必須互相等待

通信：共享存儲多處理器使用讀寫全局變量，分布存儲多計算機(jī)使用發(fā)送和接收消息。

拓展：進(jìn)程通信 在操作系統(tǒng)中，進(jìn)程通信就是進(jìn)程之間的信息交換。 進(jìn)程是分配系統(tǒng)資源的單位（包括內(nèi)存地址空間），因此各進(jìn)程擁有的內(nèi)存地址空間相互獨立。為了保證安全，一個進(jìn)程不能直接訪問另一個進(jìn)程的地址空間，但是進(jìn)程之間的信息交換又是必須實現(xiàn)的，為了保證進(jìn)程之間的安全通信，操作系統(tǒng)提供了一些方法。 共享存儲 使用共享存儲的方式進(jìn)行進(jìn)程通信的話，操作系統(tǒng)會在內(nèi)存中開辟一個共享空間，讓兩個進(jìn)程進(jìn)行通信。 需要注意的是：兩個進(jìn)程對共享空間的訪問必須是互斥的（互斥訪問通過操作系統(tǒng)提供的工具實現(xiàn)）；并且操作系統(tǒng)只負(fù)責(zé)提供共享空間和同步互斥工具。 管道通信 管道是指用于連接讀寫進(jìn)程的一個共享文件，又名pipe文件。其實就是在內(nèi)存中開辟一個大小固定的緩沖區(qū)。需要知道的是： 1. 管道只能采用半雙工通信，某一個時間段內(nèi)只能實現(xiàn)單向的傳輸。如果要實現(xiàn)雙向同時通信，則需要設(shè)置兩個管道。 2. 各進(jìn)程要互斥地訪問管道 3. 數(shù)據(jù)以字符流的形式寫入管道，當(dāng)管道寫滿時，寫進(jìn)程的write()系統(tǒng)調(diào)用將被阻塞，等待讀進(jìn)程將數(shù)據(jù)取走。當(dāng)讀進(jìn)程將數(shù)據(jù)全部取走后，管道變空，此時讀進(jìn)程的read()系統(tǒng)調(diào)用將被阻塞。 4. 如果沒寫滿，就不允許讀；如果沒讀空，就不允許寫。 5. 數(shù)據(jù)一旦被讀出，就從管道中被拋棄，這就意味著讀進(jìn)程最多只能有一個，否則可能會有讀錯數(shù)據(jù)的情況。 消息傳遞 進(jìn)程間的數(shù)據(jù)交換以格式化的消息為單位。進(jìn)程通過操作系統(tǒng)提供的“發(fā)送消息/接受消息”兩個原語進(jìn)行數(shù)據(jù)交換。 一個格式化的消息可以分為消息頭和消息體。消息頭包括：發(fā)送進(jìn)程ID、接受進(jìn)程ID、消息類型、消息長度等格式化的信息（計算機(jī)網(wǎng)絡(luò)中發(fā)送的“報文”其實就是一種格式化的消息）。 消息傳遞也分為兩種方式： 通信方式 詳情 直接通信方式 消息直接掛到接受進(jìn)程的消息緩沖隊列上 間接通信方式 消息要先發(fā)送到中間實體（信箱）中，因此也稱為“信箱通信方式”。如：計網(wǎng)中的電子郵件系統(tǒng)。

2.8 并行計算模型

PRAM模型(Parallel Random Access Machine，并行隨機(jī)存取機(jī)器)：也稱為共享存儲的SIMD模型。其有一個假定的無限大的集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計算。其中PRAM-CRCW(同時讀同時寫)是最強(qiáng)的計算模型，其隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。

異步APRAM模型

BSP模型(Bulk Synchronous Parallel，大同步并行)：一種分布存儲的多計算機(jī)模型，計算是由一系列用全部同步分開的、周期為L的超級步所組成。在各超級步中，每個處理器均執(zhí)行局部計算，并通過選路器接收和發(fā)送消息。

LogP模型：一種分布存儲的、點到點通信的多處理機(jī)模型。是比PRAM和BSP更一般的并行計算模型

2.9 并行算法一般設(shè)計過程

PCAM設(shè)計方法學(xué)

劃分：分解成小任務(wù)，開拓并發(fā)性

通訊：確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測劃分的合理性

組合：依據(jù)任務(wù)的局部性，組合成更大的任務(wù)

映射：將每個任務(wù)分配到處理器上，提高算法的性能（負(fù)載均衡）

一二階段：考慮并發(fā)性、可擴(kuò)放性，尋求具有這些特征的并行算法，即前期主要考慮如并發(fā)性等與機(jī)器無關(guān)的特性。

三四階段： 將注意力放在局部性及其它與性能有關(guān)的特性上，即后期考慮與機(jī)器有關(guān)的特性。

2.10 程序性能評價與優(yōu)化

并行執(zhí)行時間=計算時間+并行開銷時間+相互通信時間

存儲器性能：估計存儲器的帶寬B

并行與通信開銷的測量：乒乓方法

加速比性能定律

我們用p表示處理器數(shù)，用Wp表示使用具有p個處理器的多處理機(jī)的執(zhí)行所需的時間，Ws表示使用單處理器系統(tǒng)執(zhí)行時間。

Amdahl定律：固定負(fù)載的加速公式S=Ws+wp/ws+wp/p,為了歸一化可將Ws+Wp

看做f+1-f。對加速公式求極限，當(dāng)p趨近與無窮時，極限為S = 1/f。這表明了隨著處理器數(shù)目的無限增多，并行系統(tǒng)所能達(dá)到的加速之上限為1/f。

Gustafson定律：S=Ws+pWp/Ws+Wp。這表明隨著處理器數(shù)目的增加，加速幾乎與處理器數(shù)成比例的線性增加，串行比例f不再是程序的瓶頸。

3 OpenMP并行編程模型

3.1 OpenMP概述

OpenMP是由OpenMP Architecture Review Board牽頭提出的，并已被廣泛接受。其所支持的語言包括C、C++、Fortran。

OpenMP采用fork-join的執(zhí)行模式，開始的時候只存在一個主線程，當(dāng)需要進(jìn)行并行計算的時候，派生出若干個分支線程來執(zhí)行并行任務(wù)。當(dāng)并行代碼執(zhí)行完成之后，分支線程會合，并把控制流程交給單獨的主線程。

3.2 OpenMP語句模式

OpenMP通過編譯指導(dǎo)命令來并行化，什么是編譯指導(dǎo)命令？簡單來說就是我們平常寫的#開頭的語句，通過程序中插入的這些編譯指導(dǎo)命令，計算機(jī)就會完成并行計算的工作。在C/C++程序中，OpenMP的所有的編譯指導(dǎo)命令都是以#pragma omp開始的，后面跟具體的功能指導(dǎo)命令，命令形式如下：

#pragma omp 指令 子句，子句，子句……

注意：由于我不太會C，所以這里使用C++。如果是第一次使用C++的話，可以簡單理解為C++和C在以下代碼中的不同僅限于輸出是使用cout，而C使用printf。C++換行采用endl。且將要輸出的東西由<<流向cout。

3.3 OpenMP簡單演示

我們先從最簡單的一個并行程序開始。在下面的代碼中，我們只用parallel制導(dǎo)命令開啟并行域，需要注意的是，如果不指定線程數(shù)的話默認(rèn)啟用與CPU核心數(shù)同等的線程數(shù)。

#include<omp.h> #include<iostream> using namespace std; int main() { #pragma omp parallel ??? { ???????? cout << "Hello, world!" << endl; ??? } }

可以看出，從#pragma omp parallel開始的花括號內(nèi)就是并行域。parallel制導(dǎo)命令表示接下來由花括號括起來的區(qū)域?qū)?chuàng)建多個線程并行執(zhí)行。

我們還可以使用num_threads子句來控制線程的個數(shù)，需要注意的是，一般設(shè)置的線程數(shù)不超過CPU核心數(shù)，如下：

#include<omp.h> #include<iostream> using namespace std; int main() { ??? omp_set_num_threads(2);//指定線程數(shù)為2 ??? #pragma omp parallel ??? { ???????? cout << "Hello, world!" << endl; ??? } }

我們可以使用制導(dǎo)命令for來提升for循環(huán)迭代的速度。并且可以使用omp_get_thread_num()查看對應(yīng)任務(wù)在并行域中使用的線程號。在下面的代碼演示中，我使用了for循環(huán)來循環(huán)4次，每次循環(huán)中打印本次循環(huán)使用的線程號。我指定了兩條線程，線程號從0開始，說明任務(wù)只會使用0號線程或者1號線程。

#include<omp.h> #include<iostream> using namespace std; int main() { ??? omp_set_num_threads(2); #pragma omp parallel ??? { #pragma omp for ???????? for (int i = 0; i < 4; i++) ???????????? cout << omp_get_thread_num() << endl; ??? } }

OpenMP實際上允許for寫在parallel后面，即#pragma omp parallel for，不過這樣寫的壞處是會踩坑，所以平時建議不要這么寫。

3.4 Schedule關(guān)于for循環(huán)的調(diào)度

在以上的演示中，我們發(fā)現(xiàn)任務(wù)是隨機(jī)分配到各個線程上的，我們并沒有做任何的調(diào)度。在下面的介紹中，我們使用schedule制導(dǎo)來進(jìn)行for循環(huán)的調(diào)度。

schedule的基本形式是schedule(type, size)，其中type參數(shù)有四種，分別是：1.static, 2.dynamic, 3.guided, 4.runtime，而size參數(shù)時整型數(shù)據(jù)，其表示循環(huán)迭代次數(shù)劃分的單位。

static參數(shù)

static表示靜態(tài)調(diào)度，這時候不用size參數(shù)，分配給每個程序的都是n/t次迭代，n為迭代次數(shù)，t為并行的線程數(shù)目。在下面的代碼中，我指定了兩條線程，且循環(huán)8次，則實際迭代次數(shù)只有4次。

#include<omp.h> #include<iostream> using namespace std; int main() { ??? omp_set_num_threads(2); #pragma omp parallel for schedule(static) ??? for (int i = 0; i < 8; i++) ???????? cout << omp_get_thread_num() << endl; }

dynamic參數(shù)

動態(tài)調(diào)度模式是先到先得的方式進(jìn)行任務(wù)分配，不用size參數(shù)的時候，先把任務(wù)干完的線程先取下一個任務(wù)，以此類推，而不是一開始就分配固定的任務(wù)數(shù)。使用size參數(shù)的時候，分配的任務(wù)以size為單位，一次性分配size個。雖然很智能，在任務(wù)難度不均衡的時候適合用dynamic，否則會引起過多的任務(wù)動態(tài)申請的開銷。

guided參數(shù)

剛開始每個線程會分配到比較大的迭代塊，后來分配到的迭代塊逐漸遞減，沒有指定size就會降到1，否則降到size。

runtime參數(shù)

基本不會用到

3.5 設(shè)置環(huán)境變量（拓展）

這里設(shè)置環(huán)境變量你可以理解為在外面設(shè)置好的規(guī)則，程序內(nèi)都必須遵從這個規(guī)則。常見的環(huán)境變量有：

OMP_SCHEDULE：用于for和parallel for中，決定了循環(huán)的各個迭代如何在處理中進(jìn)行分配。

OMP_NUM_THREADS：定義執(zhí)行中所能使用的最大線程數(shù)。

OMP_DYNAMIC：確定是否動態(tài)設(shè)定并行域執(zhí)行部分的線程數(shù)

OMP_NESTED：確定是否允許嵌套并行

3.6 sections制導(dǎo)指令

用sections把不同的區(qū)域交給不同的線程去執(zhí)行。在下面的代碼中，我開啟三條線程，并且使用section制導(dǎo)開啟三塊區(qū)域，每個區(qū)域由一個線程所負(fù)責(zé)。

#include<omp.h> #include<iostream> using namespace std; int main() { ??? omp_set_num_threads(3); #pragma omp parallel sections ??? { #pragma omp section ???????? { ???????????? cout << omp_get_thread_num(); ???????? } #pragma omp section ???????? { ???????????? cout << omp_get_thread_num(); ???????? } #pragma omp section ???????? { ???????????? cout << omp_get_thread_num(); ???????? } ??? } }

3.7 single制導(dǎo)指令（拓展）

single制導(dǎo)指令所包含的代碼段只有一個線程執(zhí)行，別的線程跳過該代碼，如果沒有nowait子句，那么其他線程將會在single制導(dǎo)指令結(jié)束的隱式同步點等待，有nowait子句則其他線程將跳過等待往下執(zhí)行。在下面的代碼中，我開啟四條線程，可以發(fā)現(xiàn)，只有一條線程服務(wù)于single制導(dǎo)命令下的代碼段。

#include<omp.h> #include<iostream> using namespace std; int main() { ??? omp_set_num_threads(4); #pragma omp parallel ??? { #pragma omp single ???????? { ???????????? cout << "single thread=" << omp_get_thread_num() << endl; ???????? } ???????? cout << omp_get_thread_num() << endl; ??? } }

3.8 共享任務(wù)結(jié)構(gòu)

共享任務(wù)結(jié)構(gòu)將它所包含的代碼劃分給線程組的各成員執(zhí)行

不產(chǎn)生新的線程

在共享任務(wù)結(jié)構(gòu)的入口點沒有路障

在其結(jié)束處有一個隱含的路障

DO/FOR是最常用的循環(huán)，并且有SCHEDULE選項，可以指定采用何種調(diào)度算法

SECTIONS可以讓并行任務(wù)流水線執(zhí)行（詳見3.6）

SINGLE只有一個處理機(jī)執(zhí)行之（詳見3.7）

3.9 OpenMP的優(yōu)點和缺點

優(yōu)點

提供了一個可用的編程標(biāo)準(zhǔn)

可移植，簡單，可擴(kuò)展

靈活支持多線程，具有負(fù)載均衡的潛在能力

缺點

只適用于硬件共享存儲型的機(jī)器

動態(tài)可變的線程數(shù)使得支持起來困難

3.10 常用子句的補(bǔ)充

private：指定每個線程都有它自己的變量私有副本

firstprivate：指定每個線程都有它自己的變量私有副本，并且變量要被繼承主線程中的初值。

lastprivate：主要是用來指定將線程中的私有變量的值在并行處理結(jié)束后復(fù)制回主線程中的對應(yīng)變量。

nowait：忽略指定中暗含的等待

num_threads：指定線程的個數(shù)

schedule：指定如何調(diào)度for循環(huán)迭代

shared：指定一個或多個變量為多個線程間的共享變量

ordered：用來指定for循環(huán)的執(zhí)行要按順序執(zhí)行

copyprivate：用于single指令中的指定變量為多個線程的共享變量

copyin：用來指定一個threadprivate的變量的值要用主線程的值進(jìn)行初始化。

default：用來指定并行處理區(qū)域內(nèi)的變量的使用方式，缺省是shared。

4 MPI并行編程模型

4.1 拓展：什么是MPI

MPI是一個跨語言的通訊協(xié)議，用于編寫并行計算機(jī)。支持點對點和廣播。MPI的目標(biāo)是高性能，大規(guī)模性，和可移植性。MPI在今天仍為高性能計算的主要模型。

主要的MPI-1模型不包括共享內(nèi)存概念，MPI-2只有有限的分布共享內(nèi)存概念。 但是MPI程序經(jīng)常在共享內(nèi)存的機(jī)器上運行。在MPI模型周邊設(shè)計程序比在NUMA架構(gòu)下設(shè)計要好因為MPI鼓勵內(nèi)存本地化。

MPI是一個在平行計算中傳遞消息的庫的標(biāo)準(zhǔn)，由實現(xiàn)人員和使用人員來遵守。目前的實現(xiàn)版本有MPICH2， Argonne National Laboratory實現(xiàn)，他還有好幾個派生子項目。

4.2 MPI基本函數(shù)

MPI_Init(…);

MPI_Comm_size(…);

MPI_Comm_rank(…);

MPI_Send(…);

MPI_Recv(…);

MPI_Finalize();

int MPI_Init(int* argc,char** argv[])

用于并行環(huán)境初始化,其后面的代碼到MPI_Finalize()函數(shù)之前的代碼段都會在每個進(jìn)程中（并行環(huán)境）執(zhí)行一次。

除了MPI_Initialized()外，其余所有的MPI函數(shù)應(yīng)該在其后才被調(diào)用

MPI系統(tǒng)將通過argc，argv得到命令行參數(shù)，也就是說main函數(shù)必須帶參數(shù)，否則會報錯。

int MPI_Finalize (void)

退出MPI系統(tǒng)， 所有進(jìn)程正常退出都必須調(diào)用。 表明并行代碼的結(jié)束,結(jié)束除主進(jìn)程外其它進(jìn)程。

串行代碼仍可在主進(jìn)程(rank = 0)上運行， 但不能再有MPI函數(shù)（包括MPI_Init()）。

int MPI_Comm_size (MPI_Comm comm ,int* size )

獲得進(jìn)程個數(shù) size。

指定一個通信子,也指定了一組共享該空間的進(jìn)程, 這些進(jìn)程組成該通信子的group（組）。

獲得通信子comm中規(guī)定的group包含的進(jìn)程的數(shù)量。

int MPI_Comm_rank (MPI_Comm comm ,int* rank)

得到本進(jìn)程在通信空間中的rank值,即在組中的邏輯編號(該 rank值為0到p-1間的整數(shù),相當(dāng)于進(jìn)程的ID。)

int MPI_Send( void *buff, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)

void *buff：你要發(fā)送的變量。

int count：你發(fā)送的消息的個數(shù)（注意：不是長度，例如你要發(fā)送一個int整數(shù)，這里就填寫1，如要是發(fā)送“hello”字符串，這里就填寫6（C語言中字符串末有一個結(jié)束符，需要多一位））。

MPI_Datatype datatype：你要發(fā)送的數(shù)據(jù)類型，這里需要用MPI定義的數(shù)據(jù)類型，可在網(wǎng)上找到，在此不再羅列。

int dest：目的地進(jìn)程號，你要發(fā)送給哪個進(jìn)程，就填寫目的進(jìn)程的進(jìn)程號。

int tag：消息標(biāo)簽，接收方需要有相同的消息標(biāo)簽才能接收該消息。

MPI_Comm comm：通訊域。表示你要向哪個組發(fā)送消息。

int MPI_Recv( void *buff, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)

void *buff：你接收到的消息要保存到哪個變量里。

int count：你接收消息的消息的個數(shù)（注意：不是長度，例如你要發(fā)送一個int整數(shù)，這里就填寫1，如要是發(fā)送“hello”字符串，這里就填寫6（C語言中字符串末有一個結(jié)束符，需要多一位））。它是接收數(shù)據(jù)長度的上界. 具體接收到的數(shù)據(jù)長度可通過調(diào)用MPI_Get_count 函數(shù)得到。

MPI_Datatype datatype：你要接收的數(shù)據(jù)類型，這里需要用MPI定義的數(shù)據(jù)類型，可在網(wǎng)上找到，在此不再羅列。

int dest：接收端進(jìn)程號，你要需要哪個進(jìn)程接收消息就填寫接收進(jìn)程的進(jìn)程號。

int tag：消息標(biāo)簽，需要與發(fā)送方的tag值相同的消息標(biāo)簽才能接收該消息。

MPI_Comm comm：通訊域。

MPI_Status *status：消息狀態(tài)。接收函數(shù)返回時，將在這個參數(shù)指示的變量中存放實際接收消息的狀態(tài)信息，包括消息的源進(jìn)程標(biāo)識，消息標(biāo)簽，包含的數(shù)據(jù)項個數(shù)等。

4.3 消息傳遞的特點

在消息傳遞模型中，一個并行應(yīng)用由一組進(jìn)程組成，每個進(jìn)程的代碼是本地的，只能訪問私有數(shù)據(jù)，進(jìn)程之間通過傳遞消息實現(xiàn)數(shù)據(jù)共享和進(jìn)程同步。

優(yōu)點：用戶可以對并行性的開發(fā)、數(shù)據(jù)分布和通信實現(xiàn)完全控制。

缺點：

要求程序員顯式地處理通信問題，如：消息傳遞調(diào)用的位置，數(shù)據(jù)移動，數(shù)據(jù)復(fù)制，數(shù)據(jù)操作，數(shù)據(jù)的一致性等等。

對大多數(shù)科學(xué)計算程序來說，消息傳遞模型的真正困難還在于顯式的域分解。也就是說，將對相應(yīng)數(shù)據(jù)的操作限定在指定的處理器上進(jìn)行。在處理器上只能看見整個分布數(shù)據(jù)的一部分。

無法以漸進(jìn)的方式、通過逐步將串行代碼轉(zhuǎn)換成并行代碼而開發(fā)出來，大量的散布在程序各處的域分解要求整個程序由串行到并行的轉(zhuǎn)換一次性實現(xiàn)，這是消息傳遞的一個明顯的缺點。

總結(jié)

以上是生活随笔為你收集整理的并行计算总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。