[譯][并行計算] 1. 并行計算簡介

原文位址：https://blog.csdn.net/magicbean2/article/details/75174859

并行計算簡介

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

1 摘要

最近項目需要實作程式的并行化，剛好借着翻譯這篇文章的機會，了解和熟悉并行計算的基本概念和程式設計。文章的原文見這裡。

這篇文章旨在為并行計算這一廣泛而宏大的話題提供一個非常快速的概述，作為随後教程的先導。是以，它隻涵蓋了并行計算的基礎知識，實用于剛剛開始熟悉該主題的初學者。我們并不會深入讨論并行計算，因為這将花費大量的時間。本教程從對并行計算是什麼以及如何使用開始，讨論與其相關的概念和術語，然後解析并行記憶體架構(parallel memory architecture)以及程式設計模型(programming models)等。這些主題之後是一系列關于設計和運作并行計算程式的複雜問題的實踐讨論。最後，本教程給出了幾個并行化簡單串行程式的示例。

2 概述

2.1 什麼是并行計算？

串行計算：傳統的軟體通常被設計成為串行計算模式，具有如下特點：

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

例如，

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

一個問題被分解成為一系列可以并發執行的離散部分；
每個部分可以進一步被分解成為一系列離散指令；
來自每個部分的指令可以在不同的處理器上被同時執行；
需要一個總體的控制/協作機制來負責對不同部分的執行情況進行排程。

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

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

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

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

并行計算機：

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

多功能單元（L1緩存，L2緩存，分支，預取，解碼，浮點數，圖形處理器，整數等）
多執行單元/核心
多硬體線程

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

通過網絡連接配接起來的多個單機也可以形成更大的并行計算機叢集:

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

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

2.2 為什麼要并行計算？

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

自然界中的萬事萬物都在并發的，按照其内在時間序列運作着；
和串行計算相比，并行計算更适用于對現實世界中的複雜現象進行模組化，模拟和了解；
例如，可以想象對這些進行順序模組化：

主要理由：

節約時間和成本：1）理論上來講，在一個任務上投入更多的資源有利于縮短其完成時間，進而降低成本；2）并行計算機可以由大量廉價的單機構成，進而節約成本。
解決更大規模更複雜的問題：1）很多問題的規模和複雜度使得其難以在一個單機上面完成；2）一個有趣的例子：(Grand Challenge Problems)。3）網頁搜尋引擎/資料庫每秒處理百萬級别的吞吐量。
提供并發性：1）單個計算資源某個時間段隻能做一件事情，而多計算資源則可以同時做多件事情；2）協同網絡可以使得來自世界不同地區的人同時虛拟地溝通。
利用非局部的資源：1）可以利用更廣範圍中的網絡資源；2）SETI@home的例子；以及3）Folding@home的例子。
更好地利用并行硬體：1）現代計算機甚至筆記本電腦在架構上都屬于多處理器/多核的；2）并行軟體已經适用于多核的并行硬體條件，例如線程等；3）在大多數情況下，運作在現代計算機上的串行程式實際上浪費了大量的計算資源。

并行計算的未來：

在過去的二十多年中，快速發展的網絡，分布式系統以及多處理器計算機架構（甚至在桌面機級别上）表明并行化才是計算的未來；
在同一時期，超級計算機的性能已經有了至少50萬倍的增加，而且目前還沒有達到極限的迹象；
目前的峰值計算速度已經達到了10181018/秒。

2.3 誰都在使用并行計算？

科學界和工程界：

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

工業界和商業界：

如今，商業應用為更快速計算機的研發提供了更強勁的動力。這些商業應用程式需要以更複雜的方式處理大量資料，例如：大資料、資料庫、資料挖掘、石油勘探、網頁搜尋引擎、基于web的商業服務、醫學成像和診斷、跨國公司管理、進階圖形學技術以及虛拟現實、網絡視訊和多媒體技術、協同工作環境等。

全球應用：

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

3 概念和術語

3.1 馮諾依曼體系結構

以匈牙利數學家約翰·馮諾依曼命名的這一計算機體系結構，出現在他1945年發表的一篇論文中。這也通常被稱為“存儲程式計算機”——程式指令和資料都被儲存在存儲器中，這與早期通過“硬接線”程式設計的計算機不同。從此以後，所有的計算機走遵從這一基本架構：

- 四個組成部分：1）記憶體；2）控制器；3）處理器；4）輸入輸出。

- 讀寫操作：支援随機存儲的記憶體用來同時儲存程式指令和資料：1）程式指令用來指導計算機操作；2）資料是程式用來操作的對象。

- 控制器：從記憶體中讀取指令或者資料，對這些指令進行解碼并且順序執行這些指令。

- 處理器：提供基本的算術和邏輯操作。

- 輸入輸出裝置：是人機互動的接口。

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

3.2 弗林的經典分類

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

一種被廣泛采用的分類被稱為弗林經典分類，誕生于1966年。弗林分類法從指令流和資料流兩個次元區分多處理器計算機體系結構。每個次元有且僅有兩個狀态：單個或者多個。

下面個矩陣定義了弗林分類的四個可能狀态：

單指令單資料(SISD)： SISD是标準意義上的串行機，具有如下特點：1）單指令：在每一個時鐘周期内，CPU隻能執行一個指令流；2）單資料：在每一個時鐘周期内，輸入裝置隻能輸入一個資料流；3）執行結果是确定的。這是最古老的一種計算機類型。

單指令多資料(SIMD)： SIMD屬于一種類型的并行計算機，具有如下特點：1）單指令：所有處理單元在任何一個時鐘周期内都執行同一條指令；2）多資料：每個處理單元可以處理不同的資料元素；3）非常适合于處理高度有序的任務，例如圖形/圖像處理；4）同步（鎖步）及确定性執行；5）兩個主要類型：處理器陣列和矢量管道。

**多指令單資料(MISD)：**MISD屬于一種類型的并行計算機，具有如下特點：1）多指令：不同的處理單元可以獨立地執行不同的指令流；2）單資料：不同的處理單元接收的是同一單資料流。這種架構理論上是有的，但是工業實踐中這種機型非常少。

多指令多資料(MIMD)： MIMD屬于最常見的一種類型的并行計算機，具有如下特點：1）多指令：不同的處理器可以在同一時刻處理不同的指令流；2）多資料：不同的處理器可以在同一時刻處理不同的資料；3）執行可以是同步的，也可以是異步的，可以是确定性的，也可以是不确定性的。這是目前主流的計算機架構類型，目前的超級計算機、并行計算機叢集系統，網格，多處理器計算機，多核計算機等都屬于這種類型。值得注意的是，許多MIMD類型的架構中實際也可能包括SIMD的子架構。

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

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

結點(Node)：也就是一個獨立的“計算機單元”。通常由多個CPU處理器/處理核心，記憶體，網絡接口等組成。結點聯網在一起以構成超級計算機。
中央處理器/套接字/處理器/核(CPU / Socket / Processor / Core)：這些術語也取決于我們讨論的語境。在過去，中央處理器通常是計算機中的一個單個執行單元。之後多處理器被植入到一個結點中。接着處理器又被設計成為多核，每個核成為一個獨立的處理單元。具有多核的中央處理器有時候又被稱為“套接字”——實際上也沒有統一标準。是以目前來講，我們稱一個結點上具有多個中央處理器，每個中央處理器上又具有多個核心。
任務(Task)：任務通常是指一個邏輯上離散的計算工作部分。一個任務通常是一段程式或者一段類似于程式的指令集合，可以由一個處理器進行處理。一個并行程式通常由多個任務構成，并且可以運作在多個處理器上。
流水線(Pipelining)：可以将任務分解成為不同的步驟，并且由不同的處理單元完成，裡面有輸入流通過。這非常類似于一個裝配線，屬于一種類型的并行計算。
共享記憶體(Shared Memory)：從嚴格的硬體角度來講，共享記憶體描述了一種計算機架構，其中所有的處理器都可以對共同的實體記憶體進行直接存取（通常是通過總線）。從程式設計的角度來講，共享記憶體描述了一種模型，其中所有的并行任務都具有同一記憶體形态，并且都可以直接對同一記憶體區域進行直接定位和存取，而無論該實體記憶體實際上在哪裡（也許在千裡之外的另外一個計算機上？）。
對稱多處理器(Symmetric Multi-Processor (SMP))：屬于一種共享記憶體的硬體架構，并且不同的處理器對記憶體以及其它資源都具有同等的通路權限（個人了解，就是不同處理器在角色上沒有任何差別）。
分布式記憶體(Distributed Memory)：在硬體中，表示基于網絡的記憶體存取方式；在程式設計模型中，表示任務僅僅能夠從邏輯上“看到”本機上的記憶體，但是在其它任務執行的時候，必須通過通訊才能對其它任務所運作的機器上的記憶體進行存取。
通訊(communications)：并行任務通常需要資料交換。實作資料交換的方式有多種，例如通過共享記憶體或者通過網絡。但是通常意義上，資料交換指的就是通訊，而無論其實作方式。
同步(Synchronization)：指的是并行任務之間的實時協調，通常伴随着通訊(communication)。同步通常由在程式中設立同步點來實作，也就是說，在其它任務沒有執行到這一同步點的時候，某一任務不能進一步執行後面的指令。同步通常涉及到需要等待其它任務的完成，是以有時候會增加并行程式的執行時間。
粒度(Granularity)：在并行計算中，粒度定量地描述了計算與通訊的比率。粗粒度表示在通訊過程中需要做大量的計算性工作；細粒度則表示在通訊過程中需要做的計算性工作并不多。
加速比(Observed Speedup)：這是檢測并行計算性能的最簡單并且最被廣泛使用的度量政策，其定義如下：串行計算的時鐘周期數并行計算的時鐘周期數串行計算的時鐘周期數并行計算的時鐘周期數。
并行開銷(Parallel Overhead)：指的是相對于做實際計算，做協調并行任務所需要花費的時間總數。影響并行開銷的因素主要包括：1）任務啟動時間；2）同步；3）資料通訊；4）由并行語言，連結庫，作業系統等因素而導緻的軟體開銷；5）任務終止時間。
大規模并行(Massive Parallel)：指那些包含并行系統的硬體——擁有很多的處理元件。這裡的“很多”可能會随着硬體條件的進步而不斷增加，但目前，最大的并行系統所擁有的處理元件高達上百萬件。
尴尬并行(Embarrassingly Parallel)：指的是同時解決很多類似而又獨立的任務，其中任務之間幾乎沒有需要協調的地方。
可擴充性(Scalability)：指的是并行系統（包括軟體和硬體）通過添加更多資源來成比例增加并行速度的能力。影響可擴充性的因素主要包括：1）硬體，尤其是記憶體-處理器帶寬以及網絡通訊的品質和速度；2）應用算法；3）相對并行開銷；4）具體應用的特征。

3.4 并行程式的缺陷和代價

阿姆達爾定律：阿姆達爾定律說一個程式的加速比潛力由其可以并行的部分所占的比例而決定，即：

speedup=11−Pspeedup=11−P.

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

如果引入并行程式中的處理器個數，則加速比可以被重新定義為：

speedup=1PN+S=11−P+PNspeedup=1PN+S=11−P+PN，

其中P仍然是并行代碼所占的比例，N是處理器個數，S是串行代碼所占比例（S = 1 - P）。

N	P = 0.50	p = 0.90	p = 0.95	p = 0.99
10	1.82	5.26	6.89	9.17
100	1.98		16.80	50.25
1000	1.99	9.91	19.62	90.99
10000			19.96	99。02
100000		9.99	19.99	99.90

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

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

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

類型	時間	比例
2D網格計算	85秒	85%
串行比例	15秒	15%

我們可以增加網格的次元，并且将時間步長減半。其結果是四倍的網格點數量，以及兩倍的時間步長。之後的花費時間将變為：


	680秒	97.84%
		2.16%

比起具有固定并行時間百分比的問題，那些可以随着問題規模增大而不斷提高并行時間百分比的問題在并行化的意義上更具有可擴充性（複習一下可擴充性的定義^_^）。

複雜性：通常而言，并行計算的程式要比相應的串行計算程式更加複雜，也許複雜一個量級。你不僅需要同時執行不同的指令流，而且需要注意他們之間資料的通信。複雜性通常由涉及軟體開發周期各個方面的時間來确定，主要包括：1）設計；2）編碼；3）調試；4）調參；5）維護。

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

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

所有串行程式中所遇到的可移植性問題都會出現在相應的并行程式中。
盡管一些API已經被标準話，但是在一些細節的實作上任然有差異，有時候這些細節實作會影響到可移植性。
作業系統也會是導緻可移植性的關鍵因素。
硬體架構的不同有時候也會影響到可移植性。

資源需求：

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

并行程式所需要的記憶體開銷往往要大于相對應的串行程式，這是因為我們有時候需要複制資料，以滿足庫和子系統對并行算法的要求。

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

可擴充性：

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

強可擴充性的特點是：1）在更多處理器被加入的時候，問題本身的規模不會增加；2）目标是将同一問題運作的更快；3）理想狀态下，相比于對應的串行程式，運作時間為1/P。

弱可擴充性的特點是：1）随着更多處理器被加入，每個處理上需要處理的問題規模保持一緻；2）目标是在相同的時間内解決更多規模的問題；3）理想狀态下，在相同時間内，可以解決的問題規模增加為原問題規模的P倍。

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

此外，某些問題可能本身存在擴充性的極限，是以添加更多的資源有時候反而會降低性能。這種情形會出現在很多并行程式中。

硬體在可擴充性方面也扮演者重要角色，例如：1）記憶體-CPU之間的帶寬；2）通訊網絡的帶寬；3）某個機器或者某個機器集合中的記憶體大小；4）時鐘處理速度。

支援并行的庫或者子系統同樣也會限制并行程式的可擴充性。

4 并行計算機的記憶體架構

4.1 共享記憶體

一般特征：共享記憶體的并行計算機雖然也分很多種，但是通常而言，它們都可以讓所有處理器以全局尋址的方式通路所有的記憶體空間。多個處理器可以獨立地操作，但是它們共享同一片記憶體。一個處理器對記憶體位址的改變對其它處理器來說是可見的。根據記憶體通路時間，可以将已有的共享記憶體機器分為統一記憶體存取和非統一記憶體存取兩種類型。

統一記憶體存取(Uniform Memory Access)：目前更多地被稱為對稱多處理器機器(Symmetric Multiprocessor (SMP))，每個處理器都是相同的，并且其對記憶體的存取和存取之間都是無差别的。有時候也會被稱為CC-UMA (Cache coherent - UMA)。緩存想幹意味着如果一個處理器更新共享記憶體中的位置，則所有其它處理器都會了解該更新。緩存一緻性是在硬體級别上實作的。

非統一記憶體存取(Non-Uniform Memory Access)：通常由兩個或者多個實體上相連的SMP。一個SMP可以存取其它SMP上的記憶體。不是所有處理器對所有記憶體都具有相同的存取或者存取時間。通過連接配接而進行記憶體存取速度會更慢一些。如果緩存相緩存想幹的特性在這裡仍然被保持，那麼也可以被稱為CC-NUMA。

優點：全局位址空間提供了一種使用者友好的程式設計方式，并且由于記憶體與CPU的階級程度，使得任務之間的資料共享既快速又統一。

缺點：最大的缺點是記憶體和CPU之間缺少較好的可擴充性。增加更多的CPU意味着更加共享記憶體和緩存想幹系統上的存取流量，進而幾何級别地增加緩存/記憶體管理的工作量。同時也增加了程式員的責任，因為他需要確定全局記憶體“正确”的通路以及同步。

4.2 分布式記憶體

一般概念：分布式記憶體架構也可以分為很多種，但是它們仍然有一些共同特征。分布式記憶體結構需要通訊網絡，将不同的記憶體連接配接起來。一般而言，處理器會有它們所對應的記憶體。一個處理器所對應的記憶體位址不會映射到其它處理器上，是以在這種分布式記憶體架構中，不存在各個處理器所共享的全局記憶體位址。

由于每個處理器具有它所對應的局部記憶體，是以它們可以獨立進行操作。一個本地記憶體上所發生的變化并不會被其它處理器所知曉。是以，緩存想幹的概念在分布式記憶體架構中并不存在。

如果一個處理器需要對其它處理器上的資料進行存取，那麼往往程式員需要明确地定義資料通訊的時間和方式，任務之間的同步是以就成為程式員的職責。盡管分布式記憶體架構中用于資料傳輸的網絡結構可以像以太網一樣簡單，但在實踐中它們的變化往往也很大。

優點： 1）記憶體可以随着處理器的數量而擴充，增加處理器的數量的同時，記憶體的大小也在成比例地增加；2）每個處理器可以快速地通路自己的記憶體而不會受到幹擾，并且沒有維護全局告訴緩存一緻性所帶來的開銷；3）成本效益：可以使用現有的處理器和網絡。

缺點： 1）程式員需要負責處理器之間資料通訊相關的許多細節；2）将基于全局記憶體的現有資料結構映射到該分布式記憶體組織可能會存在困難；3）非均勻的記憶體通路時間——駐留在遠端結點上的資料比本地結點上的資料需要長的多的通路時間。

4.3 混合分布式-共享記憶體

一般概念：目前世界上最大和最快的并行計算機往往同時具有分布式和共享式的記憶體架構。共享式記憶體架構可以是共線記憶體機器或者圖形處理單元(GPU)。分布式記憶體元件可以是由多個共享記憶體/GPU連接配接而成的系統。每個結點隻知道自己的記憶體，不知道網絡上其它結點的記憶體。是以，需要在不同的機器上通過網絡進行資料通訊。

從目前的趨勢來看，這種混合式的記憶體架構将長期占有主導地位，并且成為高端計算在可見的未來中的最好選擇。

優缺點： 1）繼承了共享式記憶體和分布式記憶體的優缺點；2）優點之一是可擴充性；3）缺點之一是程式設計的複雜性。

5. 并行計算模型

5.1 概述

常見的并行程式設計模型包括：共享記憶體模型（無線程），線程模型，分布式記憶體/消息傳遞模型，資料并行模型，混合模型，單程式多資料模型，多程式多資料模型。

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

在分布式記憶體架構上的共享記憶體模型。機器記憶體分布于網絡上的不同結點，但是對于使用者而言，看到的确實一個具有全局位址空間的共享記憶體。這種方法通常被稱為“虛拟共享存儲器”。

在共享記憶體架構上的分布式記憶體模型。最主要的是消息傳遞接口（MPI）。每個任務都可以直接通路跨所有機器的全局位址空間。然而，它們之間資料交換卻是通過消息傳遞機制實作的，就像在分布式記憶體網絡中所進行的那樣。

那麼到底使用哪一種呢？這往往取決于現有條件以及使用者的偏好。沒有最好的模型，但對模型的實作品質卻可能存在差别。下面我們将分别描述上面提到的各種并行計算模型，并且讨論它們在實踐中的一些實作方式。

5.2 共享記憶體模型（無線程）

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

從程式設計者的角度來看，這種模型的好處之一資料“擁有者”的缺失，是以他們不必明确地指定資料之間的通訊。所有的處理器都可以看到和平等地存取共享記憶體。程式開發将是以而變得容易。

性能方面的一個重要缺點是對資料局部性的了解和管理講變得困難：1）保持資料的局部性将有利于減少記憶體的存取負擔，緩存重新整理次數以及總線流量。而當多個處理器使用同一資料時，這些負擔将會經常發生；2）不幸的是，保持資料的局部性往往比較難以了解，并且其難度超過一般使用者的水準。

實作：單機共享記憶體機器，本地作業系統，編譯器及其對應的硬體都支援共享記憶體程式設計。在分布式記憶體機器上，記憶體在實體上存在于網絡上不同的結點上，但是可以通過特殊的硬體和軟體，将其變為全局可見。

5.3 線程模型

這是共享記憶體程式設計的一種模式。線上程模型中，一個單個的“重量級”程序可以擁有多個“輕量級”的并發執行路徑。例如下圖所示：

主程式 a.out 在本地作業系統上運作。a.out 需要加載所有的系統和使用者資源來運作，這是裡面的“重量級”程序。
a.out 首先執行一些串行工作，然後生成一系列任務（線程），而這些線程可以在作業系統中被并發地執行。
每個線程具有本地資料，但同時也共享 a.out 的所有資源。這節約了所有線程都複制程式資源的的開銷。而每個線程同時也從全局記憶體中獲益，因為它可以共享 a.out 的記憶體空間。
一個線程的工作可以被描述為主程式的一個子程式。任何線程都可以在其它線程運作的同時執行任何子程式。
線程之間的通訊通過全局記憶體來實作（對全局位址的更新）。這需要建立一種同步機制，以保證在同一時刻，不會有多個線程對同一塊位址空間進行更新。
線程可以随時生成和結束，但是 a.out 卻一直存在，以提供所需的共享資源，直到整個應用程式結束。

實作：從程式設計的角度來講，線程的實作通常包括如下兩個方面：

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

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

線程并不是一個新概念。之前硬體供應商就曾經實作過他們自己的線程。由于這些線程的實作各不相同，是以使得程式員很難開發可移植的多線程應用程式。

而标準化工作卻導緻了兩種完全不同的線程實作方式：POSIX Threads 和 OpenMP。

POSIX Threads：由IEEE POSIX 1003.1c standard (1995)定義，僅支援C語言，是Unix/Linux作業系統的一部分，是基于庫函數的，也通常被稱為“Pthreads”。是非常明确的并行機制，需要程式員注意大量的細節。更多資訊可見：POSIX Threads tutorial。

OpenMP：是一個工業标準，有一組主要計算機硬體和軟體提供商，組織和個人聯合發起和定義，是基于編譯器指令的，具有可移植性/跨平台性，目前支援的包括Unix和Windows平台，目前支援C/C++和Fortran語言。非常簡單和醫用，提供了“增量并行”，可以從串行代碼開始。更多資訊可見：OpenMP tutorial。

也有一些其它的常見線程實作，但是在這裡沒有讨論，包括：

Microsoft threads
Java, Python threads
CUDA threads for GPUs

5.4 分布式記憶體/消息傳遞模型

這種模型具有如下特點：

在計算的過程中，每個任務都僅僅使用它們自身的本地記憶體。多個任務既可以寄宿在同一個實體機器上，也可以跨越不同的實體機器。
任務之間的資料交換是通過發送和接收消息而實作的。
資料傳輸通常需要不同程序之間的協同操作才能實作。例如，一個發送操作需要同時對應一個接收操作。

實作：從程式設計的角度來講，消息傳遞的實作通常包括子程式庫。對這些子程式的調用往往就嵌入在源代碼中。程式設計者負責并行機制的實作。

自從1980年代以來，出現了多種消息傳遞庫函數。這些實作各不相同，導緻程式設計者很難開發出移植性好的應用程式。自從1992年開始，MPI Forum形成，其主要目标是建立消息傳遞的标準接口。消息傳遞接口（Message Passing Interface (MPI)）的第一部分在1994年釋出，第二部分在1996年釋出，第三部分在2012年釋出。所有的MPI說明可以參見 http://mpi-forum.org/docs/。MPI成為了事實上的消息傳遞的工業标準，取代了所有其它消息傳遞的實作。幾乎所有流行的并行計算平台都存在MPI的實作，但并不是所有的實作都包含了MPI-1，MPI-2和MPI-3的所有内容。關于MPI的更多資訊可以參見 MPI tutorial。

5.5 資料并行模型

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

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

在共享記憶體的架構下，所有的任務通過全局記憶體方式來對資料進行存取；在分布式記憶體架構下，根據任務配置設定，全局資料結構在實體或者邏輯上被進行分割。

實作：目前，基于資料并行/PGAS模型，有如下幾個相對有名的實作：

Coarray Fortran: 為了支援SPMD并行程式設計而在Fortran 95上做的一個小的擴充，是編譯器相關的，更多資訊可以參見：https://en.wikipedia.org/wiki/Coarray_Fortran。
Unified Parallel C (UPC): 為了支援SPMD并行程式設計而在C語言基礎上做的擴充，也是編譯器相關的，更多資訊可以參見：http://upc.lbl.gov/。

5.6 混合模型

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

線程使用本地資料完成計算密集型的任務；
不同的程序則在不同的結點上通過MPI完成資料通訊。

這種混合模型非常适合目前流行的硬體環境——多核計算機組成的叢集系統。

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

采用MPI的任務運作于CPU上，使用本地記憶體上的資料，但是通過網絡與其它任務進行資料交換；
而計算密集型的核則被加載到GPU上進行計算；
而結點内部的記憶體和GPU上的資料交換則通過CUDA（或者類似的東西）進行資料交換。

其它混合模型還包括：

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

5.7 單程式多資料模型(SPMD)和多程式多資料模型(MPMD)

單程式多資料模型(Single Program Multiple Data (SPMD))： SPMD事實上是一種可以架構在其它并行程式設計模型之上的更“進階”的程式設計模型：

單程式：所有任務都執行同一個程式的拷貝，而這裡的程式可以是線程，消息傳遞，資料并行甚至混合；
多資料：不同的任務操作于不同的資料。

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

而這種采用消息消息傳遞或者混合程式設計的SPMD模型，有可能是今天運作在多核叢集系統上的最常見的并行計算模型了。

多程式多資料模型(Multiple Program Multiple Data (MPMD))：

和SPMD一樣，多程式多資料模型實際上也是一種可以架構在其它并行程式設計模型基礎上的“進階”并行程式設計模型：

多程式：任務可以同時執行不同的程式，這裡的程式可以是線程，消息傳遞，資料并行或者它們的混合。
多資料：所有的任務可以使用不同的資料。

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

6 并行程式設計

6.1 自動 vs. 手動并行化

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

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

完全自動：由編譯器分析源代碼并且識别可以并行化的部分，這裡的分析包括識别出哪些部分滿足并行化的條件，以及權衡并行化是否真的可以提高性能。循環（包括do, for）通常是最容易被并行化的部分。
程式員指令：通過采用“編譯器指令”或者編譯器辨別，程式員明确地告訴編譯器如何并行化代碼，而這可能會和某些自動化的并行過程結合起來使用。

最常見的由編譯器生成的并行化程式是通過使用結點内部的共享記憶體和線程實作的（例如OpenMP）。

如果你已經有了串行的程式，并且有時間和預算方面的限制，那麼自動并行化也許是一個好的選擇，但是有幾個重要的注意事項：1）可能會産生錯誤的結果；2）性能實際上可能會降低；3）可能不如手動并行那麼靈活；4）隻局限于代碼的某個子集（通常是循環）；5）可能實際上無法真正并行化，由于編譯器發現裡面有依賴或者代碼過于複雜。

接下來的部分僅适用于手動開發并行程式。

6.2 了解問題和程式

毫無疑問，開發并行程式的第一步就是了解你将要通過并行化來解決的問題。如果你是從一個已有的串行程式開始的，那麼你需要首先了解這個串行程式。

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

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

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

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

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

識别程式的關鍵點 (hotspots)：

了解哪個部分完成了程式的大多數工作。大多數的科學和技術程式中，大多數的工作都是在某些小片段中完成的。
可以通過剖析器或者性能分析工具來幫助你分析。
專注于程式中這些關鍵點，忽略那些占用少量CPU的其餘部分。

識别程式中的瓶頸 (bottlenecks)：

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

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

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

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

6.3 分割 (Partitioning)

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

域分解：在這種分割方式中，将數根據問題進行分解。每個并行任務操作資料的一部分。

通常由不同的方式來對資料進行分割：

功能分解：

在這種方法中，重點在于要執行的計算，而不是計算所操縱的資料。問題根據要做的工作進行分解，然後每個任務執行整個工作的一部分。

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

生态系統模組化：每個程式計算給定組的人口，其中每個組的正常取決于其鄰居的增長。鎖着時間的推移，每個程序計算目前狀态，然後與相鄰群體交換資訊。然後所有任務進行下一步計算。

信号處理：音頻信号資料集通過四個不同的計算濾波器，每個濾波器是一個單獨的過程。第一段資料必須通過第一個濾波器，然後才能進入第二個濾波器。當這樣做時，第二段資料通過了第一個濾波器。當第四個資料段處于第一個濾波器時（以及之後），四個任務都會變得很忙。

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

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

6.4 通訊 (Communications)

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

不需要通訊的情況：一些程式可以被分解成為并發執行的任務，而這些任務之間不需要共享資料。這類問題往往被稱為“尴尬并行”——任務之間不需要資料通訊。例如如果我們需要對下面一副圖檔的顔色進行取反（黑色的部分變為白色的，白色的變為黑色的），那麼圖像資料可以被簡單地分解為多個任務，并且每個任務可以被獨立地執行。

需要通訊的情況：大多數并行程式并不像上一問題這麼簡單，任務之間确實需要共享資料。例如下面這幅熱度擴散圖需要一個任務知道其它任務在它的鄰居方格中的計算結果。鄰居資料的變化将直接影響到該任務的資料。

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

通訊開銷： 1）任務間通訊幾乎總是意味着開銷。2）而可以用于計算的機器周期以及資源會轉而用于對資料的封裝和傳輸。3）頻繁的通訊也需要任務之間的同步，這有可能會導緻任務花費時間等待而不是執行。4）競争通訊流量可能使可用的網絡帶寬飽和，進而進一步加劇性能問題。
延遲 vs. 帶寬： 1）延遲指的是從A點到B點發送最小量的資訊所需要花費的時間，通常以毫秒計。2）帶寬指的是機關時間内可以傳輸的資料總量，通常以M/S或者G/S來計。3）發送大量的短消息可能會導緻延遲成為通訊的主要開銷。通常情況下将大量小資訊封裝成為大消息會更加有效，進而提高通訊帶寬的利用效率。
通訊可見性： 1）在消息傳遞模型中，通訊往往是顯式和可見的，并且在程式設計者的控制之下。2）在資料并行模型中，通訊對程式設計者來說往往是透明的，尤其是在分布式記憶體架構中。程式設計者往往甚至不能明确知道任務之間的通訊是如何完成的。
同步 vs. 異步通訊： 1) 同步通訊需要共享資料的任務之間某種意義上的“握手”。這既可以由程式設計者顯式地指定，也可以在底層被隐式地實作而不為程式設計者所知。2）同步通訊業常常被稱為“阻塞通訊”，因為一些任務必須等待直到它們和其它任務之間的通訊完成。3）異步通訊允許任務之間獨立地傳輸資料。例如任務1可以準備并且發送消息給任務2，然後立即開始做其它工作，它并不關心任務2什麼時候真正受到資料。4）異步通訊也常常被稱為“非阻塞通訊”，因為在通訊發生的過程中，任務還可以完成其它工作。5）在計算和通訊自由轉換是異步通訊的最大優勢所在。
通訊的範圍：明确哪些任務之間需要通訊在設計并行代碼的過程中是非常關鍵的。下面兩種通訊範圍既可以被設計為同步的，也可以被設計為異步的：1）點對點通訊：涉及到兩個任務，其中一個扮演消息發送者/生産者的角色，另外一個扮演消息接受者/消費者的角色。2）廣播通訊：涉及到多于兩個任務之間的資料共享。這些任務通常處于一個組或者集合中。

通訊的效率：通常程式設計者具有影響通訊性能的選擇，這裡列舉其中一些：1）對于一個給定的模型，究竟應該采用哪一種實作？例如對于消息傳遞模型而言，一種MPI的實作可能在某個給定的硬體下比其它實作要快。2）什麼采用什麼類型的通訊操作？正如前面所提到的，異步通訊操作往往可以提高程式的整體性能。3）網絡結構（network fabric）：某些平台可能會提供多于一個的網絡結構。那麼究竟哪一個最好？
開銷和複雜性：

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

6.5 同步 (Synchronization)

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

同步的類型：

屏障： 1）這通常意味着會涉及到所有任務；2）每個任務都執行自身的工作，直到它遇到屏障，然後它們就停止，或者“阻塞”；3）當最後一個任務到達屏障時，所有任務得以同步；4）接下來可能發生的事情就有所變化了。通常會執行一段串行代碼，或者所有的任務在這裡都結束了。
鎖/信号量： 1）可以涉及任意多個任務；2）通常用于對全局資料或者某段代碼的存取串行化（保護），在任一時刻，隻有一個任務可以使用鎖/信号量；3）第一個任務會獲得一個鎖，然後該任務就可以安全地對該保護資料進行存取；4）其它任務可以嘗試去獲得鎖，但必須等到目前擁有該鎖的任務釋放鎖才行；5）可以是阻塞的也可以是非阻塞的。
同步通訊操作： 1）僅僅涉及到執行資料通訊操作的任務；2）當一個任務執行資料通訊操作時，通常需要在參與通訊的任務之間建立某種協調機制。例如，在一個任務發送消息時，它必須收到接受任務的确認，以明确目前是可以發送消息的；3）在消息通訊一節中也已經說明。

6.6 資料依賴性 (Data Dependencies)

定義：

依賴：當語句的執行順序影響程式的運作結果時，我們稱程式語句之間存在依賴關系。
資料依賴：資料依賴是由不同任務多次存取相同的記憶體位置而産生的。

資料依賴也是并行程式設計中的關鍵，因為它是并行化中一個重要的抑制因素。

例子：

循環相關的資料依賴：下面這段代碼中， A(J-1) 必須在 A(J) 之前被計算出來，是以說 A(J) 與 A(J-1) 之間存在資料依賴，是以并行化在這裡被抑制。如果任務2中有 A(J) ，任務1中有 A(J-1) ，那麼要計算出正确的 A(J) 則需要：1）分布式記憶體架構：任務2必須在任務1計算結束之後，從任務1處中擷取 A(J-1) 的值。2）共享記憶體架構：任務2在任務1完成對 A(J-1) 的更新之後，對 A(J-1) 進行讀取。

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

循環無關的資料依賴：在下面的例子中并行化也同樣被抑制。 Y 的值依賴于：1）分布式記憶體架構：在任務之間是否需要或者何時需要對 X 的值的通訊。2）共享記憶體架構：哪個任務最後存儲 X 的值。

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

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

盡管在并行程式設計中，對所有資料依賴的識别都是重要的，但循環相關的資料依賴尤其重要，因為循環往往是最常見的可并行化部分。

處理方法： 1）分布式記憶體架構：在同步點傳輸所需資料；2）共享式記憶體結構：在任務之間同步讀寫操作。

6.7 負載均衡 (Load Balancing)

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

如何實作負載均衡：

平均配置設定任務量：

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

采用動态任務配置設定方法：

即使資料在任務之間被平均配置設定，但是某些特定類型的問題也會導緻負載不平衡，如下面三個例子所示。

稀疏矩陣：某些任務會具有真實資料，而大多數任務對應的資料卻為0。

自适應網格：某些方格需要被細分，而其它的不需要。

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

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

最終來看，可能需要設計一種在代碼中動态發生和處理負載不平衡的算法。

6.8 粒度 (Granularity)

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

細粒度并行化 (Fine-grain Parallelism)： 1）在通訊事件之外進行相對較少的計算工作；2）計算通訊率較低；3）友善負載均衡；4）意味着較高的通訊開銷以及較少的性能提升機會；5）如果粒度過細，任務之間的通訊和同步的開銷可能需要比計算更長的時間。

粗粒度并行化 (Coarse-grain Parallelism)： 1）在通訊/同步事件之外需要較大量的計算工作；2）較高的計算/通訊比；3）意味着較大的性能提升機會；4）難以進行較好的負載均衡。

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

6.9 輸入輸出 (I/O)

壞消息： 1）I/O操作通常被認為是并行化的抑制劑；2）I/O操作通常比記憶體操作需要多個數量級的時間；3）并行I/O系統可能不成熟或者不适用于所有平台；4）在所有任務均可以看到相同檔案空間的環境中，寫操作可能導緻檔案被覆寫；5）讀操作可能受到檔案伺服器同時處理多個讀取請求的能力影響；6）必須通過網絡進行的I/O操作（NFS，非本地）可能導緻嚴重的性能瓶頸，甚至導緻檔案伺服器崩潰。

好消息：已經具有不少并行檔案系統，例如：

GPFS：通用并行檔案系統 (General Parallel File System)（IBM），現在也被稱為IBM Spectrum Scale。
Lustre：針對Linux的叢集（Intel）。
HDFS：Hadoop分布式檔案系統（Apache）。
PanFS：Panasas ActiveScale File System for Linux clusters (Panasas, Inc.)
更多并行檔案系統可以參加這裡。

作為MPI-2的一部分，1996年以來MPI的并行I/O程式設計借口規範已經可用。

注意事項： 1）盡可能減少整體I/O操作；2）如果你有權通路并行檔案系統，請使用它；3）在大塊資料上執行少量寫操作往往比在小塊資料上進行大量寫操作有着更明顯的效率提升；4）較少的檔案比許多小檔案更好；5）将I/O操作限制在作業的特定串行部分，然後使用并行通訊将資料分發到并行任務中。例如任務1可以讀輸入檔案，然後将所需資料傳送到其它任務。同樣，任務2可以再從所有其它任務收到所需資料之後執行寫入操作；6）跨任務的I/O整合——相比于很多任務都執行I/O操作，更好地政策是隻讓一部分任務執行I/O操作。

6.10 調試 (Debugging)

調試并行代碼可能非常困難，特别是随着代碼量的擴充。而好消息是有一些優秀的調試器可以提供幫助：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）（本地開發）。

更多的資訊可以參考：LC web pages，TotalView tutorial。

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

對于調試而言，并行程式的性能分析和調優比串行程式更具挑戰性。幸運的是，并行程式性能分析和調優有很多優秀的工具。Livemore計算機使用者可以通路這種類似工具，其中大部分都在叢集系統上。一些安裝在LC系統上的工具包括：

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 數組處理

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

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

問題：

該問題是否可以被并行化？
如果對該問題進行分割？
需要資料通訊嗎？
有沒有資料依賴？
有沒有同步需求？
是否需要考慮負載均衡？

并行方案1：

由于對元素的計算彼此之間是獨立的，是以可以有“尴尬并行”的解決方案。
由于數組元素是均勻分布的，是以每個程序可以擁有陣列的一部分（子陣列）。1）可以選擇最佳配置設定方案以實作高效的記憶體通路，例如選擇步幅為1，或者選擇合适的步幅以最大化緩存/記憶體使用。2）由于可以使單元跨越子陣列，是以配置設定方案的選擇也取決于程式設計語言，有關選項可以參見第 6.3 節。
由于數組元素的計算是彼此獨立的，是以不需要任務之間的通訊和同步。
由于任務之間的工作量是被平均配置設定的，是以不需要考慮負載均衡。
對數組分割之後，每個任務執行與其擁有的資料相對應的循環部分，其源代碼類似于：
請注意隻有外部循環變量與串行解決方案不同。

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

一種可能的解決方案： 1）采用單程式多資料 (SPMD) 模型進行實作，每個任務執行相同的程式；2）主程序對數組進行初始化，将資訊發送給子任務，并且接收計算結果；3）子程序接收到資訊之後，執行計算任務，并且将結果發送給主程序；4）采用Fortran的存儲結構，對數組進行塊劃分；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：

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

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

任務池模式：裡面包含兩個程序：

主程序： 1）擁有任務池；2）如果得到請求，給工作程序發送工作任務；3）從工作程序出收集傳回結果。
工作程序： 1）從主程序處擷取任務；2）執行計算任務；3）向主程序發送結果。

工作程序在運作之前不知道它将處理數組的哪一部分，以及它将執行多少任務。動态負載均衡發生在運作時：運作最快的任務将完成更多的任務。一段可能的源代碼如下：

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）在上述任務池例子中，每個任務計算數組的某一個元素，計算與通訊比率是細粒度的；2）細粒度的解決方案為了減少任務空閑時間，往往會導緻更多的通訊開銷；3）更好地解決方案可能是在每個任務中配置設定更多的工作，“正确”的工作量依然是依賴于具體問題的。

7.2 圓周率計算

計算圓周率的方法有多種。我們這裡采用蒙特卡洛方法來近似計算圓周率：1）在一個邊長為 2r2r 的正方形中畫一個半徑為 rr 的内接圓；2）内接圓的面積是 πr2πr2，正方形的面積是 4r24r2；3）圓的面積與正方形的面積之比是 πr2/4r2=π/4πr2/4r2=π/4；4）如果你在正方形内随機地産生 NN個點，那麼大約會有 N∗π/4N∗π/4 個點（MM）會位于内接圓内；5）是以 ππ 可以被近似為：N∗π/4=MN∗π/4=M，π/4=M/Nπ/4=M/N，π=4∗M/Nπ=4∗M/N；6）注意越多的點産生，則對 ππ的近似就越準确。

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

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

該問題是計算密集型的——大多數時間将花費在對循環的執行。

如何對該問題進行分割？
任務之間是否需要通訊？
是否存在資料依賴？
任務之間是否有同步需求？
需要考慮負載均衡嗎？

解決方案：

又一個容易被并行化的問題：1）每個點的計算都是獨立的，不存在資料依賴；2）工作可以被平均配置設定，不需要考慮負載均衡；3）任務之間不需要通訊和同步。

并行化政策：1）将任務平均劃分為相同大小的多個部分，用于在任務池中被執行；2）每個任務獨立地完成任務；3）采用單程式多資料（SPMD）模型；4）其中一個任務作為主程序來收集計算結果，并且計算 ππ 的值。

下面是并行化之後的僞代碼：

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

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

二維熱方程問題描述了在給定初始溫度分布以及邊界條件的情況下，溫度随着時間的變化。有限差分方案可以采用數值方法求解正方形區域内的熱擴散方程：

二維數組的元素用來表示正方形區域内的點的溫度；
邊界處的初始問題是0，中心點的問題最高；
邊界處的問題會保持為0；
采用時間步長算法。

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

Ux,y=Ux,y+Cx∗(Ux+1,y+Ux−1,y−2∗Ux,y)+Cy∗(Ux,y−1+Ux,y−1−2∗Ux,y)Ux,y=Ux,y+Cx∗(Ux+1,y+Ux−1,y−2∗Ux,y)+Cy∗(Ux,y−1+Ux,y−1−2∗Ux,y).

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

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

任務之間是否需要同步？

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

确定資料依賴：1）一個任務的内部元素和其它任務之間不存在資料依賴；2）一個任務的邊界元素則和它的鄰居任務之間需要産生資料通訊。

采用單程式多資料模型（SPMD）進行實作：1）主程序向工作程序發送初始資訊，然後等待并收集來自工作程序的計算結果；2）工作程序在特定的時間步長内計算結果，并與鄰居程序之間進行資料交換。僞代碼如下：

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 一維波動方程

在這個例子中，我們計算經過指定時間量之後，一維波動曲線的振幅。其中的計算會涉及到：1）y軸上的振幅；2）x軸上的位置索引i；3）沿着波動曲線的節點；4）以離散時間步長更新振幅。

這裡需要求解的是如下一維波動方程，其中c是常數。

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)。

人物之間是否存在資料依賴？

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

采用單程式多資料（SPMD）模型的實作：1）主程序向工作程序發送初始資訊，并且等到各個工作程序傳回計算結果；2）工作程序對特定步長之内的任務進行計算，并且在必要的時候和鄰居程序進行資料通訊。其僞代碼如下：

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.
在網際網路上搜尋“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成員建立，或者從不涉及版權的政府或公領域（）擷取，或者經所有者同意從其示範文稿或者網頁上擷取。
曆史：該材料有下面的資源演化而來，而這些資源将不再被維護或者不再可用。
- 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.