轉自：http://www.cnblogs.com/wasd/archive/2009/04/07/1430859.html
并行計算簡介
作者：?Blaise Barney,?勞倫斯利弗莫爾國家實驗室
譯者：盧洋，同濟大學，2009年4月
原文地址：https://computing.llnl.gov/tutorials/parallel_comp/
?
目錄
1?摘要
2?概述
2.1?什么是并行計算
2.2?為什么使用并行計算
3?概念和術語
3.1?馮諾依曼體系結構
3.2 Flynn經典分類法
3.3?一些通用的并行術語
4?并行計算機存儲結構
4.1?共享內存
4.2?分布式內存
4.3?混合型分布式共享內存
5?并行編程模型
5.1?概覽
5.2?共享內存模型
5.3?線程模型
5.4?消息傳遞模型
5.5?數據并行模型
5.6?其他模型
6?設計并行程序
6.1?自動化?vs.?手工并行化
6.2?問題的理解和程序
6.3?問題分解
6.4?通信
6.5?同步
6.6?數據依賴
6.7?負載平衡
6.8?粒度
6.9 I/O
6.10?并行程序設計的限制和消耗
6.11?性能分析與調整
7?并行示例
7.1?數組程序
7.2 PI?的計算
7.3?簡單的加熱等式
7.4?一維的波等式
8?參考和更多信息
1?摘要
???????為了讓新手更加容易熟悉此話題，本教程覆蓋了并行計算中比較基礎的部分。首先在概述中介紹的是與并行計算相關的術語和概念。然后探索并行存儲模型和編程模型這兩個話題。之后討論一些并行程序設計相關的問題。本教程還包含了幾個將簡單串行化程序并行化的例子。無基礎亦可閱讀。
?
2?概述
2.1?什么是并行計算
l?????????傳統上，一般的軟件設計都是串行式計算：
2????????軟件在一臺只有一個CPU的電腦上運行；
2????????問題被分解成離散的指令序列；
2????????指令被一條接一條的執行；
2????????在任何時間CPU上最多只有一條指令在運行
?
?
?
l?????????在最簡單的情形下，并行計算是使用多個計算資源去解決可計算問題。
2????????用多核CPU來運行；
2????????問題被分解成離散的部分可以被同時解決；
2????????每一部分被細分成一系列指令；
2????????每一部分的指令可以在不同的CPU上同時的執行；
?
?
?
?
l?????????計算資源可以包括：
2????????多核CPU；
2????????任意數量的CPU用網絡連接起來；
2????????或者以上兩者結合；
l?????????可計算問題通常展示出如下的特性：
2????????能分解成可以同時解決的離散的工作塊；
2????????同一時刻可以執行多條程序指令；
2????????通常用多個計算資源解決問題所花的時間要比單個計算資源要短；
?
??????宇宙是并行的
l?????????并行計算是由串行計算發展而來，試圖去模仿真實世界中事物的處理過程：許多復雜的互相關聯的事件同時發生，例如：
銀河系的變換；????行星的運動；???????天氣和海洋的變化；
交通堵塞；???????????大陸板塊遷移；????炊煙升起；
自動的流水線；????建造空間飛行器；???????開車買漢堡；
?
?
?
?
????????并行計算的用途：
l?????????在歷史上，并行計算被認為是高端計算，并用于為復雜的科學計算和基于真實世界的工程問題建模。下面是一些例子：
2????????大氣層、地球、環境
2????????物理學應用、核能、原子能、凝聚態、高壓、溶解、光電子；
2????????生物科學、生物工程、基因學
2????????化學、分子科學
2????????地理和地震學
2????????機械工程、從彌補術到空間飛行器
2????????電氣工程、電路設計、微電子學
2????????計算機科學、數學
?
?
??
?
l?????????今天，商務應用是推動快速計算機發展的更大的推動力。這些應用需要用復雜的方法處理大量數據。例如：
2????????數據庫、數據挖掘
2????????石油勘探
2????????網絡搜索引擎、基于網絡的商務服務
2????????醫學成像和診斷
2????????制藥設計
2????????國有企業或跨國企業的管理
2????????金融經濟建模
2????????高級制圖和虛擬現實、特別實在娛樂事業上
2????????網絡視頻和多媒體技術
2????????協同工作環境
?
?
?
2.2?為什么使用并行計算
??????????主要的原因有：
l?????????節省時間和成本：理論上，使用更多的資源會使一個任務提前完成，而且會節約潛在的成本。況且可以使用便宜的、甚至市面將要淘汰的CPU來構建并行聚簇。
?
?
| ? | ??? | ? |
???
l?????????解決更大規模的問題：很多問題是相當龐大而復雜的，尤其是當計算機的內存受到限制的時候，用單個計算機來解決是不切實際或者根本不可能的。例如：
2????????"Grand Challenge" (en.wikipedia.org/wiki/Grand_Challenge)?問題需要Peta級浮點運算能力和存儲空間的計算資源。
2????????網絡搜索引擎和網絡數據庫每秒鐘要執行上百萬次的處理。
?
?
?
l?????????支持并行：單一的計算資源在同一時刻只能做一件事情。多個計算資源能夠同時做很多事情。例如：Access Grid (http://www.accessgrid.org/)提供一個全球的合作網絡，在這里來自世界上不同國家的人們可以開會并“現場”指導工作。
?
?
?
l?????????使用非本地資源：?當缺少本地計算資源的時候可以使用廣泛的網絡或Internet計算資源。例如：
2???????SETI@home (setiathome.berkeley.edu)?使用超過330000個計算機來執行每秒超過528T次浮點運算；(August 04, 2008)
2???????Folding@home (folding.stanford.edu)使用超過340,000?計算機來執行每秒4.2P次浮點運算?(November 4, 2008)
?
?
?
l?????????串行計算的限制：在理論上和實際上，想要輕易地制造更快的串行計算機存在著巨大的限制。
2????????傳輸速度——線性計算機的執行速度直接取決于數據在硬件中傳輸的速度。光速的絕對限制是每納秒30cm，銅導線是每納秒9cm。不斷提升的執行速度更加靠近極限。
2????????微型化的極限——處理器技術使芯片集成了更多的晶體管。但是，即使使用分子或者原子級別的組件也會很快達到芯片集成晶體管的極限。
2????????經濟上的限制——讓單個芯片變得更快需要增加昂貴的投入。用多個一般的芯片來取代單個高性能的芯片或許性能會更好而且更便宜。
?
現在的計算機體系結構越來越依賴于硬件層次的并行來提高性能：
2????????多個執行單元
2????????管道指令
2????????多核
?
?????????誰？什么？
l?????????Top500.org?給出了并行計算用戶的數據統計——下面的圖標只是一個樣例。下面幾點需要注意：
2????????扇形可能重疊——例如，研究的部分可能在經典研究中。作者不得不二選一。
2????????目前為止未分類的最大應用可能是多種應用集合。
?
?????????未來
在過去的20年里，更快速網絡、分布式系統、多核處理器體系結構（甚至是在桌面應用級別）的發展趨勢已經很清楚的指出并行化是未來科學計算的發展方向。
?
?
3?概念和術語
3.1?馮諾依曼體系結構
以匈牙利數學家約翰.?馮諾依曼命名，他是第一個在1945年的論文中提出通用電子計算機必要條件的創始人。
從那時開始，實際上所有的計算機都遵從這個基本的設計，區別于早期的硬布線編程的計算機設計。
主要有五個主要的部件構成：內存、控制單元、邏輯計算單元、輸入輸出
?
讀/寫，隨機存儲內存用于儲存程序指令和數據：程序指令是告訴計算機做什么事的代碼數據、數據是程序用到的簡單數據。
控制單元從內存中取回指令/數據，解碼指令然后連續協調操作來完成編碼工作。
計算單元完成基本的計算操作。??????
輸入輸出是用戶操作的界面。
?
?
| ? |
?
3.2 Flynn經典分類法
有很多方法給并行計算機分類，其中，Flynn分類法從1966年開始使用被大家廣為接受。
Flynn分類是利用兩個獨立的標準指令和數據對多核計算機體系結構進行劃分的。每一個標準有兩種可能的值：單個或者多個
?
| ? |
下面的矩陣定義了4中可能的Flynn分類
| S I S D 單指令單數據 | S I M D 單指令多數據 |
| M I S D 多指令單數據 | M I M D 多指令多數據 |
?
?
?
??????????單指令單數據（SISD）
串行計算機
單個指令：在一個系統時鐘周期只有一條指令可以被執行。
單數據：在一個系統時鐘周期只有一個數據流可以被用來輸入。
確定性執行。
這是迄今為止最老的，但大多數通用計算機都是這個類型。
例如：老一代的大型機、微機和工作站，還有現在大多數的PC機。
?
?
| UNIVAC1 | IBM 360 | CRAY1 |
| CDC 7600 | PDP1 | Dell Laptop |
?
??????????
| ? |
單指令多數據：
并行計算機的一種
單指令：所有的處理單元在給定的時鐘周期只能
執行相同的指令。
多數據：每一個處理器單元可以同時處理不同的
數據元素。
最適合處理高度規則的問題，如圖形圖像處理。
同步，確定性執行。
兩類：處理器數組和向量流水線。
例如：處理器矩陣：Connection Machine CM-2,
?MasPar MP-1 & MP-2, ILLIAC IV；向量流水線：IBM 9000, Cray X-MP, Y-MP & C90, Fujitsu VP, NEC SX-2, Hitachi S820, ETA10。
最先進的計算機，特別是帶有圖形處理器單元的計算機都使用SIMD指令集和執行單元。
?
?
?
| ILLIAC IV | MasPar | ????????? |
| Cray X-MP | Cray Y-MP | Thinking Machines CM-2 | Cell Processor (GPU) |
?
?
?????????多指令單數據（MISD）：
單數據流進入多處理器單元。
每一個處理器單元通過獨立的指令流在獨立的操作數據。
這種計算機幾乎在市面上找不到。有一個實驗機Carnegie-Mellon C.mmp
可能用于單信號流上多頻率過濾、用多密碼學算法破解單碼信息。
?
?
?
??????????多指令多數據（MIMD）
現在，大多數通用并行計算機都是這種。
多指令：每個處理器可以執行不同的指令流
多數據：每個處理器可以用不同的數據流。
同步或異步、確定性或非確定性執行。
例如：大多數的超級計算機、網格計算機、多核SMP計算機，多核PC機。
???????注意：很多MIMD體系結構也包含SIMD執行子構件。
?
?
?
?
?
?
3.3?一些通用的并行術語
???????像其他的東西一樣，并行計算機有他自己的術語。下面列出了一些與并行計算相關的通用的術語。其中大多數都會在后面再進行詳細的討論。
Task：可計算工作在邏輯上不連續的分區。一個任務通常是一個程序或者類似程序一樣的可以被處理器執行的指令集。
Parallel Task：一個任務可以被多個處理器安全的并行的執行，產生正確的結果。
Serial Execution：程序相繼的執行，每次一個狀態。在最簡單的情況下，單核處理器就是這樣運行的。可是，實際上所有并行的任務有一些并行程序的區域一定要串行的執行。
Parallel Execution：一個或多個任務同時執行的程序，每個任務同時能夠執行相同的或不同的代碼語句。
Pipelining：不同的處理器單元把一個任務根據輸入流來分解成一系列步驟來執行，相當于一條流水線；并行計算的一種。
Shared Memory（共享內存）：完全從硬件的視角來描述計算機體系結構，所有的處理器直接存取通用的物理內存（基于總線結構）。在編程的角度上來看，他指出從并行任務看內存是同樣的視圖，并且能夠直接定位存取相同的邏輯內存位置上的內容，不管物理內存是否真的存在。
Symmetric Multi-Processor（對稱多處理器）：這種硬件體系結構是多處理器共享一個地址空間訪問所有資源的模型；共享內存計算。
Distributed Memory（分布式存儲）：從硬件的角度來看，基于網絡存儲的物理內存訪問是不常見的。在程序模型中，任務只能看到本地機器的內存，當任務執行時一定要用通信才能訪問其他機器上的內存空間。
Communication：并行任務都需要交換數據。有幾種方法可以完成，例如：共享內存總線、網絡傳輸，然而不管用什么方法，真實的數據交換事件通常與通信相關。
Synchronization：實時并行任務的調度通常與通信相關。總是通過建立一個程序內的同步點來完成，一個任務在這個程序點上等待，直到另一個任務到達相同的邏輯設備點是才能繼續執行。同步至少要等待一個任務，致使并行程序的執行時間增加。
Granularity（粒度）：在并行計算中，粒度是定量化的用來測定通信和計算比率的方法。粗糙級：在兩個通信事件之間可以完成相對大量的可計算工作。精細級：在兩個通信事件之間只能完成相對較少量的可計算工作。
Observed Speedup：測量代碼并行化之后的加速比。這是最簡單也最廣泛使用的測量并行程序性能的方法。
| wall-clock time of serial execution ———————————————————— wall-clock time of parallel execution |
Parallel Overhead（并行開銷）：對并行任務調度花費的時間沒有做有用的工作。并行開銷可以包含如下因素：任務啟動時間、同步、數據通信、并行編譯器、庫、工具、操作系統等花費的軟件開銷，任務終止的時間等。
Massively Parallel（大規模并行）：指包含給定的并行系統硬件——有多個處理器。“多個“的意思是可以不斷的增加，但是目前大規模并行計算機由上百個處理器構成。
Embarrassingly Parallel：同時解決很多相似的獨立的任務；任務之間基本不需要調度。
Scalability：指的是并行系統通過增加更多的處理器的個數按比例提高并行性能的能力。促進可擴展性的因素有：硬件——特別是內存、CPU帶寬和網絡通信，應用程序算法，相關的并行開銷、特定的應用和編碼方式的特征。
Multi-core Processors：一個CPU上有多個處理器。
Cluster Computing：用一般的處理器單元（處理器、網絡、SMP）來構建并行系統。
Supercomputing / High Performance Computing（高性能計算）：使用世界上最快最大的機器來解決大規模的問題。
?
?
4?并行計算機存儲結構
4.1?共享內存
??????????一般特性：
???????共享內存計算機有很多種類，但是都有一個共同的特點，所有的處理器都把內存作為全局的地址空間來進行訪問。
???????多處理器能夠單獨的運行，但是都共享相同的內存地址。
???????一個處理器對內存的修改對其他的處理器是可見的。
???????共享內存的機器可以根據內存的存取次數大體分成兩類：UMA和NUMA。
??????????UMA統一的內存訪問
???????現在大多數的SMP處理器就屬于此類。
???????同核處理器。
???????對內存的存儲機會和次數均等。
???????緩存連貫意思是如果一個處理器更新共享內存，
其他的所有處理器都會知道。這是由硬件層來實現的。
??????????NUMA非統一的內存訪問
???????通常是在物理層上鏈接兩個或多個SMP構成的。
???????一個SMP能夠直接訪問另一個SMP的內存
???????不是所有的處理器都有對內存平等的訪問機會
???????通過連接的內存訪問會更慢
???????如可以保持緩存的連貫性，也可以叫做CC-NUMA - Cache Coherent NUMA。
??????????優點：
???????全局的地址空間提供了一個對用戶友好的編程視角。
???????由于內存CPU之間的密切合作使得任務間的數據共享即快速又統一。
??????????缺點：
???????主要的缺點是內存和CPU之間的可擴展性較差。增加CPU之后會增加共享內存和CPU之間傳輸時間，在緩存連貫的系統中，也會增加與緩存內存管理相關的數據流量。
???????程序員有責任同步系統以確保正確的訪問全局存儲空間。
???????代價：用更多的處理器設計和生產共享內存機器越來越困難而且越來越昂貴。
?
Shared Memory (UMA)
?
Shared Memory (NUMA)
?
4.2?分布式內存
??????????一般特征：
像共享內存系統一樣，分布式內存系統也有很多種，但是有一個共同特點：分布式存儲系統需要通信網絡來連接核間內存。
?
???????處理器都有各自的內部寄存器。一個核內的存儲地址對其他核不可見，對于所有CPU都沒有全局地址空間的概念。
???????由于每個處理器都有自己獨立的內存，本地內存的改變將不會影響到其他的處理器。因此沒有實現緩存一致性。
???????當一個處理器需要訪問另一個處理器的數據時，程序員的任務就是清楚的定義什么時候用什么方法來通信。任務間的同步問題也是程序員的職責。
???????總線網絡通信的方式有很多種，最簡單的方法類似以太網。
?
??????????優點：
a)???????內存可以和CPU的個數一起擴展。增加處理器的個數將使得內存的大小等比例增加。
b)??????每個處理器可以沒有沖突的快速訪問自己的內存，也不需維護緩存一致性的開銷。
c)???????成本效益：可以用一般的下市的CPU加上網絡來構建。
??????????缺點：
d)??????1程序員將要負責所有處理器間數據通信相關的細節問題。
e)???????2很難從基于全局內存空間的數據結構上建立起到分布式內存管理的映射。
f)???????3非統一的內存訪問次數。
?
4.3?混合型分布式共享內存
a)????當今最快最大計算機就是這種混合行分布式共享內存體系結構。
?
b)????共享內存組件通常用于緩存一致的SMP機器。在特定的SMP核上可以尋址機器的全局內存。
c)????分布式內存組件是由多個SMP網絡構成。SMP只能看到自己的緩存區。因此SMP間需要通信。
d)????現在的趨勢顯示這種類型的存儲體系結構將會在不遠的將來在高端計算機上繼續流行和發展。
e)????優點和缺點：同上。
?
?
5?并行編程模型
5.1?概覽
現在主要以下幾種通用的并行編程模型：共享內存、線程、消息傳遞、數據并行、混合模型。
??????????????并行編程模型是在硬件和內存體系結構層之上的抽象概念。
??????????????仔細研究可以發現，這些模型并不是為了某一個特定的機器或內存體系結構而設計的。事實上，這些模型都可以在硬件層之下實現。兩個例子：
??????????分布式內存機器上的共享內存模型：Kendall Square Research (KSR) ALLCACHE approach。機器的內存物理上的實現是分布式內存，但是對用戶來說是一個單一的全局地址空間。一般來說，這種方法叫做虛擬共享內存。注意：盡管KSR不再應用于商務貿易方面，但是不代表其他的供應商以后不會再利用這種方式。
??????????共享內存機器上的消息傳遞模型：MPI on SGI Origin。SGI Origin?使用?CC-NUMA類型的共享內存體系結構，這種體系結構可以使得每個任務都可以直接訪問全局內存。然而，MPI發送和接受消息的功能，就像通常在網絡上實現的分布式內存機器一樣，實現方法相似，還十分通用。
?
要使用哪個模型通常取決于可以獲得哪個模型和個人的選擇。盡管現在有模型相對于其他的來說確實有更好的實現方法，但是這里沒有“最好”的模型。
接下來將詳細描述上面提到的每個模型，也會討論它們的實現方法。
?
5.2?共享內存模型
a)?????????在共享編程模型中，任務間共享統一的可以異步讀寫的地址空間。
b)????????共享內存的訪問控制機制可能使用鎖或信號量。
c)?????????這個模型的優點是對于程序員來說數據沒有身份的區分，不需要特別清楚任務簡單數據通信。程序開發也相應的得以簡化。
d)????????在性能上有個很突出的缺點是很難理解和管理數據的本地性問題。
n?????????處理器自己的緩沖區中使用數據，使用完畢后刷新緩存寫入內存，此時可能發生多個處理器使用相同數據的總線沖突。
n?????????不幸的是，一般用戶很難理解或控制數據的本地化問題。
??????????實現
在共享內存平臺上，本地的編譯器將會把用戶程序變量轉換到全局地址空間中。
現在市面上還沒有一般的分布式內存平臺的實現。然而，先前在我們概覽部分提到的KSR，它就是在分布式的機器上提供了一個共享的數據平臺。
?
5.3?線程模型
??????????在并行編程的線程模型中，單個處理器可以有多個并行的執行路徑。
?
?
??????????線程模型的構成如下：
l?????????操作系統調度主程序a.out開始運行，a.out加載所有必要的系統資源和用戶資源開始執行。
l?????????a.out完成一些串行工作，然后創建一些可以被操作系統調度的并行任務（線程）去執行。
l?????????每次線程都有自己的數據，而且共享整個a.out的資源。這樣就節省了拷貝程序資源給每個線程的開銷。這樣線程之間可以并行執行子程序。
l?????????線程之間通過全局內存進行通信。這個需要同步構造來確保多個線程不會同時更新同一塊全局內存。
l?????????線程執行完了就自動銷毀，但是主程序a.out在應用程序完成之前一直存在，維護必要的共享資源。
?????????????
??????????線程通常和共享內存體系結構和操作系統相關。
?
u???????實現：
ü???????從程序的角度出發，線程的實現通常包括：
1）并行代碼需要調用的子程序庫；
2）串行或者并行源代碼中的一套編譯器指令。
ü???????在以上兩部分中，程序員都要負責制定所有的并行機制。
ü???????線程的實現并不是什么新技術，硬件供應商已經實現了他們自己的線程版本。線程的實現機制本質上的不同使得程序員很難開發出可以移植的多線程應用程序。
ü???????不同的標準產生了兩個不同的線程實現方式：POSIX線程和OpenMP
?
u???????POSIX線程：
ü?????????基于庫函數的，需要并行編碼。
ü?????????IEEE POSIX?1003.1c?中有具體描述。
ü?????????只適用于C語言
ü?????????通常是指Pthreads
ü?????????大多數的硬件供應商現在為自己的線程實現加入Pthreads
ü?????????十分清晰的并行，需要程序員特別關注實現的細節。
?
u???????OpenMP：
ü???????基于編譯器指令，可以使用串行代碼。
ü???????有一群計算機軟硬件廠商共同定義并支持。OpenMP在1997年完成Fortran的API，于1998年完成C/C++的API
ü???????簡潔而且跨平臺（Unix、Windows NT）
ü???????有C/C++和Fortran的實現
ü???????使用簡單，支持增量并行
微軟有自己一套獨立的線程實現機制，與以上兩者都不相關。
?
u???????更多信息
POSIX的教程computing.llnl.gov/tutorials/pthreads
OpenMP的教程computing.llnl.gov/tutorials/openMP
?
5.4?消息傳遞模型
消息傳遞模型有以下三個特征：
1）??計算時任務集可以用他們自己的內存。多任務可以在相同的物理處理器上，同時可以訪問任意數量的處理器。
2）??任務之間通過接收和發送消息來進行數據通信。
3）??數據傳輸通常需要每個處理器協調操作來完成。例如，發送操作有一個接受操作來配合。
?
?
?
??????????實現
從編程的角度上來看，消息傳遞的實現通常由源代碼中的子程序庫構成。程序員負責決定所有的并行機制。
1980年以來出現了大量的消息傳遞機制的庫函數。這些實現本質上是不同的，這就加大了程序員開發可移植的應用程序的難度。
1992年，建立了MPI討論組，他們的首要目標就是建立消息傳遞實現的標準接口。
消息傳遞接口（MPI）的第一部分于1994年完成，第二部分完成于1996年。兩部分MPI規范都可以在這里下載http://www-unix.mcs.anl.gov/mpi/。
MPI現在已經成為了工業界消息傳遞的標準了，并且代替了市面上幾乎所有的其他的實現方法。大多數比較流行的并行計算機都至少實現MPI的一個標準，有些還完全滿足標準2。
對于共享內存體系結構，MPI的實現通常不使用網絡來進行任務間的通信。替代的辦法是利用共享內存來進行通信，這樣可以提高性能。
?
??????????更多信息：
MPI的教程computing.llnl.gov/tutorials/mpi；
?
5.5?數據并行模型
l?????????數據并行模型有以下特性：
???????并行工作主要是操縱數據集。數據集一般都是像數組一樣典型的通用的數據結構。
???????任務集都使用相同的數據結構，但是，每個任務都有自己的數據。
???????每個任務的工作都是相同的，例如，給每個數組元素加4。
?
l?????????在共享內存體系結構上，所有的任務都是在全局存儲空間中訪問數據。在分布式存儲體系結構上數據都是從任務的本地存儲空間中分離出來的。
?
?
?
實現
l?????????使用數據并行模型編程通常都是用構造并行的數據來寫程序。構造方法是調用并行數據的子函數庫，然后數據并行編譯器就可以識別構造時用到的編譯器指令。
l?????????Fortran90和95：ISO/ANSI標準擴展于Fortran77：
??????????????包含Fortran77中的所有東西；加入新的代碼格式；添加新的特性集；增加程序結構和命令；增加函數、參數等變量；添加數組處理；增加新的遞歸函數和內部函數；和很多其他的新特性。大多數通用的并行平臺都可以使用。
l?????????編譯器指令：可以讓程序員指定數據的排列和分布。針對大多數的通用并行平臺都有Fortran的實現。
l?????????分布式內存模型的實現是用編譯器將程序轉換成標準的代碼，這些代碼通過調用MPI庫函數來將數據分配給所有的進程。所有的消息傳遞對于程序員來說是不可見的。
?
5.6?其他模型
上面提到的并行編程模型都是已經存在，而且會隨著計算機軟硬件的發展繼續進化。除了這些之外這里還有三個更為通用的模型。
??????????混合型：
這個模型中，是由兩個或多個模型組合在一起實現的。
當前通用的混合模型的例子就是：由消息傳遞模型（MPI）和線程模型（POSIX）或者共享內存模型（OpenMP）組成而成。
混合模型中其他比較通用的模型是：將數據并行和消息傳遞組成起來。正如我們上面在數據并行模型部分提到的那樣，在分布式體系結構上實現數據并行模型實際上是用消息傳遞的方法來為任務間傳遞數據的，對程序員是透明的。
?
??????????單程序多數據型（SPMD）：
SPMD實際上是一個高層次的編程模型，是在前面提到的并行編程模型基礎之上構建的。
一段程序可以被所有的任務同時的執行。
任務可以同時執行同一個程序中的相同或不同指令。
SPMD程序通常都包含必要的邏輯，使得任務可以有條件的或者分叉的執行那些可以被執行的程序。所以任務沒有必要去執行整個程序，很可能只執行一小塊程序就可以了。
所有的任務可能使用不同的數據。
?
?
?
??????????多程序多數據型（MPMD）：
與SPMD類似，MPMD也是高層次編程模型，建立在上面提到的并行編程模型之上。
MPMD應用程序多個執行程序。當程序并行執行時，每個任務可以執行相同或不同的程序作為自己的工作。所有的程序可能使用不同的數據。
?
?
?
6?設計并行程序
6.1?自動化?vs.?手工并行化
設計和開發并行程序是典型的人為設計的過程。程序員負責識別并行性和實現并行機制。
通常，手工開發并行代碼是一件費時、復雜、容易出錯和迭代的過程。
這些年以來，開發出多種工具幫助程序員吧串行的程序轉換成并行的程序。最通用的工具類型是并行化編譯器或預編譯器，它們可以自動把串行化程序并行化。
并行化編譯器通常有以下兩種工作方式：
1：全自動化
A）編譯器分析源代碼并識別代碼中的并行性。
B）?分析包括識別并行約束，計算使用并行機制所需要的代價，判斷是不是真的提高了性能。
C）?循環程序（do，for）是主要的自動并行化對象。
2：程序員直接指定并行化
A)?????使用編譯器指令或者編譯器標記，程序員清楚的告訴編譯器如何來并行化代碼。
B)?????也可能在程序中的一部分使用自動并行化。
?
如果你現在手中有串行的代碼需要并行化，而且時間和預算有限的情況下自動并行化可能是更好的選擇。但是在實施自動并行化之前這里有些很重要的警告應該事先告訴你。
A)?????可能產生錯誤的結果
B)?????性能可能反而下降
C)?????人為編程的并行性靈活性更好
D)?????只能用于代碼的子程序（主要是循環）
E)?????分析可能指出程序有依賴或者代碼過于復雜而不能并行化。
?
本章剩余的部分主要講解人為開發并行代碼。
?
6.2?問題的理解和程序
毫無疑問，開發并行軟件的第一步就是理解要并行處理的問題。如果寫好了串行化代碼，也有必要理解寫好的這份代碼。
???????在開始花時間嘗試開發問題的并行解決方案之前，首先應該判斷當前的問題是否真的可以被并行。
???????可并行化例子：為幾千個獨立的模塊構造方法計算潛在所需開銷，完成后找到花費最少的構造方法。這個例子可以被并行處理。每個模塊的構造方法是彼此獨立的。最小花費的計算也是可并行的問題。
???????不可并行化的例子：計算費伯那其Fibonacci數列（1，1，2，35，8，13，21……）F(K+2)=F(K+1)+F(K).這個問題不可以并行化，以為費伯那其數列的計算中每一項都依賴與其他項，而不是獨立的。K+2這個計算用到了K和K+1的結果。三個子句不可以獨立的計算，因此不可以并行。
?
???????識別程序中的關鍵點：
A）?了解程序中哪里做了大部分工作。大多數的科學和技術程序通常在某些地方完成了大部分的任務。
B）?性能分析工具在這里很有用。
C）?關注程序中關鍵點的并行，忽視那些只使用很少CPU利用率的部分程序。
?
識別程序中的瓶頸：
A)??????是否存在特別慢或者導致可并行的工作停止或延誤的程序段？例如：I/O經常是系統瓶頸。
B)?????有可能通過重構或者使用不同的算法可以減少或消除程序中的瓶頸。
?
識別程序的限制因素。常見的限制是數據依賴，像Fibonacci數列中的那樣。
研究其他可能的算法，這可能是用來設計并行應用程序最重要的方法。
?
6.3?問題分解
設計并行程序的第一步是將問題分解成離散的可以被分配到多任務中的工作塊。這就是任務分解。
分解并行任務中的可計算工作的兩個基本方式是：作用域分解和功能分解。
?
1）作用域分解：
???????在這個方法中，與問題相關的數據將會被分解。每個并行的任務只能使用部分數據。
?
?
?
?
有不同的方法可以分解數據：
?
?
2）功能分解：
???????在這種方式中，主要關注要被完成的計算而不是操作數據的計算。問題是根據當前一定要完成的任務劃分的。每個任務完成全部工作的一部分。
?
?
???????功能分解將問題很好的分解到不同的任務中去，例如：
A）生態系統模型
???????每個程序都要計算給定群體的總數目，每個群體的增長依賴它的鄰居。隨著時間的流逝，每個進程計算它自己的狀態，然后和鄰居交換總數信息。所有的進程在下個時間節點再重新計算自己的狀態。
?
??
?
B)信號處理
???????音頻信號數據集是通過四個不同的可計算濾波器傳遞的。每個濾波器都有自己獨立的進程。第一部分數據一定是先通過第一個濾波器傳輸。完成后，第二部分數據再通過第一個濾波器。第四部分數據通過了第一個濾波器后四個任務都開始運行。
?
?
?
C)氣候模型
???????模型中的每個組件都可以當作一個獨立的任務。箭頭代表計算過程中組件間的數據交換方向：大氣層模塊生成風速數據發送給大洋模塊，大洋模塊生產海洋水表溫度發送給大氣層模塊使用，如此往復。
?
???????通常聯合使用以上兩種問題分解方法。
?
6.4?通信
??????????誰需要通信？
???????任務之間是否需要通信取決于您要解決的問題。
?
l?????????不需要通信的情況：
???????1)實際上有些類型的問題可以將問題分解，并行執行時并不需要任務間共享數據。例如：假設一個圖像處理的程序在處理的圖像只有黑色，黑色的像素都反轉成黑色。圖像數據很容易就可以被分解到多個任務上，這些任務顯然可以獨立執行完成自己的那部分工作。
???????2)這種類型的問題稱為“使人尷尬的并行計算”，因為他們不是直截了當的并行程序。任務之間還是需要少許的通信。
l?????????需要通信的情況：
???????大多數并行應用程序沒有這么簡單，任務間需要彼此共享數據。例如，3D的熱擴散問題，其中一個任務的溫度計算要知道他周圍的任務的計算數據。周圍數據改變將直接影響此任務的數據。
?
??????????值得考慮的因素：
???????設計任務間通信的程序時需要考慮很多十分重要的因素。
?
1.?????????通信開銷：
任務間通信肯定是需要開銷的。
原本用于計算的機器時鐘周期和計算資源將被用于給數據打包并傳輸。
頻繁的任務間通信需要同步方法，同步使任務把時間花費在等待上而沒有工作。
通信傳輸的競爭可能會占用大量的帶寬，甚至影響性能。
2.?????????帶寬和延遲
延遲是從A點到B點發送數據需要花費的時間。通常是微秒級。
帶寬是每個時間單元需要通信的數據量。通常是Mb/s或者Gb/s級別。
如果發送很多小消息的話，延遲可能會占用絕大多數的通信資源。將小消息打包成大消息一次性傳遞通常更加高效，也會增加有效通信帶寬。
3.?????????通信的可見性
在消息傳遞模型中，通信過程是非常清楚的，對程序員是可見的、可以控制的。
在數據并行模型中，程序員不能確切的知道任務間的通信是如何實現的，特別是在分布式內存體系結構中。
4.?????????同步通信和異步通信
同步通信需要某種類型的共享數據任務間的“握手”協議。程序員可以將此過程很清楚的在程序中完成。
同步通信通常是指一項任務完成后等待與他要通信的任務，后者完成計算后才可以進行通信。
異步通信允許程序之間可以獨立的傳輸數據。例如：1號任務可以在準備好后發送消息給2號任務然后立即做其他的工作，2號任務接收數據到的時間不是特別重要。
異步通信通常是指不阻塞的通信，因為任務可以一邊通信一邊做其他任務。
異步通信最適合用于交叉計算問題。
5.?????????通信的范圍
在設計并行代碼階段，知道哪個任務需要彼此通信是至關重要的。下面兩個描述的范圍可以設計成同步的也可以設計成異步的。
點到點：這里包括兩個任務，一個作為數據的制造者/發送者，另一個作為接收者/讀數據者。
聚集：這里包括多個任務的數據共享問題，每個任務都是組中的成員。
?
?
?
6.?????????通信效率
程序員通常會根據影響通信性能的因素進行選擇。這里由于篇幅限制只能提到一部分。
應該使用哪種那個給定的模型？用消息傳遞模型為例，只有MPI實現在給定的硬件平臺上可能比別的實現方法要快。
應該使用哪種通信操作？正如前面提到的，異步通信操作能夠提升程序的整體性能。
網絡媒體：有些平臺可能會提供多個網絡來進行通信，那么問題是那個網絡是最好的呢？
7.?????????開銷和復雜性
?
?
最后，請注意這里提到的只是程序員要考慮的問題的一部分。
?
6.5?同步
l?????????障礙
·通常障礙會影響所有的任務
·每個任務完成自己的任務之后到達障礙區等待。
·當所有的任務都到達障礙點后所有的任務進行同步。
·執行到這里有不同的情況，通常需要做一串工作。其他的情況自動釋放任務繼續完成別的工作。
l?????????鎖和信號量
·可能包括任意數量的任務。
·這種方法可以串行訪問全局數據和代碼段。同時只可以有一個任務使用鎖變量或者信號量。
·第一個訪問臨界資源的任務設置鎖，然后就可以安全的訪問里面被保護的數據或代碼。
·其他的任務試圖操作臨界區，但是發現已經上鎖只能等到鎖的擁有者釋放鎖才可以操作。
·阻塞和非阻塞兩種方式
l?????????同步通信操作
·只涉及到執行通信操作的任務。
·當一個任務完成通信操作，需要某種調度方法來調度其他參與通信的任務。例如：當一個任務完成發送數據的操作他必須等待接受任務的確認信息，才可以說明發送成功。
·其余的在前面通信部分討論過。
?
6.6?數據依賴
??????????定義：
·當程序的執行順序影響程序的執行結果時，我們說程序間存在依賴。
·不同任務同時使用相同地址的存儲空間中的數據那么就存在數據依賴。
·依賴問題在并行編程中是極其重要的，也是限制并行機制的主要因素。
??????????例如：
·循環中的數據依賴：
| ? DO 500 J = MYSTART,MYEND ???A(J) = A(J-1) * 2.0 500 CONTINUE |
A(J-1)的值一定要在計算A(J)值之前計算，因此A(J)的值依賴A(J-1)的值。不能并行。
如果任務2計算A(J)，任務1計算A(J-1)，想要得到正確的A(J)的值必須要：
1）分布式內存體系結構中，任務2一定要在任務1計算完A(J-1)的值后才可以計算。
2）共享內存體系結構中，任務2一定要讀取任務1更新A(J-1)的值之后才可以計算。
?
·循環獨立數據依賴
| ? task 1????????task 2 ------????????------ ? X = 2?????????X = 4 ??.?????????????. ??.?????????????. Y = X**2??????Y = X**3 |
像前面的例子一樣，這個例子也是不能并行化的，Y值依賴于：
1）分布式內存體系結構——X的值在任務之間是否通信或者何時通信都存在一定的數據依賴。
2）共享內存體系結構——哪個任務最后將X保存。
?
·當設計并行程序的時候，識別所有的數據依賴是很重要的。并行化的主要目標可能是循環，所以識別循環中的依賴問題更為重要。
?
??????????如何處理數據依賴
·分布式內存體系結構——在同步點上需要通信數據。
·共享內存體系結構——在任務之間同步讀寫操作。
?
6.7?負載平衡
·負載平衡指的是使所有分布式的工作高效運行、是CPU可以保持較高的利用率較少的等待。也可以看作是將任務空閑時間最小化的方法。
·對于提升系統性能來說，負載平衡是十分重要的。例如，所有的任務都要在障礙處同步，最慢的任務將決定全局的時間開銷。
?
?
?
??????????如何獲得負載平衡：
·平分每個任務的工作量
1)對于數組或者矩陣操作，每個任務分配相似的工作量，任務間平衡的分配數據。
2)對于循環迭代每個迭代的工作量是相似的，給任務平均的分配迭代次數。
3)在異質的機器上性能特點各不相同，一定要用某種性能分析工具來測試負載平衡的性能，根據結果調節工作。
?
·動態工作分配
1）即使數據平均的分配到各個任務上去，還是會存在一定的負載平衡問題。
???????稀疏數組——有些任務需要些非零數據而其他任務的數據基本上都是零。
???????自適應網格——有些任務需要規劃自己的網絡，而其他的任務不需要。
???????N-體模擬——有一些小塊工作可能需要從原任務分離整合到其他任務中；這些占用小工作的進程比其他的進程需要更多的工作。
2）當進程完成任務的數量很難確定或者不可以預測的時候，使用調度線程池模型可能會有所幫助。當任務完成自己的工作后，它排隊去申請新的工作。
3）我們有必要設計算法去檢查和處理在程序中動態的發生的負載不平衡現象。
6.8?粒度
??????????計算通信比（譯者注釋：一個任務用在計算上的時間除以任務間同步通信所用的時間，比值大說明時間利用率高）
·在并行計算中，粒度是用來描述計算通信比的十分量化的方法。
·計算時間通常與同步事件通信的時間段不同。
??????????細粒度的并行
·通信處理時只能完成很少量的可計算工作。
·低的計算通信率
·促進負載平衡
·意味著高通信開銷，降低了性能提升的可能性。
·如果粒度太小很可能任務間的通信和同步所需要的花費時間比用在計算上的還長。
??????????粗粒度并行
·在每次通信同步之間完成相當多的計算任務。
·高計算通信率
·意味著更加可能進行性能提升。
·更難進行有效的負載平衡調度
??????????哪個更好？
·最高效的粒度是由算法和當前硬件平臺決定的。
·通常情況下，通信和同步的開銷很大程度上取決于執行速度，這樣使用粗粒度較好。
·細粒度并行機制可以減少負載不平衡所帶來的開銷。
?
6.9 I/O
??????????壞處
·I/O操作通常認為是限制并行化的因素。
·適用于所有平臺的并行的I/O系統目前為止尚不成熟。
·在所有任務都看到相同文件系統的環境中，寫操作可能導致文件寫覆蓋。
·文件服務器同時處理多線程讀請求的能力將會影響寫操作。
·I/O一定是通過網絡（NFS或者非本地文件系統）構建的，可能導致服務器性能瓶頸甚至文件服務器崩潰。
?
??????????優點
·并行文件系統有以下幾種：
1）GPFS：AIX（IBM）的通用的并行文件系統。
2）Lustre：Linux機群（SUN微系統）。
3）PVFS/PVFS2：Linux機群的虛擬并行文件系統（Clemson/Argonne/Ohio State/等）。
4）PanFS：?Linux機群的Panasas ActiveScale文件系統。
5）HP SFS：HP存儲工作可剪裁的文件系統。Lustre是HP的基于并行文件系統(Linux全局文件系統)的產品。
?
·并行I/O編程MPI接口規范從1996年開始發布了第二個版本MPI-2。現在也可以拿到生產商免費實現。
·選項：
1）如果你要訪問并行文件系統，你要好好研究一下。
2）規則1：盡量減少全局的I/O。
3）限定工作中的某些任務的I/O操作，然后為并行任務分配通信數據。例如：任務1讀取輸入文件，然后和其他任務通信所需要的數據。同樣，任務1從其他任務讀取所需的數據后再完成寫操作。
4）共享文件空間的分布式內存系統，在本地完成I/O操作則不共享文件空間。例如：每個處理器可能有可以使用的臨時文件空間。在自己本地操作通常要比在網絡上完成I/O操作更加高效。
5）為每個任務的輸入輸出文件創建唯一的文件名。
?
6.10?并行程序設計的限制和消耗
??????????阿姆達爾（Amdahl's）法則
·阿姆達爾法則指出加速比是由并行化代碼部分決定的。
| ?????????????????????1 ????speedup???=???-------- ???????????????????1??- P |
?
·如果沒有代碼被并行化，P=0那么加速比=1，沒有加速。
·如果所有的代碼都被并行化了，P=1，理論上加速比是無限的。
·如果50%的代碼并行化了，最大的加速比=2，意味著代碼比原來快了一倍
?
??
?
·引入處理器的數目完成并行操作的部分。關系描述模型如下：
| ???????????????????????1? ????speedup???=???------------ ????????????????????P???+??S ???????????????????--- ????????????????????N |
P是并行部分比例，N是處理器數目，S的串行比
?
·顯然并行加速比是有極限的：例如：
| ? ???????????????????????speedup ?????????????-------------------------------- ????N????????P = .50??????P = .90?????P = .99 ??-----??????-------??????-------?????------- ?????10?????????1.82?????????5.26????????9.17 ????100?????????1.98?????????9.17???????50.25???? ???1000?????????1.99?????????9.91???????90.99 ??10000?????????1.99?????????9.91???????99.02 ?100000?????????1.99?????????9.99???????99.90 ? |
?
·但是，確實有些問題可以通過增加問題的規模來提高性能。例如：
1）2D的網格計算??????????????85秒??????85%
2）串行部分????????????????15秒??????15%
我們通過加倍網絡的規格來增加問題的規模并將時間步長減半。結果應該是原來四倍的網格節點數目，兩倍數量的時間步長。計時結果如下：
1）2D網格計算???????????680秒?????97.84%
2）串行部分????????????????15秒??????2.16%
·這個問題通過增加并行時間比例比固定比例并行時間的問題可擴展性更強。（譯者注：將并行計算和串行計算的百分數代入前面公式可知加速比有所提高，證明增加問題規模提高并行比例確實可以提升性能。）
?
??????????復雜性
·通常，并行應用程序要比相對應的串行應用程序復雜得多，可能是在一個數量級上。不僅僅要考慮多個指令流在同時執行，而且它們中間還有多個數據流。
·在軟件開發周期的每一部分中，程序員因程序復雜而花費的時間是可以測量的。
???????1）設計
???????2）編碼
???????3）調試
???????4）較優
???????5）維護
·開發并行應用程序的時候特別是與人合作開發的時候，遵循標準的軟件開發實踐準則是必需的。
?
??????????可移植性
·由于MPI、POSIX、HPF、OpenMP等API的標準化，使得并行程序中的可移植性問題比前些年大大改善。
·所有串行程序的可移植性問題都歸因于將其并行化。例如，如果你使用生產商的加強的Fortran、C和C++時，可移植性將存在問題。
·盡管上訴幾個API存在標準，但是很多實現的細節卻是不同的，有時需要修改代碼才能實現可移植性。
·操作系統在代碼可移植性問題上扮演著重要的角色。
·硬件體系結構有很大差別也會影響可移植性。
?
??????????所需資源
·并行的首要目標是減少執行過程中的阻塞時間，但是為了達到這個目的，需要更多的CPU時間。例如，并行代碼在八個處理器的內核上運行1個小時實際上用了8個小時的CPU時間。
·并行程序比串行程序所需的內存數量要大得多，這是由于我們需要備份數據，為與并行相關的負載提供庫函數和子系統。
·小段的并行程序實際上在性能上要比相似的串行程序差。設置并行環境、任務創建、任務間的通信和終止等所需要的開銷占用了總開銷的絕大部分。
?
??????????可擴展性
·并行程序性能的可擴展性的能力取決于一些相關的因素。只是簡單的增加更多的機器很難提高整體性能。
·算法也是可擴展性固有的限制因素。從某種意義上來說，增加更多的資源可能會導致性能下降。很多并行的解決方案在某種程度上顯示出這個問題。
·硬件因素在可擴展性方面扮演著重要的角色。例如：
1）SMP機器上的內存和CPU總線帶寬
2）通信網絡帶寬
3）在特定的機器或機群中可以獲得的內存大小
4）處理器速度
?
·并行支持庫和子系統軟件限制與應用程序的可擴展性。
?
6.11?性能分析與調整
·相比串行程序來說，并行程序的調試、監視、分析并行程序的執行更加困難。
·現在可以獲得很多監視程序執行和程序分析的工具。
·有些非常有用，有些還跨平臺。
·起點：
1）LC的“軟件和計算支持工具”網頁在computing.llnl.gov/code/content/software_tools.php
2）關于“高性能工具和技術”的白皮書有點過時但是很可能十分有用，它提到了很多工具，還提到很多性能相關可給代碼開發者應用的話題。可以在這里找到
computing.llnl.gov/tutorials/performance_tools/HighPerformanceToolsTechnologiesLC.pdf.
3）性能分析工具教程Performance Analysis Tools Tutorial
·還有很多工作沒有完成，特別是可擴展性領域。
?
?
?
7?并行示例
7.1?數組程序
·這個例子是計算兩維數組元素，這里計算每個數組元素彼此互不影響。
·串行程序順序的每次計算一個元素。
·串行代碼可能是這樣的形式：
| do j = 1,n do i = 1,n ??a(i,j) = fcn(i,j) end do end do |
?
·元素的計算彼此獨立，這就是“令人尷尬的”并行狀態。
·這個問題可以密集的計算。
?
?
?
?
???????并行解決方案1
·數組元素是分散的，所以每個進程都擁有自己的一部分數組（子數組）。
·獨立的數組元素計算確保了不需要任務間的數據通信。
·用其他的標準來確定分配方案，例如：子數組劃分。最大緩存或內存利用率劃分。
·由于通過子數組劃分方法是比較滿意的，這樣就要根據編程語言選擇分配方案。
·將數組分配完后，每個任務都執行只和自己的數據通信執行自己的代碼。例如：用Fortran塊分配：
| do j = mystart, myend do i = 1,n ??a(i,j) = fcn(i,j) end do end do |
?
·注意：只有外層循環變量與串行的方案不同。
?
???????可能的解決方案
·用SPMD模型實現
·主線程初始化數組、發送信息給工作線程并接收計算返回結果。
·工作線程接受主線程分配任務的信息，完成自己要做的計算工作將結果發給主線程。
·使用Fortran存儲模式，完成數組的塊分配。
·偽代碼如下：紅色的部分與并行不同。
| ? 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 |
Example: MPI Program in C
Example: MPI Program in Fortran
?
???????并行解決方案2：線程池
·這里使用兩種線程：
1）主線程：
???????為工作線程維護線程池
???????在必要的時候分配任務給工作線程
???????收集工作線程的計算返回的結果集。
2）工作線程：
???????從主線程處獲取任務
???????完成計算
???????將結果發送回主線程
?
·工作線程在運行之前不知道要處理那部分數組，也不知道他們要計算多少任務。
·在運行時，自動的負載平衡：處理速度快的任務將會做更多的工作。
·偽代碼如下：紅色高亮的與并行中不同
| ? find out if I am MASTER or WORKER ? if I am MASTER ? ??do until no more jobs ????send to WORKER next job ????receive results from WORKER ??end do ? ??tell WORKER no more jobs ? else if I am WORKER ? ??do until no more jobs ????receive from MASTER next job ? ????calculate array element: a(i,j) = fcn(i,j) ? ????send results to MASTER ??end do ? endif |
?
??????????討論
·在上面線程池例子中，每個任務的工作室計算獨立的數組元素。這里的計算通信比是細粒度的。
·細粒度解決方案可以減少任務空閑時間但帶來了更多的通信開銷。
·更加理想的解決方案可能是給每個任務分配更多的工作來完成。恰到好處的任務量由問題決定。
?
?
7.2 PI?的計算
·有很多種PI值計算方法。考慮下面的近似PI值方法。
1）在正方形中話一個圓；
2）在正方形內隨機生成點；
3）確定即在正方形內又在圓形內點的數量；
4）在圓形內點的數量除以在正方形內點的數量，結果付給r；
5）PI約等于4r；
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 |
?
·注意：在執行這個循環中最花費時間的地方是執行循環。
·導致“令人尷尬的并行”的解決方案
???????高密度計算
???????最小化通信
???????最少化I/O操作
?
???????并行解決方案：
·并行策略：把循環分塊給任務集執行。
·近似的PI
1）每個任務執行一部分循環多次。
2）每個任務不需要從其他的任務獲取任何信息就可以完成自己工作。（沒有數據依賴）
3）使用SPMD模型。一個任務是主線程負責收集結果。
?
?
·偽代碼如下：紅色區是為并行而加
| 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 ? |
?
Example: MPI Program in C
Example: MPI Program in Fortran
?
?
7.3?簡單的加熱等式
?
·并行計算中的大多數問題都是需要進程間通信的。一些常見的問題還需要和鄰居任務通信。
·加熱等式描述的是溫度隨著時間而改變，初始化給出溫度分布和邊界條件值。
·我們用有限差分體系來解決在正方形區域上加熱等式量化的問題。
·邊界初始化溫度是零，中心溫度最高。
·外邊界溫度一直是零
·為了詳細闡述這個問題我們用了一個按時間分步的算法。兩維數組元素代表正方形中點的溫度。
·每一個元素的計算都依賴與鄰居元素的值。
?
?
·串行代碼如下
| 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
·用SPMD模型實施
·整個數組分組成子數組分配給所有的任務。每個任務擁有整個數組的一部分。
·裁定數據依賴
??????????????迭代元素屬于本身任務而獨立于其他任務。
??????????????邊界元素依賴鄰居任務數據，必須通信。
·主線程發送消息給工作線程，檢查分塊位置和結果集。
·工作線程執行計算，和必要的鄰居通信。
- Example: MPI Program in C
- Example: MPI Program in Fortran
?
?
?
?
?
·偽代碼如下：紅色是并行實現所需：
| find out if I am MASTER or WORKER ? if I am MASTER ??initialize array ??send each WORKER starting info and subarray ??do until all WORKERS converge ????gather from all WORKERS convergence data ????broadcast to all WORKERS convergence signal ??end do ??receive results from each WORKER else if I am WORKER ??receive from MASTER starting info and subarray ??do until solution converged ????update time ????send neighbors my border info ????receive from neighbors their border info ? ????update my portion of solution array ???? ????determine if my solution has converged ??????send MASTER convergence data ??????receive from MASTER convergence signal ??end do ??send MASTER results endif |
?
??????????并行解決方案2：重疊的通信和計算
·在前面的解決方案中，我們假定工作線程使用的是阻塞通信。阻塞通信是等待通信完成再執行下一條程序指令。
·在前面的解決方案中，鄰居任務通信邊界數據，每個進程更新自己那部分數組元素。?????
·使用非阻塞式通信通常會減少計算時間。非阻塞通信中通信的同時可以繼續工作。
·每個任務更新自己的內部數組，同時邊界數據在通信，通信完成再更新邊界值。
·偽代碼：如下
| find out if I am MASTER or WORKER ? if I am MASTER ??initialize array ??send each WORKER starting info and subarray ??? ??do until all WORKERS converge ????gather from all WORKERS convergence data ????broadcast to all WORKERS convergence signal ??end do ? ??receive results from each WORKER ? else if I am WORKER ??receive from MASTER starting info and subarray ? ??do until solution converged ????update time ??? ????non-blocking send neighbors my border info ????non-blocking receive neighbors border info ? ????update interior of my portion of solution array ????wait for non-blocking communication complete ????update border of my portion of solution array ??? ????determine if my solution has converged ??????send MASTER convergence data ??????receive from MASTER convergence signal ??end do ? ??send MASTER results ?????? endif ? |
?
?
7.4?一維的波等式
·在這個例子中，振幅沿著一個統一的震動的軌跡每隔指定的時間計算一次。
·計算包括：
1）在Y軸上的振幅
2）沿著X軸的位置索引i
3）沿著軌跡上的節點
4）在離散的時間點更新振幅
?
?
?
·這里要解的等式就是一維波等式。
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)))
這里C是常量
·注意：這里的振幅依賴前面的時間段（t,t-1）和鄰居點（i-1 , i+1）。數據依賴意味著并行解決方案要引入通信。
?
??????????一維波并行解決方案
·用SPMD模型實現
·整個振幅數組被分割成子數組分配給每個任務。每個任務擁有整個數組的一部分。
·負載平衡：所有點的計算需要相同的工作量，所以點數應該平均分配。
·塊分解將按照塊大小分解任務，使得任務數和線程個數相等。讓每個任務擁有大體上連續的數據點。
·只有數據邊界需要通信。塊大小越大所需的通信越少。
?
?
??????????偽代碼解決方案如下：
| 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 ? #Update values for each point along string #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
?????????例子: MPI Program in Fortran
?
?
8?參考和更多信息
作者: Blaise Barney,?利弗莫爾計算中心。
譯者：盧洋，同濟大學
?
由于譯者水平有限，翻譯中難免出現錯誤或遺漏歡迎大家指出。聯系方式luyang.leon@gmail.com
 - 反射)