（本人剛剛完成這篇長文章的翻譯，尚未認真校對。若里面有翻譯錯誤和打字錯誤敬請諒解，并請參考原貼）

1 摘要

帖子的原文： Introduction to Parallel Computing Tutorial

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

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

2 概述

2.1 什么是并行計算？

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

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

例如，

并行計算： 簡單來講，并行計算就是同時使用多個計算資源來解決一個計算問題：

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

每個部分可以進一步被分解成為一系列離散指令；

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

需要一個總體的控制/協(xié)作機制來負責對不同部分的執(zhí)行情況進行調度。

例如，

這里的 計算問題 需要具有如下特點：

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

這里的 計算資源 通常包括：

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

并行計算機：

通常來講，從硬件的角度來講，當前所有的單機都可以被認為是并行的：

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

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

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

例如，下面的圖解就顯示了一個典型的LLNL并行計算機集群：

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

2.2 為什么要并行計算？

真實世界就是高度并行的：

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

主要理由：

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

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

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

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

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

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

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

提供并發(fā)性：

1）單個計算資源某個時間段只能做一件事情，而多計算資源則可以同時做多件事情；

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

利用非局部的資源：

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

2）SETI@home的例子；

以及3）Folding@home的例子。

更好地利用并行硬件：

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

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

3）在大多數(shù)情況下，運行在現(xiàn)代計算機上的串行程序實際上浪費了大量的計算資源。

并行計算的未來：

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

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

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

2.3 誰都在使用并行計算？

科學界和工程界：

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

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

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

全球應用：

并行計算目前在實際上被廣泛采用于大量應用中

3 概念和術語

3.1 馮諾依曼體系結構

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

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

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

1）程序指令用來指導計算機操作；

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

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

那么馮諾依曼體系結構和并行計算有什么關系呢？答案是：并行計算機仍然遵從這一基本架構，只是處理單元多于一個而已，其它的基本架構完全保持不變。

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

有不同的方法對并行計算機進行分類（具體例子可參見并行計算分類）。

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

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

單指令單數(shù)據(jù)(SISD)： SISD是標準意義上的串行機，具有如下特點：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

值得注意的是，許多MIMD類型的架構中實際也可能包括SIMD的子架構。

3.3 一些常見的并行計算術語

和其它一些領域一樣，并行計算也有自己的“術語”。下面列出了與并行計算相關聯(lián)的一些常用術語，其中大部分術語我們在后面還會進行更詳細的討論。

• 結點(Node)：

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

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

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

• 任務(Task)：

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

• 流水線(Pipelining)：

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

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

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

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

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

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

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

• 通訊(communications)：

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

• 同步(Synchronization)：

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

• 粒度(Granularity)：

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

• 加速比(Observed Speedup)：

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

• 并行開銷(Parallel Overhead)：

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

1）任務啟動時間；

2）同步；

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

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

5）任務終止時間。

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

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

• 尷尬并行(Embarrassingly Parallel)：

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

• 可擴展性(Scalability)：

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

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

2）應用算法；

3）相對并行開銷；

4）具體應用的特征。

3.4 并行程序的缺陷和代價

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

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

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

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

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

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

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

復雜性：

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

1）設計；2）編碼；3）調試；4）調參；5）維護。

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

可移植性：

由于一些API的標準化，例如MPI，POSIX線程以及OpenMP，并行程序的可移植性問題并不像過去那么嚴重，然而：

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

資源需求：

并行編程的主要目標就是降低時鐘等待時間。然而要做到這一點，需要更多的CPU時間。例如，一個在8個處理器上跑了一個小時的并行程序實際上花費了8小時的CPU時間。

并行程序所需要的內(nèi)存開銷往往要大于相對應的串行程序，這是因為我們有時候需要復制數(shù)據(jù)，以滿足庫和子系統(tǒng)對并行算法的要求。

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

可擴展性：

基于時間和解決方案的不同，可以將擴展性分為強可擴展性和弱可擴展性：

強可擴展性的特點是：

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

2）目標是將同一問題運行的更快；

3）理想狀態(tài)下，相比于對應的串行程序，運行時間為1/P。

弱可擴展性的特點是：

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

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

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

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

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

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

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

4 并行計算機的內(nèi)存架構

4.1 共享內(nèi)存

一般特征：

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

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

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

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

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

優(yōu)點：

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

缺點：

最大的缺點是內(nèi)存和CPU之間缺少較好的可擴展性。增加更多的CPU意味著更加共享內(nèi)存和緩存想干系統(tǒng)上的存取流量，從而幾何級別地增加緩存/內(nèi)存管理的工作量。同時也增加了程序員的責任，因為他需要確保全局內(nèi)存“正確”的訪問以及同步。

4.2 分布式內(nèi)存

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

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

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

優(yōu)點：

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

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

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

缺點：

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

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

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

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

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

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

優(yōu)缺點：

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

2）優(yōu)點之一是可擴展性；

3）缺點之一是編程的復雜性。

5. 并行計算模型

5.1 概述

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

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

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

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

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

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

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

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

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

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

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

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

5.3 線程模型

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

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

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

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

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

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

而標準化工作卻導致了兩種完全不同的線程實現(xiàn)方式：POSIX Threads 和 OpenMP。

POSIX Threads：

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

OpenMP：

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

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

Microsoft threads

Java, Python threads

CUDA threads for GPUs

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

這種模型具有如下特點：

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

實現(xiàn)： 從編程的角度來講，消息傳遞的實現(xiàn)通常包括子程序庫。對這些子程序的調用往往就嵌入在源代碼中。編程者負責并行機制的實現(xiàn)。

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

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

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

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

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

在共享內(nèi)存的架構下，所有的任務通過全局內(nèi)存方式來對數(shù)據(jù)進行存取；在分布式內(nèi)存架構下，根據(jù)任務分配，全局數(shù)據(jù)結構在物理或者邏輯上被進行分割。

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

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

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

5.6 混合模型

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

• 線程使用本地數(shù)據(jù)完成計算密集型的任務；
• 不同的進程則在不同的結點上通過MPI完成數(shù)據(jù)通訊。

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

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

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

其它混合模型還包括：

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

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

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

SPMD事實上是一種可以架構在其它并行編程模型之上的更“高級”的編程模型：

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

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

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

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

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

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

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

6 并行程序設計

6.1 自動 vs. 手動并行化

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

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

完全自動：

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

程序員指令：

通過采用“編譯器指令”或者編譯器標識，程序員明確地告訴編譯器如何并行化代碼，而這可能會和某些自動化的并行過程結合起來使用。

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

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

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

6.2 理解問題和程序

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

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

• 一個容易被并行化的問題如下。該問題容易被并行化，因為每個分子構象都是獨立且確定的。計算最小能量構象也是一個可以被并行化的問題。

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

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

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

識別程序的關鍵點 (hotspots)：

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

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

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

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

如果可能的話，研究其它算法。這可能是設計并行程序的過程中最重要的一點。

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

6.3 分割 (Partitioning)

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

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

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

功能分解：

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

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

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

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

信號處理：

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

氣候建模：

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

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

6.4 通訊 (Communications)

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

不需要通訊的情況：

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

需要通訊的情況：

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

設計通訊需要考慮的因素： 在設計程序任務之間的通訊時，有大量的重要因素需要考慮：

通訊開銷：

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

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

3）頻繁的通訊也需要任務之間的同步，這有可能會導致任務花費時間等待而不是執(zhí)行。

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

延遲 vs. 帶寬：

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

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

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

通訊可見性：

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

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

同步 vs. 異步通訊：

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

2）同步通訊業(yè)常常被稱為“阻塞通訊”，因為一些任務必須等待直到它們和其它任務之間的通訊完成。

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

4）異步通訊也常常被稱為“非阻塞通訊”，因為在通訊發(fā)生的過程中，任務還可以完成其它工作。

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

通訊的范圍：

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

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

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

通訊的效率：

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

開銷和復雜性：

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

6.5 同步 (Synchronization)

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

同步的類型：

屏障：

1）這通常意味著會涉及到所有任務；

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

3）當最后一個任務到達屏障時，所有任務得以同步；

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

鎖/信號量：

1）可以涉及任意多個任務；

2）通常用于對全局數(shù)據(jù)或者某段代碼的存取串行化（保護），在任一時刻，只有一個任務可以使用鎖/信號量；

3）第一個任務會獲得一個鎖，然后該任務就可以安全地對該保護數(shù)據(jù)進行存?。?/p>

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

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

同步通訊操作：

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

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

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

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

定義：

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

數(shù)據(jù)依賴也是并行程序設計中的關鍵，因為它是并行化中一個重要的抑制因素。

例子：

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

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

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

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

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

盡管在并行程序設計中，對所有數(shù)據(jù)依賴的識別都是重要的，但循環(huán)相關的數(shù)據(jù)依賴尤其重要，因為循環(huán)往往是最常見的可并行化部分。

處理方法：

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

2）共享式內(nèi)存結構：在任務之間同步讀寫操作。

6.7 負載均衡 (Load Balancing)

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

如何實現(xiàn)負載均衡：

• 平均分配任務量：

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

• 采用動態(tài)任務分配方法：

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

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

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

N體模擬：粒子可能會跨任務域遷移，因此某些任務會需要承擔更多的工作。

當每個任務的工作量是可變的，或者無法預測的，那么可以采用 調度任務池 (Scheduler-task pool) 方法。每當某個任務完成了它的工作，它就可以從工作隊列中領取新的任務。

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

6.8 粒度 (Granularity)

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

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

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

1）在通訊事件之外進行相對較少的計算工作；

2）計算通訊率較低；

3）方便負載均衡；

4）意味著較高的通訊開銷以及較少的性能提升機會；

5）如果粒度過細，任務之間的通訊和同步的開銷可能需要比計算更長的時間。

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

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

2）較高的計算/通訊比；

3）意味著較大的性能提升機會；

4）難以進行較好的負載均衡。

最佳選擇：

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

6.9 輸入輸出 (I/O)

壞消息：

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

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

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

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

5）讀操作可能受到文件服務器同時處理多個讀取請求的能力影響；

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

好消息：

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

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

Lustre：針對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)可用。

注意事項：

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

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

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

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

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

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

6.10 調試 (Debugging)

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

1）Threaded - Pthreads和OpenMP；

2）MPI；

3）GPU/accelerator；

4）Hybrid。

在LC集群上也安裝有一些并行調試工具：

1）TotalView (RogueWave Software)；

2）DDT （Allinea）；

3）Inspector（Intel）；

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

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

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

對于調試而言，并行程序的性能分析和調優(yōu)比串行程序更具挑戰(zhàn)性。幸運的是，并行程序性能分析和調優(yōu)有很多優(yōu)秀的工具。Livemore計算機用戶可以訪問這種類似工具，其中大部分都在集群系統(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ù)組處理

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

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

問題：

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

并行方案1：

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

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

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

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

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

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

請注意只有外部循環(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) 模型進行實現(xiàn)，每個任務執(zhí)行相同的程序；

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

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

4）采用Fortran的存儲結構，對數(shù)組進行塊劃分；

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：

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

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

任務池模式： 里面包含兩個進程：

主進程：

1）擁有任務池；2）如果得到請求，給工作進程發(fā)送工作任務；3）從工作進程出收集返回結果。

工作進程：

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

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

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）在上述任務池例子中，每個任務計算數(shù)組的某一個元素，計算與通訊比率是細粒度的；

2）細粒度的解決方案為了減少任務空閑時間，往往會導致更多的通訊開銷；

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

7.2 圓周率計算

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

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

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

問題：

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

解決方案：

又一個容易被并行化的問題：

1）每個點的計算都是獨立的，不存在數(shù)據(jù)依賴；

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

3）任務之間不需要通訊和同步。

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

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 簡單熱方程

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

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

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

邊界處的初始問題是0，中心點的問題最高；

邊界處的問題會保持為0；

采用時間步長算法。

每個元素的文圖的計算取決于它的鄰居的溫度：

串行程序的代碼可能使這個樣子：

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

問題：

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

如何對該問題進行分割？

任務之間是否需要通訊？

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

任務之間是否需要同步？

是否需要考慮負載均衡？

解決方案：

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

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

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

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

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

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

2）工作進程在特定的時間步長內(nèi)計算結果，并與鄰居進程之間進行數(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 一維波動方程

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

1）y軸上的振幅；

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

3）沿著波動曲線的節(jié)點；

4）以離散時間步長更新振幅。

這里需要求解的是如下一維波動方程，其中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時刻的振幅取決于前一刻的時間步長(t, t-1)以及相鄰點(i - 1, i + 1)。

問題：

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

如何對該問題進行分割？

任務之間是否需要通訊？

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

任務之間是否需要同步？

是否需要考慮負載均衡？

解決方案：

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

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

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

2）工作進程對特定步長之內(nèi)的任務進行計算，并且在必要的時候和鄰居進程進行數(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 參考文獻和更多信息

作者：Blaise Barney，Livermore Computing.

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

推薦閱讀：

”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)建，或者從不涉及版權的政府或公領域（）獲取，或者經(jīng)所有者同意從其演示文稿或者網(wǎng)頁上獲取。

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

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.

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