這篇文章是對這段時間學(xué)習(xí)并行編程中的設(shè)計模式的一個總結(jié)。有不當(dāng)之處，希望得到大家的批評、指正。

首先，所謂“并行編程中的設(shè)計模式”（patterns in parallel programming）仍處于不斷的被發(fā)現(xiàn)、發(fā)掘的階段。當(dāng)前已經(jīng)有各路人馬對這一領(lǐng)域進行了研究，但遠遠沒有達到統(tǒng)一認識的高度。也沒有一套業(yè)界普遍認同的體系或者描述。這就造成了當(dāng)前這一領(lǐng)域的現(xiàn)狀：從事研究的人有不同的背景，他們各自總結(jié)出的模式種類不盡相同。即使是同一個模式，不同的團隊給它們?nèi)〉妹忠部赡懿灰粯?。不過這并不妨礙我們對“并行編程中的設(shè)計模式”進行一定的了解，并在實際的軟件開發(fā)工作中有所借鑒。

本文分兩部分，第一部分會簡單介紹這一領(lǐng)域的發(fā)展現(xiàn)狀：首先是進行研究的主要團體及其代表人物，然后介紹一下他們各自總結(jié)的模式體系，最后著重介紹一下加州大學(xué)伯克利分校的體系，A pattern language for parallel programming。第二部分則從該體系中挑出八個常用的設(shè)計模式作稍微詳細一點的介紹。每個設(shè)計模式都附有實際的應(yīng)用例子來幫助理解。我始終相信，通過例子的學(xué)習(xí)是最容易理解的一種方式。

1. 并行編程模式的發(fā)展現(xiàn)狀

在這一領(lǐng)域比較活躍的研究團體包括：

1. 加州大學(xué)伯克利分校。其代表人物是Kurt Keutzer教授，他曾是Synopsys公司的CTO。

2. Intel公司。代表人物是Tim Mattson，他是Intel的Principle Engineer和并行計算的布道師(evangelist)，是“Patterns for Parallel Programming”一書的作者。

3. 伊利諾伊大學(xué)。代表人物是Ralph Johnson教授。他是著名的設(shè)計模式“Gang of Four”中的一員。

4. 其他團體：包括微軟、麻省理工大學(xué)… 等等。

他們總結(jié)出的并行編程模式體系不盡相同，互相之間又有著緊密的聯(lián)系。主要有：

1. 加州大學(xué)伯克利分校的 A Pattern Language for Parallel Programming ver2.0

2. 伊利諾伊大學(xué)的 Parallel Programming Patterns

3. Tim Mattson 的著作 Patterns for Parallel Programming

這其中，我最為喜歡加州大學(xué)伯克利分校的體系:

伯克利的研究人員認為，寫出高質(zhì)量并行軟件的關(guān)鍵在于擁有好的軟件設(shè)計：從軟件的總體架構(gòu)，一直到系統(tǒng)的底層實現(xiàn)。將這些“好的設(shè)計”以一種系統(tǒng)的方式描述出來，并在各個不同的軟件項目當(dāng)中重用是解決構(gòu)建高質(zhì)量并行軟件問題的關(guān)鍵。這遠比各種具體的編程模型以及其支撐環(huán)境來得重要。因為擁有了一個好的設(shè)計之后，我們可以很容易的在各種開發(fā)平臺上編寫源代碼。

伯克利的模式體系包含了幾個不同的層次，上自軟件架構(gòu)，下至程序指令執(zhí)行的策略。最上面的兩塊分別是“架構(gòu)模式”(Structural patterns) 和“計算模式”(Computational patterns)。這兩塊并不單單包括并行軟件，也包括傳統(tǒng)的串行軟件模式。用我們常用來表達系統(tǒng)架構(gòu)的線框圖打比方，“架構(gòu)模式”指的就是那些箭頭和框框，它們表示的是程序總體的組織結(jié)構(gòu)，以及各部分之間是怎么交互的?！坝嬎隳Ｊ健敝傅氖强蚩蚶锩娴挠嬎泐愋?。例如，是基于圖的算法，還是有限狀態(tài)機，還是線性代數(shù)運算，等等。程序設(shè)計師通常需要在這兩大類模式之間翻來覆去的進行選擇。例如，我們可能先選擇了一種架構(gòu)模式，然后考慮使用某些合適的計算模式。但是選擇的計算模式可能更適合于在另一種架構(gòu)模式下運行，所以我們又得重新選擇一種架構(gòu)模式… …如此反復(fù)。上面這張圖在“架構(gòu)模式”和“計算模式”這兩大塊之間畫了兩個反復(fù)的箭頭，表達的就是這個意思。

這張圖下方的三大塊就專指并行編程當(dāng)中的模式了。它們包括“算法模式”(Algorithm strategy patterns)，“實現(xiàn)模式”(Implementation strategy patterns)和“并行執(zhí)行模式”(Parallel execution patterns)。顧名思義，“算法模式”指的是程序算法層面的模式。它們表達的是，為了解決某一類實際問題，怎么樣在較高的算法層面實現(xiàn)并行?！皩崿F(xiàn)模式”指的是我們在編寫源代碼的時候，利用什么樣的一些程序控制結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)并行。例如“parallel_for”，例如并行容器，等等。最后一個“并行執(zhí)行模式”指的是為了在計算機中有效的執(zhí)行一個并行程序，我們應(yīng)該采取哪些方法。這包括指令的執(zhí)行模式，例如是MIMD還是SIMD，也包括一些任務(wù)調(diào)度的策略。這三類模式是緊密聯(lián)系在一起的。例如，為了解決一個問題，我們可能使用“recursive splitting”的算法模式。而為了實現(xiàn)這個算法，我們很有可能使用“fork-join”的實現(xiàn)模式。在執(zhí)行層面，并行程序庫則通常會用“thread pool”的并行執(zhí)行模式來支持“fork-join”的運行。

由于我們在編寫程序時，“并行執(zhí)行模式”往往由編譯器或并行程序庫例如TBB的編寫人員考慮，我們并不需要關(guān)心；“實現(xiàn)模式”和我們選擇的具體并行運算平臺有關(guān)（OpenMP， TBB，MPI，…,，等等），不同的平臺有不同的API；“計算模式”則和具體的問題域聯(lián)接緊密。而且，看上去伯克利所總結(jié)的“計算模式”大部分和高性能計算有關(guān)，普通的應(yīng)用程序員并不熟悉。所以在本文，我將只挑選和并行計算密切相關(guān)的兩個“架構(gòu)模式”和六個常見的“算法模式”舉例進行說明。

2. 八個常用的并行編程模式

2.1 Agent and Repository

這是一個“架構(gòu)模式”，它針對這樣一類問題：我們有一組數(shù)據(jù)，它們會隨機的被一些不同的對象進行修改。解決這一類問題的方案是，創(chuàng)建一個集中管理的數(shù)據(jù)倉庫（data repository），然后定義一組自治的agent來操作這些數(shù)據(jù)，可能還有一個manager來對agent的操作進行協(xié)調(diào)，并保證數(shù)據(jù)倉庫中數(shù)據(jù)的一致性。我們常見的源代碼版本控制軟件例如Perforce就是實現(xiàn)這種架構(gòu)的典型代表：源代碼都存放在一個統(tǒng)一的服務(wù)器中（或是一組服務(wù)器中，但對client而言是透明的），不同的程序員們使用各自的客戶端對源代碼文件進行讀，寫，加，刪的操作。由Perforce負責(zé)保證源代碼數(shù)據(jù)的一致性。

2.2 Map Reduce

Map Reduce這個名詞原來是函數(shù)式編程里面的一個概念，但是自從Google于2004年推出同名的并行計算程序庫后，提到這個名詞大家大多想到的是Google的這個Framework。在這里，Map Reduce是一個“架構(gòu)模式”的名稱。當(dāng)然，我們這里的Map Reduce指的就是類似Google Map Reduce工作原理的一類模式。

那么什么是Map Reduce的模式呢？用較為簡單的語言描述，它指的是這樣一類問題的解決方案：我們可以分兩步來解決這類問題。第一步，使用一個串行的Mapper函數(shù)分別處理一組不同的數(shù)據(jù)，生成一個中間結(jié)果。第二步，將第一步的處理結(jié)果用一個Reducer函數(shù)進行處理（例如，歸并操作），生成最后的結(jié)果。從使用Google的Map Reduce程序庫的角度而言，作為應(yīng)用程序員，我們只需提供一組輸入數(shù)據(jù)，和兩個普通的串行函數(shù)（Mapper和Reducer），Google的Map Reduce框架就會接管一切，保證輸入數(shù)據(jù)有效的在一個分布式的計算機集群里面分配，然后Mapper和Reducer函數(shù)在其上有效的運行、處理，并最后匯總生成我們想要的處理結(jié)果。所有一切的細節(jié)，例如并行化、數(shù)據(jù)的分配、不同機器之間的計算誤差，通通被隱藏在程序庫內(nèi)。

那么Map Reduce到底是什么樣的一個過程呢？

我們講過，使用Map Reduce，程序員必須提供一組輸入數(shù)據(jù)，以及一個Mapper和一個Reducer函數(shù)。在這里，輸入數(shù)據(jù)必須是一個按(input_key,input_value)方式組織的列表。

mapper函數(shù)的任務(wù)是處理輸入列表中的某一個單元數(shù)據(jù)：mapper(input_key,input_value)，并產(chǎn)生如下輸出結(jié)果：

接下來，把對所有單元數(shù)據(jù)的處理結(jié)果按照intermediate_key歸類：同樣的intermediate_key放在一起，它們的intermediate_value簡單的串接起來，得到：

Reducer函數(shù)的任務(wù)是對上述的中間結(jié)果進行處理：reducer(intermediate_key, intermediate_value_list)，并產(chǎn)生如下最終輸出結(jié)果：

我們會舉兩個例子說明這一過程。第一個例子是一個簡單的統(tǒng)計單詞出現(xiàn)次數(shù)的小程序。第二個例子是Google曾經(jīng)怎樣使用Map Reduce FrameWork來計算Page Rank。

第一個例子，假設(shè)我們要寫一個小程序，來統(tǒng)計在幾篇不同文章里所有出現(xiàn)過的單詞各自總共出現(xiàn)的次數(shù)。我們應(yīng)該怎么做呢？下面描述的利用Map Reduce的方法肯定不是大多數(shù)程序員第一感會想到的方法。但這種方法非常好的揭示了Map Reduce的基本思想。并且，這種方法很容易被擴展到處理上千萬甚至是上億的文件數(shù)據(jù)，并且能夠在一個分布的計算機集群里面運行。這可不是傳統(tǒng)的方法能夠輕易做到的。

具體而言，假設(shè)我們有如下三個文本文件，a.txt, b.txt和c.txt：

對于輸入數(shù)據(jù)而言，input_key就是文件名，input_value就是一個大的string，包含的是文件內(nèi)容。所以我們的輸入數(shù)據(jù)看上去會是這樣的：

我們會寫一個簡單的串行的mapper(fileName, fileContent)函數(shù)。這個函數(shù)做的事情很簡單，讀入一個文本文件，把每一個遇到的單詞當(dāng)作一個新的intermediate_key，并賦其intermediate_value為1。將mapper函數(shù)處理文件a，我們會得到如下結(jié)果：

將所有三個文件的處理結(jié)果放在一起，我們得到：

然后將中間結(jié)果按intermediate_key歸類：

最后，由reducer(intermediate_key, intermediate_value_list)對中間結(jié)果進行處理。它做的事也很簡單，僅僅是把某intermediate_key對應(yīng)的所有intermediate_value相加。我們于是得到最終結(jié)果:

第二個例子，怎樣使用Map Reduce計算PageRank。什么是PageRank？可能大家都有所了解，這是Google用來量度一個網(wǎng)頁的重要性的值。簡單而言，有越多的其它網(wǎng)頁鏈接到這個網(wǎng)頁，這個網(wǎng)頁的PageRank越高。鏈接到這個網(wǎng)頁的網(wǎng)頁PageRank越高，這個網(wǎng)頁的PageRank也越高。假設(shè)我們一共有n個網(wǎng)頁0, 1, …, n-1。對第j個網(wǎng)頁我們給它賦一個PageRank值q_j。所有的q_j組合起來成為一個向量q = (q₀,q₁, …q_n-1)。這個向量滿足概率分布。即q_j的值都在0和1之間，并且所有的q_j加起來等于1。q_j越大，網(wǎng)頁的重要性越高。那么q是怎么計算出來的呢？答案是使用迭代的方法：

我們從一個初始的PageRank向量分布P開始，乘以一個n*n的矩陣M，得到一個新的PageRank向量。把新的PageRank向量繼續(xù)乘以M得到下一步的PageRank… … 如此迭代有限步后，PageRank向量的值會趨于收斂，于是我們得到最終的PageRank。

這里需要回答兩個問題：1. 如何確定初始的PageRank，即迭代的起點？答案是任意選擇一個概率分布就可以，無論你選擇什么初始值，都不影響其收斂到最終的結(jié)果。我們通常使用均勻概率分布，即。2. 如何定義M？這個問題稍顯復(fù)雜，有興趣的讀者可以參見Michael Nielsen 的博文Using MapReduce to compute PageRank了解更詳細的內(nèi)容。在這里，我們將其簡化的定義為一個描述網(wǎng)頁間互相鏈接結(jié)構(gòu)的超大矩陣。假設(shè)網(wǎng)絡(luò)里有n個網(wǎng)頁，那么我們這個矩陣就是一個n*n的方陣。矩陣的每一列代表一個網(wǎng)頁對外的超鏈接情況。例如，我們定義#(j)為第j個網(wǎng)頁對外的所有超鏈接的數(shù)量。那么對于矩陣M的第j列而言，如果網(wǎng)頁j對網(wǎng)頁k沒有超鏈接，那么第k行元素M_kj=0，否則M_kj=1/#(j)。這里隱含的意思是當(dāng)一個讀者在瀏覽網(wǎng)頁j時，有1/#(j)的可能性跳轉(zhuǎn)到網(wǎng)頁k。

那么如何使用Map Reduce來計算PageRank呢？雖然整個迭代的過程必須是串行的，迭代的每一步我們還是可以用Map Reduce來并行的計算的。這里也必須并行的計算因為這個矩陣和向量的規(guī)模是超大的（想象一下整個互聯(lián)網(wǎng)的網(wǎng)頁數(shù)量）。使用Map Reduce來計算迭代的一步實際上是用Map Reduce來計算矩陣和向量的乘法。假設(shè)我們要計算如下一個方陣和向量的乘法。其實質(zhì)是將第i個向量元素的值p_i乘以矩陣第i列的每一元素，然后放在矩陣元素原來的位置。最后，把矩陣第i行的所有元素相加，得到結(jié)果向量的第i個元素的值。

類似的，我們可以得到用MapReduce計算PageRank的方法：

第一步，輸入的(input_key, input_value)。input_key是某個網(wǎng)頁的編號，如j。input_value是一個列表，元素值是M矩陣的第j列元素，最后再加上一個p_j，就是當(dāng)前網(wǎng)頁j的PageRank值。

第二步，Map。Mapper(input_key, input_value)所做的事情很簡單，就是把p_j乘以列表元素的每一個值，然后輸出一組(intermediate_key, intermediate_value)。intermediate_key就是矩陣的行號，k。intermediate_value就是p_j列表元素的值，即p_j乘以矩陣第k行第j列的元素的值。

第三步，匯總。把所有intermediate_key相同的中間結(jié)果放到一起。即是把第k行所有的intermediate_value放在一個列表intermediate_value_list內(nèi)。

第四步，Reduce。Reducer(intermediate_key, intermediate_value_list)做的事也很簡單，就是把intermediate_value_list內(nèi)所有的值相加。最后形成的(output_key, output_value)就是結(jié)果向量第k行的元素值。

以上就是利用Map Reduce計算PageRank的簡略過程。這個過程相當(dāng)粗略和不精確，只是為了揭示Map Reduce的工作過程和Google曾經(jīng)用來計算PageRank的大致方法。認真的讀者應(yīng)該查閱其它更嚴謹?shù)闹鳌?/p>

最后，和上述計算矩陣和向量乘法的例子相似，Map Reduce也可以用來計算兩個向量的點乘。具體怎么做留給讀者自己去思考，一個提示是我們所有的intermediate_key都是相同的，可以取同一個值例如1。

2.3 Data Parallelism

這是一個“算法模式”。事實上，把Data Parallelism和下節(jié)將要提到的Task Parallelism都稱之為一種“算法模式”我覺得有過于籠統(tǒng)之嫌。到最后，哪一種并行算法不是被分解為并行執(zhí)行的task呢（task parallelism）？ 而并行執(zhí)行的task不都是處理著各自的那份數(shù)據(jù)嗎（data parallelism）？所以如果硬要把Data Parallelism和Task Parallelism稱為兩種算法模式，我只能說它們的地位要高于其它的算法模式。它們是其它算法模式的基礎(chǔ)。只不過對于有些問題而言，比較明顯的我們可以把它看成是Data Parallelism的或是Task Parallelism的。也許Data Parallelism模式和Task Parallelism模式特指的就是這類比較明顯的問題。

那么什么是Data Parallelism? 顧名思義，就是這類問題可以表達為同樣的一組操作被施加在不同的相互獨立的數(shù)據(jù)上。

一個比較典型的例子就是計算機圖形學(xué)里面的Ray tracing算法。Ray tracing算法可以大致描述為從一個虛擬相機的光心射出一條射線，透過屏幕的某個像素點，投射在要渲染的幾何模型上。找到射線和物體的交點后，再根據(jù)該點的材料屬性、光照條件等，算出該像素點的顏色值，賦給屏幕上的像素點。由于物體的幾何模型很多個小的三角面片表示，算法的第一步就是要求出射線與哪個三角面片有交點。射線與各個單獨的三角面片求交顯然是相互獨立的，所以這可以看做是Data Parallelism的例子。

2.4 Task Parallelism

Task Parallelism的算法模式可以表述為，一組互相獨立的Task各自處理自己的數(shù)據(jù)。和Data Parallelism不同，這里關(guān)注的重點不是數(shù)據(jù)的劃分，而是Task的劃分。

如前所述，Task Parallelism和Data Parallelism是密不可分的。互相獨立的Task肯定也是運行在互相獨立的數(shù)據(jù)上。這主要是看我們以什么樣的視角去看問題。例如，上一節(jié)RayTracing的例子中，我們也可以把射線和一個獨立的三角面片求交看作是一個獨立的Task。這樣就也可以當(dāng)它做是Task Parallelism的例子。然而，咬文嚼字的去區(qū)分到底是Task Parallelism還是Data Parallelism不是我們的目的，我們關(guān)注的應(yīng)該是問題本身。對于某一個具體問題，從Data Parallelism出發(fā)考慮方便還是從Task Parallelism出發(fā)考慮方便，完全取決于問題本身的應(yīng)用場景以及設(shè)計人員自身的經(jīng)驗、背景。事實上，很多時候，不管你是從Task Parallelism出發(fā)還是從Data Parallelism出發(fā)，經(jīng)過不斷的優(yōu)化，最終的解決方案可能是趨同的。

下面一個矩陣乘法的例子很好的說明了這個問題。我們都知道矩陣乘法的定義：假如有n行k列的矩陣A乘以k行m列的矩陣B，那么我們可以得到一個n行m列的的矩陣C。矩陣C的第n行第m列的元素的值等于矩陣A的第n行和矩陣B的第m列的點乘。

從Task Parallelism的角度出發(fā)，我們可能把計算C的每一個元素當(dāng)做一個獨立的Task。接下來，為了提高CPU的緩存利用率，我們可能把鄰近幾個單元格的計算合并成一個大一點的Task。從Data Parallelism的角度出發(fā)，我們可能一開始把C按行分成不同的塊。為了探索到底怎樣的劃分更加有效率，我們可能調(diào)整劃分的方式和大小，最后，可能發(fā)現(xiàn)，最有效率的做法是把A，B，C都分成幾個不同的小塊，進行分塊矩陣的乘法?？梢钥吹?，這個結(jié)果實際上和從Task Parallelism出發(fā)考慮的方案是殊途同歸的。

2.5 Recursive Splitting

Recursive Splitting指的是這樣一種算法模式：為了解決一個大問題，把它分解為可以獨立求解的小問題。分解出來的小問題，可能又可以進一步分解為更小的問題。把問題分解到足夠小的規(guī)模后，就可以直接求解了。最后，把各個小問題的解合并為原始的大問題的解。這實際上是我們傳統(tǒng)的串行算法領(lǐng)域里面也有的“divide and conquer”的思想。

舉兩個例子。第一個是傳統(tǒng)的歸并排序。例如，要排序下面的8個元素的數(shù)組，我們不管三七二十一先把它一分為二。排序4個元素的數(shù)組還是顯得太復(fù)雜了，于是又一分為二?，F(xiàn)在，排序2個元素的數(shù)組很簡單，按照大小交換順序就行。最后，把排好序的數(shù)組按序依次組合起來，就得到我們最終的輸出結(jié)果。

第二個例子稍微有趣一點，是一個如何用程序解“數(shù)獨”游戲的例子?！皵?shù)獨”就是在一個9*9的大九宮格內(nèi)有9個3*3的小九宮格。里面有些格子已經(jīng)填入了數(shù)字，玩家必須在剩下的空格里也填入1到9的數(shù)字，使每個數(shù)字在每行、每列以及每個小九宮格內(nèi)只出現(xiàn)一次。

這里作為舉例說明，我們考慮一個簡單一點的情況：在一個4*4的格子里填入1~4的數(shù)字，使其在每行、每列以及每個2*2的格子里只出現(xiàn)一次。

解“數(shù)獨”游戲的算法可以有很多種。如果是人來解，大概會按照上圖的次序依次填入1,2,3到相應(yīng)的格子當(dāng)中。每填入一個新數(shù)字，都會重新按規(guī)則評估周圍的空格，看能否按現(xiàn)有情況再填入一些數(shù)字。這個方法當(dāng)然沒錯，不過看上去不太容易并行化。下面介紹一個按照“recursive splitting”的方法可以很容易做到并行化的解法。

1） 首先，將二維的數(shù)獨格子展開成一個一維的數(shù)組。已經(jīng)有數(shù)字的地方是原來的數(shù)字，空格子的地方填上“0”。

2） 接下來，從前到后對數(shù)組進行掃描。第一格是“3”，已經(jīng)有數(shù)字了，跳過。移動搜索指針到下一格。

3） 第二格是“0”，意味著我們需要填入一個新的數(shù)字。這個新的數(shù)字有4種可能性：1， 2， 3， 4。所以創(chuàng)建4個新的搜索分支：

4） 接下來根據(jù)現(xiàn)有的數(shù)字信息檢查各個搜索分支。明顯，第三和第四個搜索分支是非法的。因為我們在同一行中已經(jīng)有了數(shù)字“3”和“4”。所以忽略這兩個分支。第一和第二條分支用現(xiàn)有的數(shù)字檢查不出沖突，所以繼續(xù)從這兩個分支各派生出4條新的分支進行搜索… …

這個思路像極了我們之前的歸并排序的例子，都是在算法運行的過程中不斷產(chǎn)生出新的任務(wù)。所以實際上這也是一個“Task Parallelism”的例子。

2.6 Pipeline

“Pipeline”也是一種比較常見的算法模式。通常，我們都會用汽車裝配中的流水線、CPU中指令執(zhí)行的流水線來類比的說明這一模式。它說的是我們會對一批數(shù)據(jù)進行有序、分階段的處理，前一階段處理的輸出作為下一階段處理的輸入。每一個階段永遠只重復(fù)自己這一階段的任務(wù)，不停的接受新的數(shù)據(jù)進行處理。用一個軟件上的例子打比方，我們要打開一批文本文件，將里面每一個單詞的字母全部改成大寫，然后寫到一批新的文件里面去，就可以創(chuàng)建一條有3個stage的流水線：讀文件，改大寫，寫文件。

“Pipeline”模式的概念看上去很容易理解，可是也不是每一個人都能一下子理解的那么透徹的。例如有這樣一個問題：我們有一個for循環(huán)，循環(huán)體是一條有3個stage的pipeline，每個stage的運行時間分別是10， 40， 和10個CPU的時鐘間隔。請問這個for循環(huán)執(zhí)行N次大概需要多長時間（N是一個很大的數(shù)）？

A. 60*N

B. 10*N

C. 60

D. 40*N

請仔細思考并選擇一個答案。:-)

答案是40*N。流水線總的執(zhí)行時間是由它最慢的一個stage決定的。原因請見下圖。

2.7 Geometric decomposition

接下來這兩個算法模式看上去都顯得比較特殊化，只針對某些特定的應(yīng)用類型?！癎eometric decomposition”說的是對于一些線性的數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組），我們可以把數(shù)據(jù)切分成幾個連續(xù)的子集。因為這種切分模式看上去和把一塊幾何區(qū)域切分成連續(xù)的幾塊很類似，我們就把它叫做”Geometric decomposition”。

最常用的例子是分塊矩陣的乘法。例如，為了計算兩個矩陣A，B的乘法。我們可以把他們切分成各自可以相乘的小塊。

結(jié)果矩陣當(dāng)然也是分塊的：

結(jié)果矩陣每一分塊的計算按照如下公式進行：

例如：

最終的結(jié)果就是：

下面這幅圖顯示了兩個4*4的分塊矩陣A，B進行乘法時，計算結(jié)果矩陣C的某一分塊時，需要依次訪問的A，B矩陣的分塊。黑色矩陣分塊代表要計算的C的分塊，行方向上的灰色矩陣代表要訪問的矩陣A的分塊，列方向上的灰色分塊代表要訪問的矩陣B的分塊。

2.8 Non-work-efficient Parallelism

這個模式的名字取得很怪異，也有其他人把它叫做“Recursive Data”。不過相比而言，還是這個名字更為貼切。它指的是這一類模式：有些問題的處理使用傳統(tǒng)的方法，必須依賴于對數(shù)據(jù)進行有序的訪問，例如深度優(yōu)先搜索，這樣就很難并行化。但是假如我們愿意花費一些額外的計算量，我們就能夠采用并行的方法來解決這個問題。

常用的一個例子是如下的“尋找根節(jié)點”的問題。假設(shè)我們有一個森林，里面每一個節(jié)點都只記錄了自己的前向節(jié)點，根節(jié)點的前向節(jié)點就是它自己。我們要給每一個節(jié)點找到它的根節(jié)點。用傳統(tǒng)的方法，我們只能從當(dāng)前節(jié)點出發(fā)，依次查找它的前向節(jié)點，直到前向節(jié)點是它自身。這種算法對每一個節(jié)點的時間復(fù)雜度是O(N)。總的時間復(fù)雜度是N*O(N)。

如果我們能換一種思路來解這個問題就可以將其并行化了。我們可以給每一個節(jié)點定義一個successor（后繼結(jié)點），successor的初始值都是其前向節(jié)點。然后我們可以同步的更新每一個節(jié)點的successor，令其等于“successor的successor”，直到successor的值不再變化為止。這樣對于上圖的例子，最快兩次更新，我們就可以找到每個節(jié)點的根節(jié)點了。這種方法能同時找到所有節(jié)點的根節(jié)點，總的時間復(fù)雜度是N*log (N)。

3. 后記

如前所述，“并行編程中的設(shè)計模式”是一個仍在不斷變化、發(fā)展的領(lǐng)域。這篇博文簡要介紹了這一領(lǐng)域當(dāng)前的發(fā)展現(xiàn)狀，并選取八個常用的模式進行了介紹。我涉足并行編程領(lǐng)域不久，很多理解也并不深入。所以文章的缺點錯誤在所難免，真誠希望能得到大家的批評指正。

4. 參考文獻

本文的寫作參考了如下資源，可以作為進一步閱讀的材料：

· UC Berkeley, A Pattern Language for Parallel Programming

· Eun-Gyu Kim, Parallel Programming Patterns

· Jim Browne, Design Patterns for Parallel Computation

· Tim Mattson, Patterns for Parallel Programming

· Michael Nielsen, Using Map Reduce to compute PageRank

· Aater Suleman, Parallel Programming: Do you know Pipeline Parallelism?