（本人剛剛完成這篇長(zhǎng)文章的翻譯，尚未認(rèn)真校對(duì)。若里面有翻譯錯(cuò)誤和打字錯(cuò)誤敬請(qǐng)諒解，并請(qǐng)參考原貼）

1 摘要

帖子的原文： Introduction to Parallel Computing Tutorial

這篇帖子旨在為并行計(jì)算這一廣泛而宏大的話題提供一個(gè)非?？?/p>

速的概述，作為隨后教程的先導(dǎo)。因此，它只涵蓋了并行計(jì)算的基礎(chǔ)知識(shí)，實(shí)用于剛剛開始熟悉該主題的初學(xué)者。我們并不會(huì)深入討論并行計(jì)算，因?yàn)檫@將花費(fèi)大量的時(shí)間。本教程從對(duì)并行計(jì)算是什么以及如何使用開始，討論與其相關(guān)的概念和術(shù)語，然后解析并行內(nèi)存架構(gòu)(parallel memory architecture)以及編程模型(programming models)等。這些主題之后是一系列關(guān)于設(shè)計(jì)和運(yùn)行并行計(jì)算程序的復(fù)雜問題的實(shí)踐討論。最后，本教程給出了幾個(gè)并行化簡(jiǎn)單串行程序的示例。

2 概述

2.1 什么是并行計(jì)算？

串行計(jì)算： 傳統(tǒng)的軟件通常被設(shè)計(jì)成為串行計(jì)算模式，具有如下特點(diǎn)：

• 一個(gè)問題被分解成為一系列離散的指令；
• 這些指令被順次執(zhí)行；
• 所有指令均在一個(gè)處理器上被執(zhí)行；
• 在任何時(shí)刻，最多只有一個(gè)指令能夠被執(zhí)行。
  

例如，

并行計(jì)算： 簡(jiǎn)單來講，并行計(jì)算就是同時(shí)使用多個(gè)計(jì)算資源來解決一個(gè)計(jì)算問題：

一個(gè)問題被分解成為一系列可以并發(fā)執(zhí)行的離散部分；

每個(gè)部分可以進(jìn)一步被分解成為一系列離散指令；

來自每個(gè)部分的指令可以在不同的處理器上被同時(shí)執(zhí)行；

需要一個(gè)總體的控制/協(xié)作機(jī)制來負(fù)責(zé)對(duì)不同部分的執(zhí)行情況進(jìn)行調(diào)度。

例如，

這里的 計(jì)算問題 需要具有如下特點(diǎn)：

• 能夠被分解成為并發(fā)執(zhí)行離散片段；
• 不同的離散片段能夠被在任意時(shí)刻執(zhí)行；
• 采用多個(gè)計(jì)算資源的花費(fèi)時(shí)間要小于采用單個(gè)計(jì)算資源所花費(fèi)的時(shí)間。

這里的 計(jì)算資源 通常包括：

• 具有多處理器/多核(multiple processors/cores)的計(jì)算機(jī)；
• 任意數(shù)量的被連接在一起的計(jì)算機(jī)。

并行計(jì)算機(jī)：

通常來講，從硬件的角度來講，當(dāng)前所有的單機(jī)都可以被認(rèn)為是并行的：

• 多功能單元（L1緩存，L2緩存，分支，預(yù)取，解碼，浮點(diǎn)數(shù)，圖形處理器，整數(shù)等）
• 多執(zhí)行單元/內(nèi)核
• 多硬件線程

IBM BG/Q Compute Chip with 18 cores (PU) and 16 L2 Cache units (L2)

通過網(wǎng)絡(luò)連接起來的多個(gè)單機(jī)也可以形成更大的并行計(jì)算機(jī)集群:

例如，下面的圖解就顯示了一個(gè)典型的LLNL并行計(jì)算機(jī)集群：

• 每個(gè)計(jì)算結(jié)點(diǎn)就是一個(gè)多處理器的并行計(jì)算機(jī)；
• 多個(gè)計(jì)算結(jié)點(diǎn)用無限寬帶網(wǎng)絡(luò)連接起來；
• 某些特殊的結(jié)點(diǎn)（通常也是多處理器單機(jī)）被用來執(zhí)行特定的任務(wù)。

2.2 為什么要并行計(jì)算？

真實(shí)世界就是高度并行的：

• 自然界中的萬事萬物都在并發(fā)的，按照其內(nèi)在時(shí)間序列運(yùn)行著；
• 和串行計(jì)算相比，并行計(jì)算更適用于對(duì)現(xiàn)實(shí)世界中的復(fù)雜現(xiàn)象進(jìn)行建模，模擬和理解；
• 例如，可以想象對(duì)這些進(jìn)行順序建模：
  

主要理由：

節(jié)約時(shí)間和成本：

1）理論上來講，在一個(gè)任務(wù)上投入更多的資源有利于縮短其完成時(shí)間，從而降低成本；

2）并行計(jì)算機(jī)可以由大量廉價(jià)的單機(jī)構(gòu)成，從而節(jié)約成本。

解決更大規(guī)模更復(fù)雜的問題：

1）很多問題的規(guī)模和復(fù)雜度使得其難以在一個(gè)單機(jī)上面完成；

2）一個(gè)有趣的例子：(Grand Challenge Problems)。

3）網(wǎng)頁(yè)搜索引擎/數(shù)據(jù)庫(kù)每秒處理百萬級(jí)別的吞吐量。

提供并發(fā)性：

1）單個(gè)計(jì)算資源某個(gè)時(shí)間段只能做一件事情，而多計(jì)算資源則可以同時(shí)做多件事情；

2）協(xié)同網(wǎng)絡(luò)可以使得來自世界不同地區(qū)的人同時(shí)虛擬地溝通。

利用非局部的資源：

1）可以利用更廣范圍中的網(wǎng)絡(luò)資源；

2）SETI@home的例子；

以及3）Folding@home的例子。

更好地利用并行硬件：

1）現(xiàn)代計(jì)算機(jī)甚至筆記本電腦在架構(gòu)上都屬于多處理器/多核的；

2）并行軟件已經(jīng)適用于多核的并行硬件條件，例如線程等；

3）在大多數(shù)情況下，運(yùn)行在現(xiàn)代計(jì)算機(jī)上的串行程序?qū)嶋H上浪費(fèi)了大量的計(jì)算資源。

并行計(jì)算的未來：

在過去的二十多年中，快速發(fā)展的網(wǎng)絡(luò)，分布式系統(tǒng)以及多處理器計(jì)算機(jī)架構(gòu)（甚至在桌面機(jī)級(jí)別上）表明并行化才是計(jì)算的未來；

在同一時(shí)期，超級(jí)計(jì)算機(jī)的性能已經(jīng)有了至少50萬倍的增加，而且目前還沒有達(dá)到極限的跡象；

目前的峰值計(jì)算速度已經(jīng)達(dá)到了10181018/秒

2.3 誰都在使用并行計(jì)算？

科學(xué)界和工程界：

從歷史上來講，并行計(jì)算就被認(rèn)為是“計(jì)算的高端”，許多科學(xué)和工程領(lǐng)域的研究團(tuán)隊(duì)在對(duì)很多領(lǐng)域的問題建模上都采用了并行計(jì)算這一模式，包括：大氣與地球環(huán)境、應(yīng)用物理、生物科學(xué)、遺傳學(xué)、化學(xué)、分子科學(xué)、機(jī)械工程、電氣工程、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、國(guó)防和武器研發(fā)等。

工業(yè)界和商業(yè)界：

如今，商業(yè)應(yīng)用為更快速計(jì)算機(jī)的研發(fā)提供了更強(qiáng)勁的動(dòng)力。這些商業(yè)應(yīng)用程序需要以更復(fù)雜的方式處理大量數(shù)據(jù)，例如：大數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、石油勘探、網(wǎng)頁(yè)搜索引擎、基于web的商業(yè)服務(wù)、醫(yī)學(xué)成像和診斷、跨國(guó)公司管理、高級(jí)圖形學(xué)技術(shù)以及虛擬現(xiàn)實(shí)、網(wǎng)絡(luò)視頻和多媒體技術(shù)、協(xié)同工作環(huán)境等。

全球應(yīng)用：

并行計(jì)算目前在實(shí)際上被廣泛采用于大量應(yīng)用中

3 概念和術(shù)語

3.1 馮諾依曼體系結(jié)構(gòu)

以匈牙利數(shù)學(xué)家約翰·馮諾依曼命名的這一計(jì)算機(jī)體系結(jié)構(gòu)，出現(xiàn)在他1945年發(fā)表的一篇論文中。這也通常被稱為“存儲(chǔ)程序計(jì)算機(jī)”——程序指令和數(shù)據(jù)都被保存在存儲(chǔ)器中，這與早期通過“硬接線”編程的計(jì)算機(jī)不同。從此以后，所有的計(jì)算機(jī)走遵從這一基本架構(gòu)：

- 四個(gè)組成部分：1）內(nèi)存；2）控制器；3）處理器；4）輸入輸出。

- 讀寫操作：支持隨機(jī)存儲(chǔ)的內(nèi)存用來同時(shí)保存程序指令和數(shù)據(jù)：

1）程序指令用來指導(dǎo)計(jì)算機(jī)操作；

2）數(shù)據(jù)是程序用來操作的對(duì)象。

- 控制器：從內(nèi)存中讀取指令或者數(shù)據(jù)，對(duì)這些指令進(jìn)行解碼并且順序執(zhí)行這些指令。
- 處理器：提供基本的算術(shù)和邏輯操作。
- 輸入輸出設(shè)備：是人機(jī)交互的接口。

那么馮諾依曼體系結(jié)構(gòu)和并行計(jì)算有什么關(guān)系呢？答案是：并行計(jì)算機(jī)仍然遵從這一基本架構(gòu)，只是處理單元多于一個(gè)而已，其它的基本架構(gòu)完全保持不變。

3.2 弗林的經(jīng)典分類

有不同的方法對(duì)并行計(jì)算機(jī)進(jìn)行分類（具體例子可參見并行計(jì)算分類）。

一種被廣泛采用的分類被稱為弗林經(jīng)典分類，誕生于1966年。弗林分類法從指令流和數(shù)據(jù)流兩個(gè)維度區(qū)分多處理器計(jì)算機(jī)體系結(jié)構(gòu)。每個(gè)維度有且僅有兩個(gè)狀態(tài)：?jiǎn)蝹€(gè)或者多個(gè)。

下面?zhèn)€矩陣定義了弗林分類的四個(gè)可能狀態(tài)：

單指令單數(shù)據(jù)(SISD)： SISD是標(biāo)準(zhǔn)意義上的串行機(jī)，具有如下特點(diǎn)：

1）單指令：在每一個(gè)時(shí)鐘周期內(nèi)，CPU只能執(zhí)行一個(gè)指令流；

2）單數(shù)據(jù)：在每一個(gè)時(shí)鐘周期內(nèi)，輸入設(shè)備只能輸入一個(gè)數(shù)據(jù)流；

3）執(zhí)行結(jié)果是確定的。這是最古老的一種計(jì)算機(jī)類型。

單指令多數(shù)據(jù)(SIMD)： SIMD屬于一種類型的并行計(jì)算機(jī)，具有如下特點(diǎn)：

1）單指令：所有處理單元在任何一個(gè)時(shí)鐘周期內(nèi)都執(zhí)行同一條指令；

2）多數(shù)據(jù)：每個(gè)處理單元可以處理不同的數(shù)據(jù)元素；

3）非常適合于處理高度有序的任務(wù)，例如圖形/圖像處理；

4）同步（鎖步）及確定性執(zhí)行；

5）兩個(gè)主要類型：處理器陣列和矢量管道。

多指令單數(shù)據(jù)(MISD)：MISD屬于一種類型的并行計(jì)算機(jī)，具有如下特點(diǎn)：

1）多指令：不同的處理單元可以獨(dú)立地執(zhí)行不同的指令流；

2）單數(shù)據(jù)：不同的處理單元接收的是同一單數(shù)據(jù)流。這種架構(gòu)理論上是有的，但是工業(yè)實(shí)踐中這種機(jī)型非常少。

多指令多數(shù)據(jù)(MIMD)： MIMD屬于最常見的一種類型的并行計(jì)算機(jī)，具有如下特點(diǎn)：

1）多指令：不同的處理器可以在同一時(shí)刻處理不同的指令流；

2）多數(shù)據(jù)：不同的處理器可以在同一時(shí)刻處理不同的數(shù)據(jù)；

3）執(zhí)行可以是同步的，也可以是異步的，可以是確定性的，也可以是不確定性的。這是目前主流的計(jì)算機(jī)架構(gòu)類型，目前的超級(jí)計(jì)算機(jī)、并行計(jì)算機(jī)集群系統(tǒng)，網(wǎng)格，多處理器計(jì)算機(jī)，多核計(jì)算機(jī)等都屬于這種類型。

值得注意的是，許多MIMD類型的架構(gòu)中實(shí)際也可能包括SIMD的子架構(gòu)。

3.3 一些常見的并行計(jì)算術(shù)語

和其它一些領(lǐng)域一樣，并行計(jì)算也有自己的“術(shù)語”。下面列出了與并行計(jì)算相關(guān)聯(lián)的一些常用術(shù)語，其中大部分術(shù)語我們?cè)诤竺孢€會(huì)進(jìn)行更詳細(xì)的討論。

• 結(jié)點(diǎn)(Node)：

也就是一個(gè)獨(dú)立的“計(jì)算機(jī)單元”。通常由多個(gè)CPU處理器/處理內(nèi)核，內(nèi)存，網(wǎng)絡(luò)接口等組成。結(jié)點(diǎn)聯(lián)網(wǎng)在一起以構(gòu)成超級(jí)計(jì)算機(jī)。

• 中央處理器/套接字/處理器/核(CPU / Socket / Processor / Core)：

這些術(shù)語也取決于我們討論的語境。在過去，中央處理器通常是計(jì)算機(jī)中的一個(gè)單個(gè)執(zhí)行單元。之后多處理器被植入到一個(gè)結(jié)點(diǎn)中。接著處理器又被設(shè)計(jì)成為多核，每個(gè)核成為一個(gè)獨(dú)立的處理單元。具有多核的中央處理器有時(shí)候又被稱為“套接字”——實(shí)際上也沒有統(tǒng)一標(biāo)準(zhǔn)。所以目前來講，我們稱一個(gè)結(jié)點(diǎn)上具有多個(gè)中央處理器，每個(gè)中央處理器上又具有多個(gè)內(nèi)核。

• 任務(wù)(Task)：

任務(wù)通常是指一個(gè)邏輯上離散的計(jì)算工作部分。一個(gè)任務(wù)通常是一段程序或者一段類似于程序的指令集合，可以由一個(gè)處理器進(jìn)行處理。一個(gè)并行程序通常由多個(gè)任務(wù)構(gòu)成，并且可以運(yùn)行在多個(gè)處理器上。

• 流水線(Pipelining)：

可以將任務(wù)分解成為不同的步驟，并且由不同的處理單元完成，里面有輸入流通過。這非常類似于一個(gè)裝配線，屬于一種類型的并行計(jì)算。

• 共享內(nèi)存(Shared Memory)：

從嚴(yán)格的硬件角度來講，共享內(nèi)存描述了一種計(jì)算機(jī)架構(gòu)，其中所有的處理器都可以對(duì)共同的物理內(nèi)存進(jìn)行直接存?。ㄍǔＪ峭ㄟ^總線）。從編程的角度來講，共享內(nèi)存描述了一種模型，其中所有的并行任務(wù)都具有同一內(nèi)存形態(tài)，并且都可以直接對(duì)同一內(nèi)存區(qū)域進(jìn)行直接定位和存取，而無論該物理內(nèi)存實(shí)際上在哪里（也許在千里之外的另外一個(gè)計(jì)算機(jī)上？）。

• 對(duì)稱多處理器(Symmetric Multi-Processor (SMP))：

屬于一種共享內(nèi)存的硬件架構(gòu)，并且不同的處理器對(duì)內(nèi)存以及其它資源都具有同等的訪問權(quán)限（個(gè)人理解，就是不同處理器在角色上沒有任何區(qū)別）。

• 分布式內(nèi)存(Distributed Memory)：

在硬件中，表示基于網(wǎng)絡(luò)的內(nèi)存存取方式；在編程模型中，表示任務(wù)僅僅能夠從邏輯上“看到”本機(jī)上的內(nèi)存，但是在其它任務(wù)執(zhí)行的時(shí)候，必須通過通訊才能對(duì)其它任務(wù)所運(yùn)行的機(jī)器上的內(nèi)存進(jìn)行存取。

• 通訊(communications)：

并行任務(wù)通常需要數(shù)據(jù)交換。實(shí)現(xiàn)數(shù)據(jù)交換的方式有多種，例如通過共享內(nèi)存或者通過網(wǎng)絡(luò)。但是通常意義上，數(shù)據(jù)交換指的就是通訊，而無論其實(shí)現(xiàn)方式。

• 同步(Synchronization)：

指的是并行任務(wù)之間的實(shí)時(shí)協(xié)調(diào)，通常伴隨著通訊(communication)。同步通常由在程序中設(shè)立同步點(diǎn)來實(shí)現(xiàn)，也就是說，在其它任務(wù)沒有執(zhí)行到這一同步點(diǎn)的時(shí)候，某一任務(wù)不能進(jìn)一步執(zhí)行后面的指令。同步通常涉及到需要等待其它任務(wù)的完成，因此有時(shí)候會(huì)增加并行程序的執(zhí)行時(shí)間。

• 粒度(Granularity)：

在并行計(jì)算中，粒度定量地描述了計(jì)算與通訊的比率。粗粒度表示在通訊過程中需要做大量的計(jì)算性工作；細(xì)粒度則表示在通訊過程中需要做的計(jì)算性工作并不多。

• 加速比(Observed Speedup)：

這是檢測(cè)并行計(jì)算性能的最簡(jiǎn)單并且最被廣泛使用的度量策略，其定義如下：串行計(jì)算的時(shí)鐘周期數(shù)并行計(jì)算的時(shí)鐘周期數(shù)串行計(jì)算的時(shí)鐘周期數(shù)并行計(jì)算的時(shí)鐘周期數(shù)。

• 并行開銷(Parallel Overhead)：

指的是相對(duì)于做實(shí)際計(jì)算，做協(xié)調(diào)并行任務(wù)所需要花費(fèi)的時(shí)間總數(shù)。影響并行開銷的因素主要包括：

1）任務(wù)啟動(dòng)時(shí)間；

2）同步；

3）數(shù)據(jù)通訊；

4）由并行語言，鏈接庫(kù)，操作系統(tǒng)等因素而導(dǎo)致的軟件開銷；

5）任務(wù)終止時(shí)間。

• 大規(guī)模并行(Massive Parallel)：

指那些包含并行系統(tǒng)的硬件——擁有很多的處理元件。這里的“很多”可能會(huì)隨著硬件條件的進(jìn)步而不斷增加，但目前，最大的并行系統(tǒng)所擁有的處理元件高達(dá)上百萬件。

• 尷尬并行(Embarrassingly Parallel)：

指的是同時(shí)解決很多類似而又獨(dú)立的任務(wù)，其中任務(wù)之間幾乎沒有需要協(xié)調(diào)的地方。

• 可擴(kuò)展性(Scalability)：

指的是并行系統(tǒng)（包括軟件和硬件）通過添加更多資源來成比例增加并行速度的能力。影響可擴(kuò)展性的因素主要包括：

1）硬件，尤其是內(nèi)存-處理器帶寬以及網(wǎng)絡(luò)通訊的質(zhì)量和速度；

2）應(yīng)用算法；

3）相對(duì)并行開銷；

4）具體應(yīng)用的特征。

3.4 并行程序的缺陷和代價(jià)

阿姆達(dá)爾定律： 阿姆達(dá)爾定律說一個(gè)程序的加速比潛力由其可以并行的部分所占的比例而決定，即：
speedup=11−Pspeedup=11−P.

如果沒有代碼可以被并行，那么p = 0，所以加速比為1。如果所有的代碼都可以被并行，那么 p = 1，加速比為無窮大（當(dāng)然只是理論上而言）。如果50%的代碼可以被并行，那么最大的加速比為2，意味著的運(yùn)行速度最快可以被加速到2倍。

如果引入并行程序中的處理器個(gè)數(shù)，則加速比可以被重新定義為：
speedup=1PN+S=11−P+PNspeedup=1PN+S=11−P+PN，
其中P仍然是并行代碼所占的比例，N是處理器個(gè)數(shù)，S是串行代碼所占比例（S = 1 - P）。

之后我們就迅速意識(shí)到并行計(jì)算的極限所在，例如上表所示。

“注明引言：”你可以花費(fèi)一生的時(shí)間使得你的代碼的95%都可以被并行，然而你如論投入多少處理器，都不會(huì)獲得20倍的加速比。

然而，某些問題我們可以通過增加問題的大小來提高其性能。例如：

我們可以增加網(wǎng)格的維度，并且將時(shí)間步長(zhǎng)減半。其結(jié)果是四倍的網(wǎng)格點(diǎn)數(shù)量，以及兩倍的時(shí)間步長(zhǎng)。之后的花費(fèi)時(shí)間將變?yōu)椋?/p>

復(fù)雜性：

通常而言，并行計(jì)算的程序要比相應(yīng)的串行計(jì)算程序更加復(fù)雜，也許復(fù)雜一個(gè)量級(jí)。你不僅需要同時(shí)執(zhí)行不同的指令流，而且需要注意他們之間數(shù)據(jù)的通信。復(fù)雜性通常由涉及軟件開發(fā)周期各個(gè)方面的時(shí)間來確定，主要包括：

1）設(shè)計(jì)；2）編碼；3）調(diào)試；4）調(diào)參；5）維護(hù)。

遵循良好的軟件開發(fā)實(shí)踐對(duì)并行應(yīng)用開發(fā)是至關(guān)重要的，尤其是在除你之外的其他人還需要和你合作的情況下。

可移植性：

由于一些API的標(biāo)準(zhǔn)化，例如MPI，POSIX線程以及OpenMP，并行程序的可移植性問題并不像過去那么嚴(yán)重，然而：

• 所有串行程序中所遇到的可移植性問題都會(huì)出現(xiàn)在相應(yīng)的并行程序中。
• 盡管一些API已經(jīng)被標(biāo)準(zhǔn)話，但是在一些細(xì)節(jié)的實(shí)現(xiàn)上任然有差異，有時(shí)候這些細(xì)節(jié)實(shí)現(xiàn)會(huì)影響到可移植性。
• 操作系統(tǒng)也會(huì)是導(dǎo)致可移植性的關(guān)鍵因素。
• 硬件架構(gòu)的不同有時(shí)候也會(huì)影響到可移植性。

資源需求：

并行編程的主要目標(biāo)就是降低時(shí)鐘等待時(shí)間。然而要做到這一點(diǎn)，需要更多的CPU時(shí)間。例如，一個(gè)在8個(gè)處理器上跑了一個(gè)小時(shí)的并行程序?qū)嶋H上花費(fèi)了8小時(shí)的CPU時(shí)間。

并行程序所需要的內(nèi)存開銷往往要大于相對(duì)應(yīng)的串行程序，這是因?yàn)槲覀冇袝r(shí)候需要復(fù)制數(shù)據(jù)，以滿足庫(kù)和子系統(tǒng)對(duì)并行算法的要求。

對(duì)于運(yùn)行時(shí)間較短的并行陳顧，實(shí)際性能反而有可能比相對(duì)應(yīng)的串行程序有所降低。這是由于并行環(huán)境的建立，任務(wù)創(chuàng)建，通訊，任務(wù)結(jié)束等在這個(gè)運(yùn)行時(shí)間中有可能會(huì)占有比較大的比例。

可擴(kuò)展性：

基于時(shí)間和解決方案的不同，可以將擴(kuò)展性分為強(qiáng)可擴(kuò)展性和弱可擴(kuò)展性：

強(qiáng)可擴(kuò)展性的特點(diǎn)是：

1）在更多處理器被加入的時(shí)候，問題本身的規(guī)模不會(huì)增加；

2）目標(biāo)是將同一問題運(yùn)行的更快；

3）理想狀態(tài)下，相比于對(duì)應(yīng)的串行程序，運(yùn)行時(shí)間為1/P。

弱可擴(kuò)展性的特點(diǎn)是：

1）隨著更多處理器被加入，每個(gè)處理上需要處理的問題規(guī)模保持一致；

2）目標(biāo)是在相同的時(shí)間內(nèi)解決更多規(guī)模的問題；

3）理想狀態(tài)下，在相同時(shí)間內(nèi)，可以解決的問題規(guī)模增加為原問題規(guī)模的P倍。

并行程序的性能提高取決于一系列相互依賴的因素，簡(jiǎn)單地增加更多的處理器并不一定是唯一的方法。

此外，某些問題可能本身存在擴(kuò)展性的極限，因此添加更多的資源有時(shí)候反而會(huì)降低性能。這種情形會(huì)出現(xiàn)在很多并行程序中。

硬件在可擴(kuò)展性方面也扮演者重要角色，例如：1）內(nèi)存-CPU之間的帶寬；2）通訊網(wǎng)絡(luò)的帶寬；3）某個(gè)機(jī)器或者某個(gè)機(jī)器集合中的內(nèi)存大?。?）時(shí)鐘處理速度。

支持并行的庫(kù)或者子系統(tǒng)同樣也會(huì)限制并行程序的可擴(kuò)展性。

4 并行計(jì)算機(jī)的內(nèi)存架構(gòu)

4.1 共享內(nèi)存

一般特征：

共享內(nèi)存的并行計(jì)算機(jī)雖然也分很多種，但是通常而言，它們都可以讓所有處理器以全局尋址的方式訪問所有的內(nèi)存空間。多個(gè)處理器可以獨(dú)立地操作，但是它們共享同一片內(nèi)存。一個(gè)處理器對(duì)內(nèi)存地址的改變對(duì)其它處理器來說是可見的。根據(jù)內(nèi)存訪問時(shí)間，可以將已有的共享內(nèi)存機(jī)器分為統(tǒng)一內(nèi)存存取和非統(tǒng)一內(nèi)存存取兩種類型。

統(tǒng)一內(nèi)存存取(Uniform Memory Access)：

目前更多地被稱為對(duì)稱多處理器機(jī)器(Symmetric Multiprocessor (SMP))，每個(gè)處理器都是相同的，并且其對(duì)內(nèi)存的存取和存取之間都是無差別的。有時(shí)候也會(huì)被稱為CC-UMA (Cache coherent - UMA)。緩存想干意味著如果一個(gè)處理器更新共享內(nèi)存中的位置，則所有其它處理器都會(huì)了解該更新。緩存一致性是在硬件級(jí)別上實(shí)現(xiàn)的。

非統(tǒng)一內(nèi)存存取(Non-Uniform Memory Access)：

通常由兩個(gè)或者多個(gè)物理上相連的SMP。一個(gè)SMP可以存取其它SMP上的內(nèi)存。不是所有處理器對(duì)所有內(nèi)存都具有相同的存取或者存取時(shí)間。通過連接而進(jìn)行內(nèi)存存取速度會(huì)更慢一些。如果緩存相緩存想干的特性在這里仍然被保持，那么也可以被稱為CC-NUMA。

優(yōu)點(diǎn)：

全局地址空間提供了一種用戶友好的編程方式，并且由于內(nèi)存與CPU的階級(jí)程度，使得任務(wù)之間的數(shù)據(jù)共享既快速又統(tǒng)一。

缺點(diǎn)：

最大的缺點(diǎn)是內(nèi)存和CPU之間缺少較好的可擴(kuò)展性。增加更多的CPU意味著更加共享內(nèi)存和緩存想干系統(tǒng)上的存取流量，從而幾何級(jí)別地增加緩存/內(nèi)存管理的工作量。同時(shí)也增加了程序員的責(zé)任，因?yàn)樗枰_保全局內(nèi)存“正確”的訪問以及同步。

4.2 分布式內(nèi)存

一般概念： 分布式內(nèi)存架構(gòu)也可以分為很多種，但是它們?nèi)匀挥幸恍┕餐卣?。分布式?nèi)存結(jié)構(gòu)需要通訊網(wǎng)絡(luò)，將不同的內(nèi)存連接起來。一般而言，處理器會(huì)有它們所對(duì)應(yīng)的內(nèi)存。一個(gè)處理器所對(duì)應(yīng)的內(nèi)存地址不會(huì)映射到其它處理器上，所以在這種分布式內(nèi)存架構(gòu)中，不存在各個(gè)處理器所共享的全局內(nèi)存地址。

由于每個(gè)處理器具有它所對(duì)應(yīng)的局部?jī)?nèi)存，所以它們可以獨(dú)立進(jìn)行操作。一個(gè)本地內(nèi)存上所發(fā)生的變化并不會(huì)被其它處理器所知曉。因此，緩存想干的概念在分布式內(nèi)存架構(gòu)中并不存在。

如果一個(gè)處理器需要對(duì)其它處理器上的數(shù)據(jù)進(jìn)行存取，那么往往程序員需要明確地定義數(shù)據(jù)通訊的時(shí)間和方式，任務(wù)之間的同步因此就成為程序員的職責(zé)。盡管分布式內(nèi)存架構(gòu)中用于數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)結(jié)構(gòu)可以像以太網(wǎng)一樣簡(jiǎn)單，但在實(shí)踐中它們的變化往往也很大。

優(yōu)點(diǎn)：

1）內(nèi)存可以隨著處理器的數(shù)量而擴(kuò)展，增加處理器的數(shù)量的同時(shí)，內(nèi)存的大小也在成比例地增加；

2）每個(gè)處理器可以快速地訪問自己的內(nèi)存而不會(huì)受到干擾，并且沒有維護(hù)全局告訴緩存一致性所帶來的開銷；

3）成本效益：可以使用現(xiàn)有的處理器和網(wǎng)絡(luò)。

缺點(diǎn)：

1）程序員需要負(fù)責(zé)處理器之間數(shù)據(jù)通訊相關(guān)的許多細(xì)節(jié)；

2）將基于全局內(nèi)存的現(xiàn)有數(shù)據(jù)結(jié)構(gòu)映射到該分布式內(nèi)存組織可能會(huì)存在困難；

3）非均勻的內(nèi)存訪問時(shí)間——駐留在遠(yuǎn)程結(jié)點(diǎn)上的數(shù)據(jù)比本地結(jié)點(diǎn)上的數(shù)據(jù)需要長(zhǎng)的多的訪問時(shí)間。

4.3 混合分布式-共享內(nèi)存

一般概念： 目前世界上最大和最快的并行計(jì)算機(jī)往往同時(shí)具有分布式和共享式的內(nèi)存架構(gòu)。共享式內(nèi)存架構(gòu)可以是共線內(nèi)存機(jī)器或者圖形處理單元(GPU)。分布式內(nèi)存組件可以是由多個(gè)共享內(nèi)存/GPU連接而成的系統(tǒng)。每個(gè)結(jié)點(diǎn)只知道自己的內(nèi)存，不知道網(wǎng)絡(luò)上其它結(jié)點(diǎn)的內(nèi)存。因此，需要在不同的機(jī)器上通過網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)通訊。

從目前的趨勢(shì)來看，這種混合式的內(nèi)存架構(gòu)將長(zhǎng)期占有主導(dǎo)地位，并且成為高端計(jì)算在可見的未來中的最好選擇。

優(yōu)缺點(diǎn)：

1）繼承了共享式內(nèi)存和分布式內(nèi)存的優(yōu)缺點(diǎn)；

2）優(yōu)點(diǎn)之一是可擴(kuò)展性；

3）缺點(diǎn)之一是編程的復(fù)雜性。

5. 并行計(jì)算模型

5.1 概述

常見的并行編程模型包括：共享內(nèi)存模型（無線程），線程模型，分布式內(nèi)存/消息傳遞模型，數(shù)據(jù)并行模型，混合模型，單程序多數(shù)據(jù)模型，多程序多數(shù)據(jù)模型。

并行計(jì)算模型是作為硬件和內(nèi)存架構(gòu)之上的一種抽象存在。雖然不一定顯而易見，但這些模型并不和特定的機(jī)器和內(nèi)存架構(gòu)有關(guān)。事實(shí)上，任何一個(gè)并行計(jì)算模型從理論上來講都可以實(shí)現(xiàn)在任何一種硬件上。下面是兩個(gè)例子。

在分布式內(nèi)存架構(gòu)上的共享內(nèi)存模型

機(jī)器內(nèi)存分布于網(wǎng)絡(luò)上的不同結(jié)點(diǎn)，但是對(duì)于用戶而言，看到的確實(shí)一個(gè)具有全局地址空間的共享內(nèi)存。這種方法通常被稱為“虛擬共享存儲(chǔ)器”。

在共享內(nèi)存架構(gòu)上的分布式內(nèi)存模型

最主要的是消息傳遞接口（MPI）。每個(gè)任務(wù)都可以直接訪問跨所有機(jī)器的全局地址空間。然而，它們之間數(shù)據(jù)交換卻是通過消息傳遞機(jī)制實(shí)現(xiàn)的，就像在分布式內(nèi)存網(wǎng)絡(luò)中所進(jìn)行的那樣。

那么到底使用哪一種呢？這往往取決于現(xiàn)有條件以及用戶的偏好。沒有最好的模型，但對(duì)模型的實(shí)現(xiàn)質(zhì)量卻可能存在差別。下面我們將分別描述上面提到的各種并行計(jì)算模型，并且討論它們?cè)趯?shí)踐中的一些實(shí)現(xiàn)方式。

5.2 共享內(nèi)存模型（無線程）

在這種并行計(jì)算模型中，處理器/任務(wù)共享內(nèi)存空間，并且可以異步地對(duì)內(nèi)存進(jìn)行讀寫。很多機(jī)制被用來控制對(duì)內(nèi)存的存取，例如鎖/信號(hào)量等，用來解決訪問沖突以及避免死鎖。這應(yīng)該是最簡(jiǎn)單的并行計(jì)算模型了。

從編程者的角度來看，這種模型的好處之一數(shù)據(jù)“擁有者”的缺失，所以他們不必明確地指定數(shù)據(jù)之間的通訊。所有的處理器都可以看到和平等地存取共享內(nèi)存。程序開發(fā)將因此而變得容易。

性能方面的一個(gè)重要缺點(diǎn)是對(duì)數(shù)據(jù)局部性的理解和管理講變得困難：1）保持?jǐn)?shù)據(jù)的局部性將有利于減少內(nèi)存的存取負(fù)擔(dān)，緩存刷新次數(shù)以及總線流量。而當(dāng)多個(gè)處理器使用同一數(shù)據(jù)時(shí)，這些負(fù)擔(dān)將會(huì)經(jīng)常發(fā)生；2）不幸的是，保持?jǐn)?shù)據(jù)的局部性往往比較難以理解，并且其難度超過一般用戶的水平。

實(shí)現(xiàn)： 單機(jī)共享內(nèi)存機(jī)器，本地操作系統(tǒng)，編譯器及其對(duì)應(yīng)的硬件都支持共享內(nèi)存編程。在分布式內(nèi)存機(jī)器上，內(nèi)存在物理上存在于網(wǎng)絡(luò)上不同的結(jié)點(diǎn)上，但是可以通過特殊的硬件和軟件，將其變?yōu)槿挚梢姟?/p>

5.3 線程模型

這是共享內(nèi)存編程的一種模式。在線程模型中，一個(gè)單個(gè)的“重量級(jí)”進(jìn)程可以擁有多個(gè)“輕量級(jí)”的并發(fā)執(zhí)行路徑。例如下圖所示：

• 主程序 a.out 在本地操作系統(tǒng)上運(yùn)行。a.out 需要加載所有的系統(tǒng)和用戶資源來運(yùn)行，這是里面的“重量級(jí)”進(jìn)程。a.out 首先執(zhí)行一些串行工作，然后生成一系列任務(wù)（線程），而這些線程可以在操作系統(tǒng)中被并發(fā)地執(zhí)行。
• 每個(gè)線程具有本地?cái)?shù)據(jù)，但同時(shí)也共享 a.out 的所有資源。這節(jié)約了所有線程都復(fù)制程序資源的的開銷。而每個(gè)線程同時(shí)也從全局內(nèi)存中獲益，因?yàn)樗梢怨蚕?a.out 的內(nèi)存空間。
• 一個(gè)線程的工作可以被描述為主程序的一個(gè)子程序。任何線程都可以在其它線程運(yùn)行的同時(shí)執(zhí)行任何子程序。
• 線程之間的通訊通過全局內(nèi)存來實(shí)現(xiàn)（對(duì)全局地址的更新）。這需要建立一種同步機(jī)制，以保證在同一時(shí)刻，不會(huì)有多個(gè)線程對(duì)同一塊地址空間進(jìn)行更新。
• 線程可以隨時(shí)生成和結(jié)束，但是 a.out 卻一直存在，以提供所需的共享資源，直到整個(gè)應(yīng)用程序結(jié)束。

實(shí)現(xiàn)： 從編程的角度來講，線程的實(shí)現(xiàn)通常包括如下兩個(gè)方面：

• 庫(kù)函數(shù)或者子程序，這些庫(kù)函數(shù)或者子程序可以在并行源代碼中被調(diào)用；
• 嵌入在并行或者串行源代碼中的一組編譯器指令集合。

程序員需要同時(shí)定義上面的兩個(gè)方面（盡管有時(shí)候編譯器可以提供幫助）。

線程并不是一個(gè)新概念。之前硬件供應(yīng)商就曾經(jīng)實(shí)現(xiàn)過他們自己的線程。由于這些線程的實(shí)現(xiàn)各不相同，所以使得程序員很難開發(fā)可移植的多線程應(yīng)用程序。

而標(biāo)準(zhǔn)化工作卻導(dǎo)致了兩種完全不同的線程實(shí)現(xiàn)方式：POSIX Threads 和 OpenMP。

POSIX Threads：

由IEEE POSIX 1003.1c standard (1995)定義，僅支持C語言，是Unix/Linux操作系統(tǒng)的一部分，是基于庫(kù)函數(shù)的，也通常被稱為“Pthreads”。是非常明確的并行機(jī)制，需要程序員注意大量的細(xì)節(jié)。更多信息可見：POSIX Threads tutorial。

OpenMP：

是一個(gè)工業(yè)標(biāo)準(zhǔn)，有一組主要計(jì)算機(jī)硬件和軟件提供商，組織和個(gè)人聯(lián)合發(fā)起和定義，是基于編譯器指令的，具有可移植性/跨平臺(tái)性，目前支持的包括Unix和Windows平臺(tái)，目前支持C/C++和Fortran語言。非常簡(jiǎn)單和醫(yī)用，提供了“增量并行”，可以從串行代碼開始。更多信息可見：OpenMP tutorial。

也有一些其它的常見線程實(shí)現(xiàn)，但是在這里沒有討論，包括：

Microsoft threads

Java, Python threads

CUDA threads for GPUs

5.4 分布式內(nèi)存/消息傳遞模型

這種模型具有如下特點(diǎn)：

• 在計(jì)算的過程中，每個(gè)任務(wù)都僅僅使用它們自身的本地內(nèi)存。多個(gè)任務(wù)既可以寄宿在同一個(gè)物理機(jī)器上，也可以跨越不同的物理機(jī)器。
• 任務(wù)之間的數(shù)據(jù)交換是通過發(fā)送和接收消息而實(shí)現(xiàn)的。
• 數(shù)據(jù)傳輸通常需要不同進(jìn)程之間的協(xié)同操作才能實(shí)現(xiàn)。例如，一個(gè)發(fā)送操作需要同時(shí)對(duì)應(yīng)一個(gè)接收操作。

實(shí)現(xiàn)： 從編程的角度來講，消息傳遞的實(shí)現(xiàn)通常包括子程序庫(kù)。對(duì)這些子程序的調(diào)用往往就嵌入在源代碼中。編程者負(fù)責(zé)并行機(jī)制的實(shí)現(xiàn)。

自從1980年代以來，出現(xiàn)了多種消息傳遞庫(kù)函數(shù)。這些實(shí)現(xiàn)各不相同，導(dǎo)致編程者很難開發(fā)出移植性好的應(yīng)用程序。自從1992年開始，MPI Forum形成，其主要目標(biāo)是建立消息傳遞的標(biāo)準(zhǔn)接口。消息傳遞接口（Message Passing Interface (MPI)）的第一部分在1994年發(fā)布，第二部分在1996年發(fā)布，第三部分在2012年發(fā)布。所有的MPI說明可以參見 MPI Documents

。MPI成為了事實(shí)上的消息傳遞的工業(yè)標(biāo)準(zhǔn)，取代了所有其它消息傳遞的實(shí)現(xiàn)。幾乎所有流行的并行計(jì)算平臺(tái)都存在MPI的實(shí)現(xiàn)，但并不是所有的實(shí)現(xiàn)都包含了MPI-1，MPI-2和MPI-3的所有內(nèi)容。關(guān)于MPI的更多信息可以參見 MPI tutorial。

5.5 數(shù)據(jù)并行模型

通常也被稱為“全局地址空間分區(qū)”（Partitioned Global Address Space (PGAS)）模型。具有如下特點(diǎn)：

• 地址空間被認(rèn)為是全局的。
• 大多數(shù)的并行工作聚焦于在數(shù)據(jù)集上的操作。數(shù)據(jù)集通常被組織成為常用的結(jié)構(gòu)，例如數(shù)組，數(shù)立方等。
• 一系列任務(wù)在同一塊數(shù)據(jù)結(jié)構(gòu)上操作，但是每個(gè)任務(wù)卻操作在該數(shù)據(jù)結(jié)構(gòu)的不同分區(qū)上。
• 每個(gè)任務(wù)在數(shù)據(jù)結(jié)構(gòu)的不同分區(qū)上執(zhí)行相同的操作，例如，“給每個(gè)數(shù)組元素加上4”。

在共享內(nèi)存的架構(gòu)下，所有的任務(wù)通過全局內(nèi)存方式來對(duì)數(shù)據(jù)進(jìn)行存?。辉诜植际絻?nèi)存架構(gòu)下，根據(jù)任務(wù)分配，全局?jǐn)?shù)據(jù)結(jié)構(gòu)在物理或者邏輯上被進(jìn)行分割。

實(shí)現(xiàn)： 目前，基于數(shù)據(jù)并行/PGAS模型，有如下幾個(gè)相對(duì)有名的實(shí)現(xiàn)：

Coarray Fortran: 為了支持SPMD并行編程而在Fortran 95上做的一個(gè)小的擴(kuò)展，是編譯器相關(guān)的，更多信息可以參見： Coarray_Fortran

Unified Parallel C (UPC): 為了支持SPMD并行編程而在C語言基礎(chǔ)上做的擴(kuò)展，也是編譯器相關(guān)的，更多信息可以參見： The UPC Language

5.6 混合模型

混合模型指的是包含了至少兩個(gè)我們前面提到的并行計(jì)算模型的模型。目前，最常見的混合模型的例子是消息傳遞模型（MPI）和線程模型（OpenMP）的結(jié)合：

• 線程使用本地?cái)?shù)據(jù)完成計(jì)算密集型的任務(wù)；
• 不同的進(jìn)程則在不同的結(jié)點(diǎn)上通過MPI完成數(shù)據(jù)通訊。

這種混合模型非常適合目前流行的硬件環(huán)境——多核計(jì)算機(jī)組成的集群系統(tǒng)。

另外一種類似的，但原來越流行的例子是采用MPI和CPU-GPU的混合編程：

• 采用MPI的任務(wù)運(yùn)行于CPU上，使用本地內(nèi)存上的數(shù)據(jù)，但是通過網(wǎng)絡(luò)與其它任務(wù)進(jìn)行數(shù)據(jù)交換；
• 而計(jì)算密集型的核則被加載到GPU上進(jìn)行計(jì)算；
• 而結(jié)點(diǎn)內(nèi)部的內(nèi)存和GPU上的數(shù)據(jù)交換則通過CUDA（或者類似的東西）進(jìn)行數(shù)據(jù)交換。

其它混合模型還包括：

• MPI和Pthreads的混合；
• MPI和non-GPU加速器的混合。
• …

5.7 單程序多數(shù)據(jù)模型(SPMD)和多程序多數(shù)據(jù)模型(MPMD)

單程序多數(shù)據(jù)模型(Single Program Multiple Data (SPMD))：

SPMD事實(shí)上是一種可以架構(gòu)在其它并行編程模型之上的更“高級(jí)”的編程模型：

• 單程序：所有任務(wù)都執(zhí)行同一個(gè)程序的拷貝，而這里的程序可以是線程，消息傳遞，數(shù)據(jù)并行甚至混合；
• 多數(shù)據(jù)：不同的任務(wù)操作于不同的數(shù)據(jù)。

SMPD通常需要指定任務(wù)的執(zhí)行邏輯，也就是不同的任務(wù)可能會(huì)根據(jù)分支和邏輯關(guān)系，去執(zhí)行整個(gè)程序的某個(gè)部分，也就是說，不是所有的任務(wù)都必須執(zhí)行整個(gè)程序——有可能只是整個(gè)程序的某個(gè)部分。（譯者注：如果不強(qiáng)調(diào)這一點(diǎn)，SPMD就退化成了數(shù)據(jù)并行模型了。）

而這種采用消息消息傳遞或者混合編程的SPMD模型，有可能是今天運(yùn)行在多核集群系統(tǒng)上的最常見的并行計(jì)算模型了。

多程序多數(shù)據(jù)模型(Multiple Program Multiple Data (MPMD))：

和SPMD一樣，多程序多數(shù)據(jù)模型實(shí)際上也是一種可以架構(gòu)在其它并行編程模型基礎(chǔ)上的“高級(jí)”并行編程模型：

• 多程序：任務(wù)可以同時(shí)執(zhí)行不同的程序，這里的程序可以是線程，消息傳遞，數(shù)據(jù)并行或者它們的混合。
• 多數(shù)據(jù)：所有的任務(wù)可以使用不同的數(shù)據(jù)。

MPMD應(yīng)用并不像SPMD應(yīng)用那么常見，但是它可能更適合于特定類型的程序。

6 并行程序設(shè)計(jì)

6.1 自動(dòng) vs. 手動(dòng)并行化

設(shè)計(jì)和實(shí)現(xiàn)并行程序是一個(gè)非常手動(dòng)的過程，程序員通常需要負(fù)責(zé)識(shí)別和實(shí)現(xiàn)并行化，而通常手動(dòng)開發(fā)并行程序是一個(gè)耗時(shí)，復(fù)雜，易于出錯(cuò)并且迭代的過程。很多年來，很多工具被開發(fā)出來，用以協(xié)助程序員將串行程序轉(zhuǎn)化為并行程序，而最常見的工具就是可以自動(dòng)并行化串行程序的并行編譯器(parallelizing compiler)或者預(yù)處理器 (pre-processor)。

并行編譯器通常以如下兩種方式工作：

完全自動(dòng)：

由編譯器分析源代碼并且識(shí)別可以并行化的部分，這里的分析包括識(shí)別出哪些部分滿足并行化的條件，以及權(quán)衡并行化是否真的可以提高性能。循環(huán)（包括do, for）通常是最容易被并行化的部分。

程序員指令：

通過采用“編譯器指令”或者編譯器標(biāo)識(shí)，程序員明確地告訴編譯器如何并行化代碼，而這可能會(huì)和某些自動(dòng)化的并行過程結(jié)合起來使用。

最常見的由編譯器生成的并行化程序是通過使用結(jié)點(diǎn)內(nèi)部的共享內(nèi)存和線程實(shí)現(xiàn)的（例如OpenMP）。

如果你已經(jīng)有了串行的程序，并且有時(shí)間和預(yù)算方面的限制，那么自動(dòng)并行化也許是一個(gè)好的選擇，但是有幾個(gè)重要的注意事項(xiàng)：1）可能會(huì)產(chǎn)生錯(cuò)誤的結(jié)果；2）性能實(shí)際上可能會(huì)降低；3）可能不如手動(dòng)并行那么靈活；4）只局限于代碼的某個(gè)子集（通常是循環(huán)）；5）可能實(shí)際上無法真正并行化，由于編譯器發(fā)現(xiàn)里面有依賴或者代碼過于復(fù)雜。

接下來的部分僅適用于手動(dòng)開發(fā)并行程序。

6.2 理解問題和程序

毫無疑問，開發(fā)并行程序的第一步就是理解你將要通過并行化來解決的問題。如果你是從一個(gè)已有的串行程序開始的，那么你需要首先理解這個(gè)串行程序。

在開始嘗試開發(fā)并行解決方案之前，需要確定該問題是否真正可以被并行化。

• 一個(gè)容易被并行化的問題如下。該問題容易被并行化，因?yàn)槊總€(gè)分子構(gòu)象都是獨(dú)立且確定的。計(jì)算最小能量構(gòu)象也是一個(gè)可以被并行化的問題。

計(jì)算數(shù)千個(gè)獨(dú)立分子構(gòu)象中每一個(gè)的勢(shì)能，完成之后，找出能量構(gòu)象最小的那一個(gè)。

• 一個(gè)不太可能被并行化的問題如下。由于F(n)同時(shí)依賴于F(n-1)和F(n-2)，而后者需要提前被計(jì)算出來。

采用如下公式計(jì)算菲波那切數(shù)列 （0,1,1,2,3,5,8,13,21,…）：F(n) = F(n-1) + F(n-2)。

識(shí)別程序的關(guān)鍵點(diǎn) (hotspots)：

了解哪個(gè)部分完成了程序的大多數(shù)工作。大多數(shù)的科學(xué)和技術(shù)程序中，大多數(shù)的工作都是在某些小片段中完成的?？梢酝ㄟ^剖析器或者性能分析工具來幫助你分析。專注于程序中這些關(guān)鍵點(diǎn)，忽略那些占用少量CPU的其余部分。

識(shí)別程序中的瓶頸 (bottlenecks)：

• 有沒有導(dǎo)致程序不成比例地變慢的，或者導(dǎo)致并行程序停止或者延遲的部分？例如有時(shí)候輸入輸出操作會(huì)導(dǎo)致程序變慢。
• 有時(shí)候也可能通過重構(gòu)程序，或者采用不同的算法來降低或者消除這些執(zhí)行很慢的區(qū)域。

識(shí)別并行化的抑制因素。一個(gè)常見的類型是數(shù)據(jù)依賴性 (data dependence)，例如上面提到的菲波那切數(shù)列的例子。

如果可能的話，研究其它算法。這可能是設(shè)計(jì)并行程序的過程中最重要的一點(diǎn)。

利用成熟的第三方并行軟件，或者高度成熟的數(shù)學(xué)庫(kù)（例如IBM的ESSL，Intel的MKL，AMD的AMCL等）。

6.3 分割 (Partitioning)

設(shè)計(jì)并行程序的第一步就是將程序分解成為可以分配到不同任務(wù)中去的“塊”。這被稱為程序的分解 (decomposition) 或者分割 (partitioning)。通常有兩種基本方法可以將并行任務(wù)進(jìn)行分解：域分解和功能分解。

域分解： 在這種分割方式中，將數(shù)根據(jù)問題進(jìn)行分解。每個(gè)并行任務(wù)操作數(shù)據(jù)的一部分。

通常由不同的方式來對(duì)數(shù)據(jù)進(jìn)行分割：

功能分解：

在這種方法中，重點(diǎn)在于要執(zhí)行的計(jì)算，而不是計(jì)算所操縱的數(shù)據(jù)。問題根據(jù)要做的工作進(jìn)行分解，然后每個(gè)任務(wù)執(zhí)行整個(gè)工作的一部分。

這種功能分解非常適合于可分為不同任務(wù)的問題，例如：

生態(tài)系統(tǒng)建模：

每個(gè)程序計(jì)算給定組的人口，其中每個(gè)組的正常取決于其鄰居的增長(zhǎng)。鎖著時(shí)間的推移，每個(gè)進(jìn)程計(jì)算當(dāng)前狀態(tài)，然后與相鄰群體交換信息。然后所有任務(wù)進(jìn)行下一步計(jì)算。

信號(hào)處理：

音頻信號(hào)數(shù)據(jù)集通過四個(gè)不同的計(jì)算濾波器，每個(gè)濾波器是一個(gè)單獨(dú)的過程。第一段數(shù)據(jù)必須通過第一個(gè)濾波器，然后才能進(jìn)入第二個(gè)濾波器。當(dāng)這樣做時(shí)，第二段數(shù)據(jù)通過了第一個(gè)濾波器。當(dāng)?shù)谒膫€(gè)數(shù)據(jù)段處于第一個(gè)濾波器時(shí)（以及之后），四個(gè)任務(wù)都會(huì)變得很忙。

氣候建模：

每個(gè)模型組件都可以被認(rèn)為是一個(gè)單獨(dú)的任務(wù)。箭頭表示計(jì)算期間組件之間的數(shù)據(jù)交換：大氣模型需要使用風(fēng)速數(shù)據(jù)生成海洋模型；海洋模型使用海面溫度數(shù)據(jù)生成大氣模型等。

在實(shí)踐中將這兩種分解方式結(jié)合起來是很自然的，也是很常見的。

6.4 通訊 (Communications)

任務(wù)之間的通訊需求取決于你的問題：

不需要通訊的情況：

一些程序可以被分解成為并發(fā)執(zhí)行的任務(wù)，而這些任務(wù)之間不需要共享數(shù)據(jù)。這類問題往往被稱為“尷尬并行”——任務(wù)之間不需要數(shù)據(jù)通訊。例如如果我們需要對(duì)下面一副圖片的顏色進(jìn)行取反（黑色的部分變?yōu)榘咨?，白色的變?yōu)楹谏模?，那么圖像數(shù)據(jù)可以被簡(jiǎn)單地分解為多個(gè)任務(wù)，并且每個(gè)任務(wù)可以被獨(dú)立地執(zhí)行。

需要通訊的情況：

大多數(shù)并行程序并不像上一問題這么簡(jiǎn)單，任務(wù)之間確實(shí)需要共享數(shù)據(jù)。例如下面這幅熱度擴(kuò)散圖需要一個(gè)任務(wù)知道其它任務(wù)在它的鄰居方格中的計(jì)算結(jié)果。鄰居數(shù)據(jù)的變化將直接影響到該任務(wù)的數(shù)據(jù)。

設(shè)計(jì)通訊需要考慮的因素： 在設(shè)計(jì)程序任務(wù)之間的通訊時(shí)，有大量的重要因素需要考慮：

通訊開銷：

1）任務(wù)間通訊幾乎總是意味著開銷。

2）而可以用于計(jì)算的機(jī)器周期以及資源會(huì)轉(zhuǎn)而用于對(duì)數(shù)據(jù)的封裝和傳輸。

3）頻繁的通訊也需要任務(wù)之間的同步，這有可能會(huì)導(dǎo)致任務(wù)花費(fèi)時(shí)間等待而不是執(zhí)行。

4）競(jìng)爭(zhēng)通訊流量可能使可用的網(wǎng)絡(luò)帶寬飽和，從而進(jìn)一步加劇性能問題。

延遲 vs. 帶寬：

1）延遲 指的是從A點(diǎn)到B點(diǎn)發(fā)送最小量的信息所需要花費(fèi)的時(shí)間，通常以毫秒計(jì)。

2）帶寬 指的是單位時(shí)間內(nèi)可以傳輸?shù)臄?shù)據(jù)總量，通常以M/S或者G/S來計(jì)。

3）發(fā)送大量的短消息可能會(huì)導(dǎo)致延遲成為通訊的主要開銷。通常情況下將大量小信息封裝成為大消息會(huì)更加有效，從而提高通訊帶寬的利用效率。

通訊可見性：

1）在消息傳遞模型中，通訊往往是顯式和可見的，并且在編程者的控制之下。

2）在數(shù)據(jù)并行模型中，通訊對(duì)編程者來說往往是透明的，尤其是在分布式內(nèi)存架構(gòu)中。編程者往往甚至不能明確知道任務(wù)之間的通訊是如何完成的。

同步 vs. 異步通訊：

1) 同步通訊需要共享數(shù)據(jù)的任務(wù)之間某種意義上的“握手”。這既可以由編程者顯式地指定，也可以在底層被隱式地實(shí)現(xiàn)而不為編程者所知。

2）同步通訊業(yè)常常被稱為“阻塞通訊”，因?yàn)橐恍┤蝿?wù)必須等待直到它們和其它任務(wù)之間的通訊完成。

3）異步通訊允許任務(wù)之間獨(dú)立地傳輸數(shù)據(jù)。例如任務(wù)1可以準(zhǔn)備并且發(fā)送消息給任務(wù)2然后立即開始做其它工作，它并不關(guān)心任務(wù)2什么時(shí)候真正受到數(shù)據(jù)。

4）異步通訊也常常被稱為“非阻塞通訊”，因?yàn)樵谕ㄓ嵃l(fā)生的過程中，任務(wù)還可以完成其它工作。

5）在計(jì)算和通訊自由轉(zhuǎn)換是異步通訊的最大優(yōu)勢(shì)所在。

通訊的范圍：

明確哪些任務(wù)之間需要通訊在設(shè)計(jì)并行代碼的過程中是非常關(guān)鍵的。下面兩種通訊范圍既可以被設(shè)計(jì)為同步的，也可以被設(shè)計(jì)為異步的：

1）點(diǎn)對(duì)點(diǎn)通訊： 涉及到兩個(gè)任務(wù)，其中一個(gè)扮演消息發(fā)送者/生產(chǎn)者的角色，另外一個(gè)扮演消息接受者/消費(fèi)者的角色。

2）廣播通訊： 涉及到多于兩個(gè)任務(wù)之間的數(shù)據(jù)共享。這些任務(wù)通常處于一個(gè)組或者集合中。

通訊的效率：

通常編程者具有影響通訊性能的選擇，這里列舉其中一些：1）對(duì)于一個(gè)給定的模型，究竟應(yīng)該采用哪一種實(shí)現(xiàn)？例如對(duì)于消息傳遞模型而言，一種MPI的實(shí)現(xiàn)可能在某個(gè)給定的硬件下比其它實(shí)現(xiàn)要快。2）什么采用什么類型的通訊操作？正如前面所提到的，異步通訊操作往往可以提高程序的整體性能。3）網(wǎng)絡(luò)結(jié)構(gòu)（network fabric）：某些平臺(tái)可能會(huì)提供多于一個(gè)的網(wǎng)絡(luò)結(jié)構(gòu)。那么究竟哪一個(gè)最好？

開銷和復(fù)雜性：

最后需要意識(shí)到，上面提到的僅僅是需要注意的問題的一部分！

6.5 同步 (Synchronization)

管理工作的順序和執(zhí)行它的任務(wù)是大多數(shù)并行程序設(shè)計(jì)的關(guān)鍵，它也可能是提升程序性能的關(guān)鍵，通常也需要對(duì)某些程序進(jìn)行“串行化”。

同步的類型：

屏障：

1）這通常意味著會(huì)涉及到所有任務(wù)；

2）每個(gè)任務(wù)都執(zhí)行自身的工作，直到它遇到屏障，然后它們就停止，或者“阻塞”；

3）當(dāng)最后一個(gè)任務(wù)到達(dá)屏障時(shí)，所有任務(wù)得以同步；

4）接下來可能發(fā)生的事情就有所變化了。通常會(huì)執(zhí)行一段串行代碼，或者所有的任務(wù)在這里都結(jié)束了。

鎖/信號(hào)量：

1）可以涉及任意多個(gè)任務(wù)；

2）通常用于對(duì)全局?jǐn)?shù)據(jù)或者某段代碼的存取串行化（保護(hù)），在任一時(shí)刻，只有一個(gè)任務(wù)可以使用鎖/信號(hào)量；

3）第一個(gè)任務(wù)會(huì)獲得一個(gè)鎖，然后該任務(wù)就可以安全地對(duì)該保護(hù)數(shù)據(jù)進(jìn)行存??；

4）其它任務(wù)可以嘗試去獲得鎖，但必須等到當(dāng)前擁有該鎖的任務(wù)釋放鎖才行；

5）可以是阻塞的也可以是非阻塞的。

同步通訊操作：

1）僅僅涉及到執(zhí)行數(shù)據(jù)通訊操作的任務(wù)；

2）當(dāng)一個(gè)任務(wù)執(zhí)行數(shù)據(jù)通訊操作時(shí)，通常需要在參與通訊的任務(wù)之間建立某種協(xié)調(diào)機(jī)制。例如，在一個(gè)任務(wù)發(fā)送消息時(shí)，它必須收到接受任務(wù)的確認(rèn)，以明確當(dāng)前是可以發(fā)送消息的；

3）在消息通訊一節(jié)中也已經(jīng)說明。

6.6 數(shù)據(jù)依賴性 (Data Dependencies)

定義：

• 依賴： 當(dāng)語句的執(zhí)行順序影響程序的運(yùn)行結(jié)果時(shí)，我們稱程序語句之間存在依賴關(guān)系。
• 數(shù)據(jù)依賴： 數(shù)據(jù)依賴是由不同任務(wù)多次存取相同的內(nèi)存位置而產(chǎn)生的。

數(shù)據(jù)依賴也是并行程序設(shè)計(jì)中的關(guān)鍵，因?yàn)樗遣⑿谢幸粋€(gè)重要的抑制因素。

例子：

循環(huán)相關(guān)的數(shù)據(jù)依賴：下面這段代碼中，A(J-1) 必須在A(J) 之前被計(jì)算出來，因此說A(J) 與 A(J-1) 之間存在數(shù)據(jù)依賴，所以并行化在這里被抑制。如果任務(wù)2中有A(J)，任務(wù)1中有A(J-1)，那么要計(jì)算出正確的A(J) 則需要：1）分布式內(nèi)存架構(gòu)：任務(wù)2必須在任務(wù)1計(jì)算結(jié)束之后，從任務(wù)1處中獲取A(J-1) 的值。2）共享內(nèi)存架構(gòu)：任務(wù)2在任務(wù)1完成對(duì)A(J-1) 的更新之后，對(duì)A(J-1) 進(jìn)行讀取。

DO J = MYSTART,MYEND
A(J) = A(J-1) * 2.0
END DO

循環(huán)無關(guān)的數(shù)據(jù)依賴：在下面的例子中并行化也同樣被抑制。Y的值依賴于：1）分布式內(nèi)存架構(gòu)： 在任務(wù)之間是否需要或者何時(shí)需要對(duì)X的值的通訊。2）共享內(nèi)存架構(gòu)： 哪個(gè)任務(wù)最后存儲(chǔ)X的值。

task 1 task 2
------ ------

X = 2 X = 4
. .
. .
Y = X**2 Y = X**3

盡管在并行程序設(shè)計(jì)中，對(duì)所有數(shù)據(jù)依賴的識(shí)別都是重要的，但循環(huán)相關(guān)的數(shù)據(jù)依賴尤其重要，因?yàn)檠h(huán)往往是最常見的可并行化部分。

處理方法：

1）分布式內(nèi)存架構(gòu)：在同步點(diǎn)傳輸所需數(shù)據(jù)；

2）共享式內(nèi)存結(jié)構(gòu)：在任務(wù)之間同步讀寫操作。

6.7 負(fù)載均衡 (Load Balancing)

負(fù)載均衡是指在任務(wù)之間分配大約相等數(shù)量的工作的做法，以便所有任務(wù)在所有時(shí)間保持繁忙，它也可以被認(rèn)為是使任務(wù)空閑時(shí)間最小化。出于性能原因方面的考慮，負(fù)載均衡對(duì)并行程序很重要。例如如果所有恩物都收到屏障同步點(diǎn)的影響，那么最慢的任務(wù)將決定整體性能。

如何實(shí)現(xiàn)負(fù)載均衡：

• 平均分配任務(wù)量：

對(duì)于數(shù)組/矩陣而言，如果每個(gè)任務(wù)都執(zhí)行相同或者類似的工作，那么在任務(wù)之間平均分配數(shù)據(jù)集；2）對(duì)于循環(huán)迭代而言，如果每個(gè)迭代完成的工作量大小類似，則在每個(gè)任務(wù)中分配相同或者類似的迭代次數(shù)；3）如果你的架構(gòu)是由具有不同性能特征的機(jī)器異構(gòu)組合而成，那么請(qǐng)確保使用某種性能分析工具來簡(jiǎn)則任何的負(fù)載不平衡，并相應(yīng)調(diào)整工作。

• 采用動(dòng)態(tài)任務(wù)分配方法：

即使數(shù)據(jù)在任務(wù)之間被平均分配，但是某些特定類型的問題也會(huì)導(dǎo)致負(fù)載不平衡，如下面三個(gè)例子所示。

稀疏矩陣：某些任務(wù)會(huì)具有真實(shí)數(shù)據(jù)，而大多數(shù)任務(wù)對(duì)應(yīng)的數(shù)據(jù)卻為0。

自適應(yīng)網(wǎng)格：某些方格需要被細(xì)分，而其它的不需要。

N體模擬：粒子可能會(huì)跨任務(wù)域遷移，因此某些任務(wù)會(huì)需要承擔(dān)更多的工作。

當(dāng)每個(gè)任務(wù)的工作量是可變的，或者無法預(yù)測(cè)的，那么可以采用 調(diào)度任務(wù)池 (Scheduler-task pool) 方法。每當(dāng)某個(gè)任務(wù)完成了它的工作，它就可以從工作隊(duì)列中領(lǐng)取新的任務(wù)。

最終來看，可能需要設(shè)計(jì)一種在代碼中動(dòng)態(tài)發(fā)生和處理負(fù)載不平衡的算法。

6.8 粒度 (Granularity)

計(jì)算通訊比 (computation / Communication Ratio)：

在并行計(jì)算中，粒度是對(duì)計(jì)算與通訊的比例的定性度量。計(jì)算周期通常通過同步時(shí)間與通訊周期分離。

細(xì)粒度并行化 (Fine-grain Parallelism)：

1）在通訊事件之外進(jìn)行相對(duì)較少的計(jì)算工作；

2）計(jì)算通訊率較低；

3）方便負(fù)載均衡；

4）意味著較高的通訊開銷以及較少的性能提升機(jī)會(huì)；

5）如果粒度過細(xì)，任務(wù)之間的通訊和同步的開銷可能需要比計(jì)算更長(zhǎng)的時(shí)間。

粗粒度并行化 (Coarse-grain Parallelism)：

1）在通訊/同步事件之外需要較大量的計(jì)算工作；

2）較高的計(jì)算/通訊比；

3）意味著較大的性能提升機(jī)會(huì)；

4）難以進(jìn)行較好的負(fù)載均衡。

最佳選擇：

最有效的粒度取決于具體算法及其所運(yùn)行的硬件環(huán)境。在大多數(shù)情況下，與通訊/同步相關(guān)的開銷相對(duì)于執(zhí)行速度很高，因此具有粗粒度的問題是相對(duì)有利的。而從另外一方面來講，細(xì)粒度則可以幫助減少由負(fù)載不均衡所造成的開銷。

6.9 輸入輸出 (I/O)

壞消息：

1）I/O操作通常被認(rèn)為是并行化的抑制劑；

2）I/O操作通常比內(nèi)存操作需要多個(gè)數(shù)量級(jí)的時(shí)間；

3）并行I/O系統(tǒng)可能不成熟或者不適用于所有平臺(tái)；

4）在所有任務(wù)均可以看到相同文件空間的環(huán)境中，寫操作可能導(dǎo)致文件被覆蓋；

5）讀操作可能受到文件服務(wù)器同時(shí)處理多個(gè)讀取請(qǐng)求的能力影響；

6）必須通過網(wǎng)絡(luò)進(jìn)行的I/O操作（NFS，非本地）可能導(dǎo)致嚴(yán)重的性能瓶頸，甚至導(dǎo)致文件服務(wù)器崩潰。

好消息：

已經(jīng)具有不少并行文件系統(tǒng)，例如：

GPFS：通用并行文件系統(tǒng) (General Parallel File System)（IBM），現(xiàn)在也被稱為IBM Spectrum Scale。

Lustre：針對(duì)Linux的集群（Intel）。

HDFS：Hadoop分布式文件系統(tǒng)（Apache）。

PanFS：Panasas ActiveScale File System for Linux clusters (Panasas, Inc.)更多并行文件系統(tǒng)可以參加這里。

作為MPI-2的一部分，1996年以來MPI的并行I/O編程借口規(guī)范已經(jīng)可用。

注意事項(xiàng)：

1）盡可能減少整體I/O操作；

2）如果你有權(quán)訪問并行文件系統(tǒng)，請(qǐng)使用它；

3）在大塊數(shù)據(jù)上執(zhí)行少量寫操作往往比在小塊數(shù)據(jù)上進(jìn)行大量寫操作有著更明顯的效率提升；

4）較少的文件比許多小文件更好；

5）將I/O操作限制在作業(yè)的特定串行部分，然后使用并行通訊將數(shù)據(jù)分發(fā)到并行任務(wù)中。例如任務(wù)1可以讀輸入文件，然后將所需數(shù)據(jù)傳送到其它任務(wù)。同樣，任務(wù)2可以再?gòu)乃衅渌蝿?wù)收到所需數(shù)據(jù)之后執(zhí)行寫入操作；

6）跨任務(wù)的I/O整合——相比于很多任務(wù)都執(zhí)行I/O操作，更好地策略是只讓一部分任務(wù)執(zhí)行I/O操作。

6.10 調(diào)試 (Debugging)

調(diào)試并行代碼可能非常困難，特別是隨著代碼量的擴(kuò)展。而好消息是有一些優(yōu)秀的調(diào)試器可以提供幫助：

1）Threaded - Pthreads和OpenMP；

2）MPI；

3）GPU/accelerator；

4）Hybrid。

在LC集群上也安裝有一些并行調(diào)試工具：

1）TotalView (RogueWave Software)；

2）DDT （Allinea）；

3）Inspector（Intel）；

4）Stack Trace Analysis Tool（STAT）（本地開發(fā)）。

更多的信息可以參考：LC web pages，TotalView tutorial。

6.11 性能分析和調(diào)優(yōu) (Performance Analysis and Tuning)

對(duì)于調(diào)試而言，并行程序的性能分析和調(diào)優(yōu)比串行程序更具挑戰(zhàn)性。幸運(yùn)的是，并行程序性能分析和調(diào)優(yōu)有很多優(yōu)秀的工具。Livemore計(jì)算機(jī)用戶可以訪問這種類似工具，其中大部分都在集群系統(tǒng)上。一些安裝在LC系統(tǒng)上的工具包括：

LC's web pages：https://hpc.llnl.gov/software/development-environment-software

TAU: http://www.cs.uoregon.edu/research/tau/docs.php

HPCToolkit: http://hpctoolkit.org/documentation.html

Open|Speedshop: http://www.openspeedshop.org/

Vampir / Vampirtrace: http://vampir.eu/

Valgrind: http://valgrind.org/

PAPI: http://icl.cs.utk.edu/papi/

mpitrace：https://computing.llnl.gov/tutorials/bgq/index.html#mpitrace

mpiP: http://mpip.sourceforge.net/

memP: http://memp.sourceforge.net/

7 并行示例

7.1 數(shù)組處理

此示例演示了對(duì)二維數(shù)組元素的操作：將某個(gè)函數(shù)作用于二維數(shù)組中的每個(gè)元素，其中對(duì)每個(gè)數(shù)組元素的操作都是獨(dú)立于其它數(shù)組元素的，并且該問題是計(jì)算密集型的。對(duì)于串行程序而言，我們依次對(duì)每個(gè)元素進(jìn)行操作，其代碼類似于：

do j = 1,n
do i = 1,n
a(i,j) = fcn(i,j)
end do
end do

問題：

• 該問題是否可以被并行化？
• 如果對(duì)該問題進(jìn)行分割？需要數(shù)據(jù)通訊嗎？
• 有沒有數(shù)據(jù)依賴？
• 有沒有同步需求？
• 是否需要考慮負(fù)載均衡？

并行方案1：

由于對(duì)元素的計(jì)算彼此之間是獨(dú)立的，所以可以有“尷尬并行”的解決方案。

由于數(shù)組元素是均勻分布的，所以每個(gè)進(jìn)程可以擁有陣列的一部分（子陣列）。

• 1）可以選擇最佳分配方案以實(shí)現(xiàn)高效的內(nèi)存訪問，例如選擇步幅為1，或者選擇合適的步幅以最大化緩存/內(nèi)存使用。
• 2）由于可以使單元跨越子陣列，所以分配方案的選擇也取決于編程語言，有關(guān)選項(xiàng)可以參見第 6.3 節(jié)。

由于數(shù)組元素的計(jì)算是彼此獨(dú)立的，所以不需要任務(wù)之間的通訊和同步。

由于任務(wù)之間的工作量是被平均分配的，所以不需要考慮負(fù)載均衡。

對(duì)數(shù)組分割之后，每個(gè)任務(wù)執(zhí)行與其擁有的數(shù)據(jù)相對(duì)應(yīng)的循環(huán)部分，其源代碼類似于：

請(qǐng)注意只有外部循環(huán)變量與串行解決方案不同。

for i (i = mystart; i < myend; i++) {
for j (j = 0; j < n; j++) {
a(i,j) = fcn(i,j);
}
}

一種可能的解決方案：

1）采用單程序多數(shù)據(jù) (SPMD) 模型進(jìn)行實(shí)現(xiàn)，每個(gè)任務(wù)執(zhí)行相同的程序；

2）主進(jìn)程對(duì)數(shù)組進(jìn)行初始化，將信息發(fā)送給子任務(wù)，并且接收計(jì)算結(jié)果；

3）子進(jìn)程接收到信息之后，執(zhí)行計(jì)算任務(wù)，并且將結(jié)果發(fā)送給主進(jìn)程；

4）采用Fortran的存儲(chǔ)結(jié)構(gòu)，對(duì)數(shù)組進(jìn)行塊劃分；

5）偽代碼如下所示。

6）具體的C代碼可以參見MPI Program in C：

find out if I am MASTER or WORKER
 
if I am MASTER 
  initialize the array
  send each WORKER info on part of array it owns
  send each WORKER its portion of initial array 
  receive from each WORKER results 
 
else if I am WORKER
  receive from MASTER info on part of array I own
  receive from MASTER my portion of initial array 
  # calculate my portion of array
  do j = my first column,my last column 
    do i = 1,n
      a(i,j) = fcn(i,j)
    end do
  end do 
  send MASTER results 
 
endif

并行方案2：

上一個(gè)并行方案展示了靜態(tài)負(fù)載均衡：1）每個(gè)任務(wù)執(zhí)行固定量的工作；2）某些很快或者負(fù)載較輕的處理器將會(huì)擁有空閑時(shí)間，而最慢執(zhí)行的任務(wù)最終決定整體性能。

如果所有任務(wù)在同一臺(tái)機(jī)器上運(yùn)行相同量的工作，那么靜態(tài)負(fù)載均衡往往并不是一個(gè)主要問題。但是如果你確實(shí)有負(fù)載均衡方面的問題（某些任務(wù)比其它任務(wù)運(yùn)行的快），那么你可以采用“任務(wù)池”(pool of tasks)模式。

任務(wù)池模式： 里面包含兩個(gè)進(jìn)程：

主進(jìn)程：

1）擁有任務(wù)池；2）如果得到請(qǐng)求，給工作進(jìn)程發(fā)送工作任務(wù)；3）從工作進(jìn)程出收集返回結(jié)果。

工作進(jìn)程：

1）從主進(jìn)程處獲取任務(wù)；2）執(zhí)行計(jì)算任務(wù)；3）向主進(jìn)程發(fā)送結(jié)果。

工作進(jìn)程在運(yùn)行之前不知道它將處理數(shù)組的哪一部分，以及它將執(zhí)行多少任務(wù)。動(dòng)態(tài)負(fù)載均衡發(fā)生在運(yùn)行時(shí)：運(yùn)行最快的任務(wù)將完成更多的任務(wù)。一段可能的源代碼如下：

find out if I am MASTER or WORKER
 
if I am MASTER
 
  do until no more jobs
    if request send to WORKER next job
    else receive results from WORKER
  end do
 
else if I am WORKER
 
  do until no more jobs
    request job from MASTER
    receive from MASTER next job
 
    calculate array element: a(i,j) = fcn(i,j)
 
    send results to MASTER
  end do
 
endif

討論：

1）在上述任務(wù)池例子中，每個(gè)任務(wù)計(jì)算數(shù)組的某一個(gè)元素，計(jì)算與通訊比率是細(xì)粒度的；

2）細(xì)粒度的解決方案為了減少任務(wù)空閑時(shí)間，往往會(huì)導(dǎo)致更多的通訊開銷；

3）更好地解決方案可能是在每個(gè)任務(wù)中分配更多的工作，“正確”的工作量依然是依賴于具體問題的。

7.2 圓周率計(jì)算

該問題的串行代碼大約是這樣的：

npoints = 10000
circle_count = 0
 
do j = 1,npoints
  generate 2 random numbers between 0 and 1
  xcoordinate = random1
  ycoordinate = random2
  if (xcoordinate, ycoordinate) inside circle
  then circle_count = circle_count + 1
end do
 
PI = 4.0*circle_count/npoints

該問題是計(jì)算密集型的——大多數(shù)時(shí)間將花費(fèi)在對(duì)循環(huán)的執(zhí)行。

問題：

• 該問題是否可以被并行化？
• 如何對(duì)該問題進(jìn)行分割？
• 任務(wù)之間是否需要通訊？
• 是否存在數(shù)據(jù)依賴？
• 任務(wù)之間是否有同步需求？需
• 要考慮負(fù)載均衡嗎？

解決方案：

又一個(gè)容易被并行化的問題：

1）每個(gè)點(diǎn)的計(jì)算都是獨(dú)立的，不存在數(shù)據(jù)依賴；

2）工作可以被平均分配，不需要考慮負(fù)載均衡；

3）任務(wù)之間不需要通訊和同步。

下面是并行化之后的偽代碼：

npoints = 10000
circle_count = 0
 
p = number of tasks
num = npoints/p
 
find out if I am MASTER or WORKER 
 
do j = 1,num 
  generate 2 random numbers between 0 and 1
  xcoordinate = random1
  ycoordinate = random2
  if (xcoordinate, ycoordinate) inside circle
  then circle_count = circle_count + 1
end do
 
if I am MASTER
 
  receive from WORKERS their circle_counts
  compute PI (use MASTER and WORKER calculations)
 
else if I am WORKER
 
  send to MASTER circle_count
 
endif

C語言的示例程序可以參考這里：MPI Program in C。

7.3 簡(jiǎn)單熱方程

大多數(shù)并行計(jì)算問題需要任務(wù)之間的通訊，其中一大部分問題需要“相鄰”任務(wù)之間的通訊。

二維熱方程問題描述了在給定初始溫度分布以及邊界條件的情況下，溫度隨著時(shí)間的變化。有限差分方案可以采用數(shù)值方法求解正方形區(qū)域內(nèi)的熱擴(kuò)散方程：

二維數(shù)組的元素用來表示正方形區(qū)域內(nèi)的點(diǎn)的溫度；

邊界處的初始問題是0，中心點(diǎn)的問題最高；

邊界處的問題會(huì)保持為0；

采用時(shí)間步長(zhǎng)算法。

每個(gè)元素的文圖的計(jì)算取決于它的鄰居的溫度：

串行程序的代碼可能使這個(gè)樣子：

do iy = 2, ny - 1
  do ix = 2, nx - 1
    u2(ix, iy) =  u1(ix, iy)  +
        cx * (u1(ix+1,iy) + u1(ix-1,iy) - 2.*u1(ix,iy)) +
        cy * (u1(ix,iy+1) + u1(ix,iy-1) - 2.*u1(ix,iy))
  end do
end do

問題：

該問題是否可以被并行化？

如何對(duì)該問題進(jìn)行分割？

任務(wù)之間是否需要通訊？

是否存在數(shù)據(jù)依賴？

任務(wù)之間是否需要同步？

是否需要考慮負(fù)載均衡？

解決方案：

該問題更具有挑戰(zhàn)性。因?yàn)榇嬖跀?shù)據(jù)依賴，所以需要任務(wù)之間的通訊和同步。整個(gè)數(shù)組需要被風(fēng)格成為子數(shù)組，并分配給不同任務(wù)，每個(gè)任務(wù)擁有整個(gè)數(shù)組的一部分。由于任務(wù)量是均勻劃分的，所以不需要考慮負(fù)載均衡。

確定數(shù)據(jù)依賴：

1）一個(gè)任務(wù)的 內(nèi)部元素 和其它任務(wù)之間不存在數(shù)據(jù)依賴；

2）一個(gè)任務(wù)的 邊界元素 則和它的鄰居任務(wù)之間需要產(chǎn)生數(shù)據(jù)通訊。

采用單程序多數(shù)據(jù)模型（SPMD）進(jìn)行實(shí)現(xiàn)：

1）主進(jìn)程向工作進(jìn)程發(fā)送初始信息，然后等待并收集來自工作進(jìn)程的計(jì)算結(jié)果；

2）工作進(jìn)程在特定的時(shí)間步長(zhǎng)內(nèi)計(jì)算結(jié)果，并與鄰居進(jìn)程之間進(jìn)行數(shù)據(jù)交換。

偽代碼如下：

find out if I am MASTER or WORKER
 
if I am MASTER
  initialize array
  send each WORKER starting info and subarray
  receive results from each WORKER 
else if I am WORKER
  receive from MASTER starting info and subarray
 
  # Perform time steps
  do t = 1, nsteps
    update time 
    send neighbors my border info
    receive from neighbors their border info 
    update my portion of solution array 
  end do
  send MASTER results
 
endif

示例程序可以參加：MPI Program in C。

7.4 一維波動(dòng)方程

在這個(gè)例子中，我們計(jì)算經(jīng)過指定時(shí)間量之后，一維波動(dòng)曲線的振幅。其中的計(jì)算會(huì)涉及到：

1）y軸上的振幅；

2）x軸上的位置索引i；

3）沿著波動(dòng)曲線的節(jié)點(diǎn)；

4）以離散時(shí)間步長(zhǎng)更新振幅。

這里需要求解的是如下一維波動(dòng)方程，其中c是常數(shù)。

A(i,t+1) = (2.0 * A(i,t)) - A(i,t-1) + (c * (A(i-1,t) - (2.0 * A(i,t)) + A(i+1,t)))

我們注意到，t時(shí)刻的振幅取決于前一刻的時(shí)間步長(zhǎng)(t, t-1)以及相鄰點(diǎn)(i - 1, i + 1)。

問題：

該問題是否可以被并行化？

如何對(duì)該問題進(jìn)行分割？

任務(wù)之間是否需要通訊？

人物之間是否存在數(shù)據(jù)依賴？

任務(wù)之間是否需要同步？

是否需要考慮負(fù)載均衡？

解決方案：

這是涉及到數(shù)據(jù)依賴的另外一個(gè)例子，其并行方案將會(huì)涉及到任務(wù)見的通訊和同步。整個(gè)振幅陣列被分割并分配給所有的子任務(wù)，每個(gè)任務(wù)擁有總陳列的相等的部分。由于所有點(diǎn)需要相等的工作，所以我們應(yīng)該均勻地分配節(jié)點(diǎn)。我們可以將工作分成多個(gè)塊，并且允許每個(gè)任務(wù)擁有大多數(shù)連續(xù)的數(shù)據(jù)點(diǎn)。而通訊只需要在數(shù)據(jù)邊界上進(jìn)行，塊大小越大，則所需的通信越少。

采用單程序多數(shù)據(jù)（SPMD）模型的實(shí)現(xiàn)：

1）主進(jìn)程向工作進(jìn)程發(fā)送初始信息，并且等到各個(gè)工作進(jìn)程返回計(jì)算結(jié)果；

2）工作進(jìn)程對(duì)特定步長(zhǎng)之內(nèi)的任務(wù)進(jìn)行計(jì)算，并且在必要的時(shí)候和鄰居進(jìn)程進(jìn)行數(shù)據(jù)通訊。

其偽代碼如下：

find out number of tasks and task identities
 
#Identify left and right neighbors
left_neighbor = mytaskid - 1
right_neighbor = mytaskid +1
if mytaskid = first then left_neigbor = last
if mytaskid = last then right_neighbor = first
 
find out if I am MASTER or WORKER
if I am MASTER
  initialize array
  send each WORKER starting info and subarray
else if I am WORKER`
  receive starting info and subarray from MASTER
endif
 
#Perform time steps 
#In this example the master participates in calculations
do t = 1, nsteps 
  send left endpoint to left neighbor
  receive left endpoint from right neighbor
  send right endpoint to right neighbor
  receive right endpoint from left neighbor
 
  #Update points along line
  do i = 1, npoints
    newval(i) = (2.0 * values(i)) - oldval(i) 
    + (sqtau * (values(i-1) - (2.0 * values(i)) + values(i+1))) 
  end do
 
end do
 
#Collect results and write to file
if I am MASTER
  receive results from each WORKER
  write results to file
else if I am WORKER
  send results to MASTER
endif 

程序示例可以參見：MPI Program in C。

8 參考文獻(xiàn)和更多信息

作者：Blaise Barney，Livermore Computing.

在萬維網(wǎng)上搜索“parallel programming”或者“parallel computing”將會(huì)獲得大量信息。

推薦閱讀：

”Designing and Building Parallel Programs”. Lan Foster.

http://www.mcs.anl.gov/~itf/dbpp/“

Introduction to Parallel Computing”. Ananth Grama, Anshul Gupta, George Karpis, Vpin Kumar.

http://www-users.cs.umn.edu/~karypis/parbook/“

Overview of Recent Supercomputers”. A.J. van der Steen, Jack Dongarra.

OverviewRecentSupercomputers.2008.pdf

圖片/圖像由作者以及其它LLNL成員創(chuàng)建，或者從不涉及版權(quán)的政府或公領(lǐng)域（）獲取，或者經(jīng)所有者同意從其演示文稿或者網(wǎng)頁(yè)上獲取。

歷史：該材料有下面的資源演化而來，而這些資源將不再被維護(hù)或者不再可用。

Tutorials located in the Maui High Performance Computing Center's “SP Parallel Programming Workshop”.

Tutorials located at the Cornell Theory Center's “Education and Training” web page.

以上就是并行計(jì)算概念及定義全面詳解的詳細(xì)內(nèi)容，更多關(guān)于并行計(jì)算的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論