這篇文章是對(duì)這段時(shí)間學(xué)習(xí)并行編程中的設(shè)計(jì)模式的一個(gè)總結(jié)。有不當(dāng)之處，希望得到大家的批評(píng)、指正。
首先，所謂“并行編程中的設(shè)計(jì)模式”（patterns in parallel programming）仍處于不斷的被發(fā)現(xiàn)、發(fā)掘的階段。當(dāng)前已經(jīng)有各路人馬對(duì)這一領(lǐng)域進(jìn)行了研究，但遠(yuǎn)遠(yuǎn)沒(méi)有達(dá)到統(tǒng)一認(rèn)識(shí)的高度。也沒(méi)有一套業(yè)界普遍認(rèn)同的體系或者描述。這就造成了當(dāng)前這一領(lǐng)域的現(xiàn)狀：從事研究的人有不同的背景，他們各自總結(jié)出的模式種類(lèi)不盡相同。即使是同一個(gè)模式，不同的團(tuán)隊(duì)給它們?nèi)〉妹忠部赡懿灰粯?。不過(guò)這并不妨礙我們對(duì)“并行編程中的設(shè)計(jì)模式”進(jìn)行一定的了解，并在實(shí)際的軟件開(kāi)發(fā)工作中有所借鑒。
本文分兩部分，第一部分會(huì)簡(jiǎn)單介紹這一領(lǐng)域的發(fā)展現(xiàn)狀：首先是進(jìn)行研究的主要團(tuán)體及其代表人物，然后介紹一下他們各自總結(jié)的模式體系，最后著重介紹一下加州大學(xué)伯克利分校的體系，A pattern language for parallel programming。第二部分則從該體系中挑出八個(gè)常用的設(shè)計(jì)模式作稍微詳細(xì)一點(diǎn)的介紹。每個(gè)設(shè)計(jì)模式都附有實(shí)際的應(yīng)用例子來(lái)幫助理解。我始終相信，通過(guò)例子的學(xué)習(xí)是最容易理解的一種方式。
在這一領(lǐng)域比較活躍的研究團(tuán)體包括：
1. 加州大學(xué)伯克利分校。其代表人物是Kurt Keutzer教授，他曾是Synopsys公司的CTO。
2. Intel公司。代表人物是Tim Mattson，他是Intel的Principle Engineer和并行計(jì)算的布道師(evangelist)，是“Patterns for Parallel Programming”一書(shū)的作者。
3. 伊利諾伊大學(xué)。代表人物是Ralph Johnson教授。他是著名的設(shè)計(jì)模式“Gang of Four”中的一員。
4. 其他團(tuán)體：包括微軟、麻省理工大學(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é)伯克利分校的體系:
伯克利的研究人員認(rèn)為，寫(xiě)出高質(zhì)量并行軟件的關(guān)鍵在于擁有好的軟件設(shè)計(jì)：從軟件的總體架構(gòu)，一直到系統(tǒng)的底層實(shí)現(xiàn)。將這些“好的設(shè)計(jì)”以一種系統(tǒng)的方式描述出來(lái)，并在各個(gè)不同的軟件項(xiàng)目當(dāng)中重用是解決構(gòu)建高質(zhì)量并行軟件問(wèn)題的關(guān)鍵。這遠(yuǎn)比各種具體的編程模型以及其支撐環(huán)境來(lái)得重要。因?yàn)閾碛辛艘粋€(gè)好的設(shè)計(jì)之后，我們可以很容易的在各種開(kāi)發(fā)平臺(tái)上編寫(xiě)源代碼。
伯克利的模式體系包含了幾個(gè)不同的層次，上自軟件架構(gòu)，下至程序指令執(zhí)行的策略。最上面的兩塊分別是“架構(gòu)模式”(Structural patterns) 和“計(jì)算模式”(Computational patterns)。這兩塊并不單單包括并行軟件，也包括傳統(tǒng)的串行軟件模式。用我們常用來(lái)表達(dá)系統(tǒng)架構(gòu)的線(xiàn)框圖打比方，“架構(gòu)模式”指的就是那些箭頭和框框，它們表示的是程序總體的組織結(jié)構(gòu)，以及各部分之間是怎么交互的?！坝?jì)算模式”指的是框框里面的計(jì)算類(lèi)型。例如，是基于圖的算法，還是有限狀態(tài)機(jī)，還是線(xiàn)性代數(shù)運(yùn)算，等等。程序設(shè)計(jì)師通常需要在這兩大類(lèi)模式之間翻來(lái)覆去的進(jìn)行選擇。例如，我們可能先選擇了一種架構(gòu)模式，然后考慮使用某些合適的計(jì)算模式。但是選擇的計(jì)算模式可能更適合于在另一種架構(gòu)模式下運(yùn)行，所以我們又得重新選擇一種架構(gòu)模式… …如此反復(fù)。上面這張圖在“架構(gòu)模式”和“計(jì)算模式”這兩大塊之間畫(huà)了兩個(gè)反復(fù)的箭頭，表達(dá)的就是這個(gè)意思。
這張圖下方的三大塊就專(zhuān)指并行編程當(dāng)中的模式了。它們包括“算法模式”(Algorithm strategy patterns)，“實(shí)現(xiàn)模式”(Implementation strategy patterns)和“并行執(zhí)行模式”(Parallel execution patterns)。顧名思義，“算法模式”指的是程序算法層面的模式。它們表達(dá)的是，為了解決某一類(lèi)實(shí)際問(wèn)題，怎么樣在較高的算法層面實(shí)現(xiàn)并行?！皩?shí)現(xiàn)模式”指的是我們?cè)诰帉?xiě)源代碼的時(shí)候，利用什么樣的一些程序控制結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)并行。例如“parallel_for”，例如并行容器，等等。最后一個(gè)“并行執(zhí)行模式”指的是為了在計(jì)算機(jī)中有效的執(zhí)行一個(gè)并行程序，我們應(yīng)該采取哪些方法。這包括指令的執(zhí)行模式，例如是MIMD還是SIMD，也包括一些任務(wù)調(diào)度的策略。這三類(lèi)模式是緊密聯(lián)系在一起的。例如，為了解決一個(gè)問(wèn)題，我們可能使用“recursive splitting”的算法模式。而為了實(shí)現(xiàn)這個(gè)算法，我們很有可能使用“fork-join”的實(shí)現(xiàn)模式。在執(zhí)行層面，并行程序庫(kù)則通常會(huì)用“thread pool”的并行執(zhí)行模式來(lái)支持“fork-join”的運(yùn)行。
由于我們?cè)诰帉?xiě)程序時(shí)，“并行執(zhí)行模式”往往由編譯器或并行程序庫(kù)例如TBB的編寫(xiě)人員考慮，我們并不需要關(guān)心；“實(shí)現(xiàn)模式”和我們選擇的具體并行運(yùn)算平臺(tái)有關(guān)（OpenMP， TBB，MPI，…,，等等），不同的平臺(tái)有不同的API；“計(jì)算模式”則和具體的問(wèn)題域聯(lián)接緊密。而且，看上去伯克利所總結(jié)的“計(jì)算模式”大部分和高性能計(jì)算有關(guān)，普通的應(yīng)用程序員并不熟悉。所以在本文，我將只挑選和并行計(jì)算密切相關(guān)的兩個(gè)“架構(gòu)模式”和六個(gè)常見(jiàn)的“算法模式”舉例進(jìn)行說(shuō)明。
這是一個(gè)“架構(gòu)模式”，它針對(duì)這樣一類(lèi)問(wèn)題：我們有一組數(shù)據(jù)，它們會(huì)隨機(jī)的被一些不同的對(duì)象進(jìn)行修改。解決這一類(lèi)問(wèn)題的方案是，創(chuàng)建一個(gè)集中管理的數(shù)據(jù)倉(cāng)庫(kù)（data repository），然后定義一組自治的agent來(lái)操作這些數(shù)據(jù)，可能還有一個(gè)manager來(lái)對(duì)agent的操作進(jìn)行協(xié)調(diào)，并保證數(shù)據(jù)倉(cāng)庫(kù)中數(shù)據(jù)的一致性。我們常見(jiàn)的源代碼版本控制軟件例如Perforce就是實(shí)現(xiàn)這種架構(gòu)的典型代表：源代碼都存放在一個(gè)統(tǒng)一的服務(wù)器中（或是一組服務(wù)器中，但對(duì)client而言是透明的），不同的程序員們使用各自的客戶(hù)端對(duì)源代碼文件進(jìn)行讀，寫(xiě)，加，刪的操作。由Perforce負(fù)責(zé)保證源代碼數(shù)據(jù)的一致性。
Map Reduce這個(gè)名詞原來(lái)是函數(shù)式編程里面的一個(gè)概念，但是自從Google于2004年推出同名的并行計(jì)算程序庫(kù)后，提到這個(gè)名詞大家大多想到的是Google的這個(gè)Framework。在這里，Map Reduce是一個(gè)“架構(gòu)模式”的名稱(chēng)。當(dāng)然，我們這里的Map Reduce指的就是類(lèi)似Google Map Reduce工作原理的一類(lèi)模式。
那么什么是Map Reduce的模式呢？用較為簡(jiǎn)單的語(yǔ)言描述，它指的是這樣一類(lèi)問(wèn)題的解決方案：我們可以分兩步來(lái)解決這類(lèi)問(wèn)題。第一步，使用一個(gè)串行的Mapper函數(shù)分別處理一組不同的數(shù)據(jù)，生成一個(gè)中間結(jié)果。第二步，將第一步的處理結(jié)果用一個(gè)Reducer函數(shù)進(jìn)行處理（例如，歸并操作），生成最后的結(jié)果。從使用Google的Map Reduce程序庫(kù)的角度而言，作為應(yīng)用程序員，我們只需提供一組輸入數(shù)據(jù)，和兩個(gè)普通的串行函數(shù)（Mapper和Reducer），Google的Map Reduce框架就會(huì)接管一切，保證輸入數(shù)據(jù)有效的在一個(gè)分布式的計(jì)算機(jī)集群里面分配，然后Mapper和Reducer函數(shù)在其上有效的運(yùn)行、處理，并最后匯總生成我們想要的處理結(jié)果。所有一切的細(xì)節(jié)，例如并行化、數(shù)據(jù)的分配、不同機(jī)器之間的計(jì)算誤差，通通被隱藏在程序庫(kù)內(nèi)。
那么Map Reduce到底是什么樣的一個(gè)過(guò)程呢？
我們講過(guò)，使用Map Reduce，程序員必須提供一組輸入數(shù)據(jù)，以及一個(gè)Mapper和一個(gè)Reducer函數(shù)。在這里，輸入數(shù)據(jù)必須是一個(gè)按(input_key,input_value)方式組織的列表。
mapper函數(shù)的任務(wù)是處理輸入列表中的某一個(gè)單元數(shù)據(jù)：mapper(input_key,input_value)，并產(chǎn)生如下輸出結(jié)果：
接下來(lái)，把對(duì)所有單元數(shù)據(jù)的處理結(jié)果按照intermediate_key歸類(lèi)：同樣的intermediate_key放在一起，它們的intermediate_value簡(jiǎn)單的串接起來(lái)，得到：
Reducer函數(shù)的任務(wù)是對(duì)上述的中間結(jié)果進(jìn)行處理：reducer(intermediate_key, intermediate_value_list)，并產(chǎn)生如下最終輸出結(jié)果：
我們會(huì)舉兩個(gè)例子說(shuō)明這一過(guò)程。第一個(gè)例子是一個(gè)簡(jiǎn)單的統(tǒng)計(jì)單詞出現(xiàn)次數(shù)的小程序。第二個(gè)例子是Google曾經(jīng)怎樣使用Map Reduce FrameWork來(lái)計(jì)算Page Rank。
第一個(gè)例子，假設(shè)我們要寫(xiě)一個(gè)小程序，來(lái)統(tǒng)計(jì)在幾篇不同文章里所有出現(xiàn)過(guò)的單詞各自總共出現(xiàn)的次數(shù)。我們應(yīng)該怎么做呢？下面描述的利用Map Reduce的方法肯定不是大多數(shù)程序員第一感會(huì)想到的方法。但這種方法非常好的揭示了Map Reduce的基本思想。并且，這種方法很容易被擴(kuò)展到處理上千萬(wàn)甚至是上億的文件數(shù)據(jù)，并且能夠在一個(gè)分布的計(jì)算機(jī)集群里面運(yùn)行。這可不是傳統(tǒng)的方法能夠輕易做到的。
具體而言，假設(shè)我們有如下三個(gè)文本文件，a.txt, b.txt和c.txt：
對(duì)于輸入數(shù)據(jù)而言，input_key就是文件名，input_value就是一個(gè)大的string，包含的是文件內(nèi)容。所以我們的輸入數(shù)據(jù)看上去會(huì)是這樣的：
我們會(huì)寫(xiě)一個(gè)簡(jiǎn)單的串行的mapper(fileName, fileContent)函數(shù)。這個(gè)函數(shù)做的事情很簡(jiǎn)單，讀入一個(gè)文本文件，把每一個(gè)遇到的單詞當(dāng)作一個(gè)新的intermediate_key，并賦其intermediate_value為1。將mapper函數(shù)處理文件a，我們會(huì)得到如下結(jié)果：
將所有三個(gè)文件的處理結(jié)果放在一起，我們得到：
然后將中間結(jié)果按intermediate_key歸類(lèi)：
最后，由reducer(intermediate_key, intermediate_value_list)對(duì)中間結(jié)果進(jìn)行處理。它做的事也很簡(jiǎn)單，僅僅是把某intermediate_key對(duì)應(yīng)的所有intermediate_value相加。我們于是得到最終結(jié)果:
第二個(gè)例子，怎樣使用Map Reduce計(jì)算PageRank。什么是PageRank？可能大家都有所了解，這是Google用來(lái)量度一個(gè)網(wǎng)頁(yè)的重要性的值。簡(jiǎn)單而言，有越多的其它網(wǎng)頁(yè)鏈接到這個(gè)網(wǎng)頁(yè)，這個(gè)網(wǎng)頁(yè)的PageRank越高。鏈接到這個(gè)網(wǎng)頁(yè)的網(wǎng)頁(yè)P(yáng)ageRank越高，這個(gè)網(wǎng)頁(yè)的PageRank也越高。假設(shè)我們一共有n個(gè)網(wǎng)頁(yè)0, 1, …, n-1。對(duì)第j個(gè)網(wǎng)頁(yè)我們給它賦一個(gè)PageRank值qj。所有的qj組合起來(lái)成為一個(gè)向量q = (q0,q1, …qn-1)。這個(gè)向量滿(mǎn)足概率分布。即qj的值都在0和1之間，并且所有的qj加起來(lái)等于1。qj越大，網(wǎng)頁(yè)的重要性越高。那么q是怎么計(jì)算出來(lái)的呢？答案是使用迭代的方法：
我們從一個(gè)初始的PageRank向量分布P開(kāi)始，乘以一個(gè)n*n的矩陣M，得到一個(gè)新的PageRank向量。把新的PageRank向量繼續(xù)乘以M得到下一步的PageRank… … 如此迭代有限步后，PageRank向量的值會(huì)趨于收斂，于是我們得到最終的PageRank。
這里需要回答兩個(gè)問(wèn)題：1. 如何確定初始的PageRank，即迭代的起點(diǎn)？答案是任意選擇一個(gè)概率分布就可以，無(wú)論你選擇什么初始值，都不影響其收斂到最終的結(jié)果。我們通常使用均勻概率分布，即。2. 如何定義M？這個(gè)問(wèn)題稍顯復(fù)雜，有興趣的讀者可以參見(jiàn)Michael Nielsen 的博文Using MapReduce to compute PageRank了解更詳細(xì)的內(nèi)容。在這里，我們將其簡(jiǎn)化的定義為一個(gè)描述網(wǎng)頁(yè)間互相鏈接結(jié)構(gòu)的超大矩陣。假設(shè)網(wǎng)絡(luò)里有n個(gè)網(wǎng)頁(yè)，那么我們這個(gè)矩陣就是一個(gè)n*n的方陣。矩陣的每一列代表一個(gè)網(wǎng)頁(yè)對(duì)外的超鏈接情況。例如，我們定義#(j)為第j個(gè)網(wǎng)頁(yè)對(duì)外的所有超鏈接的數(shù)量。那么對(duì)于矩陣M的第j列而言，如果網(wǎng)頁(yè)j對(duì)網(wǎng)頁(yè)k沒(méi)有超鏈接，那么第k行元素Mkj=0，否則Mkj=1/#(j)。這里隱含的意思是當(dāng)一個(gè)讀者在瀏覽網(wǎng)頁(yè)j時(shí)，有1/#(j)的可能性跳轉(zhuǎn)到網(wǎng)頁(yè)k。
那么如何使用Map Reduce來(lái)計(jì)算PageRank呢？雖然整個(gè)迭代的過(guò)程必須是串行的，迭代的每一步我們還是可以用Map Reduce來(lái)并行的計(jì)算的。這里也必須并行的計(jì)算因?yàn)檫@個(gè)矩陣和向量的規(guī)模是超大的（想象一下整個(gè)互聯(lián)網(wǎng)的網(wǎng)頁(yè)數(shù)量）。使用Map Reduce來(lái)計(jì)算迭代的一步實(shí)際上是用Map Reduce來(lái)計(jì)算矩陣和向量的乘法。假設(shè)我們要計(jì)算如下一個(gè)方陣和向量的乘法。其實(shí)質(zhì)是將第i個(gè)向量元素的值pi乘以矩陣第i列的每一元素，然后放在矩陣元素原來(lái)的位置。最后，把矩陣第i行的所有元素相加，得到結(jié)果向量的第i個(gè)元素的值。
類(lèi)似的，我們可以得到用MapReduce計(jì)算PageRank的方法：
第一步，輸入的(input_key, input_value)。input_key是某個(gè)網(wǎng)頁(yè)的編號(hào)，如j。input_value是一個(gè)列表，元素值是M矩陣的第j列元素，最后再加上一個(gè)pj，就是當(dāng)前網(wǎng)頁(yè)j的PageRank值。
第二步，Map。Mapper(input_key, input_value)所做的事情很簡(jiǎn)單，就是把pj乘以列表元素的每一個(gè)值，然后輸出一組(intermediate_key, intermediate_value)。intermediate_key就是矩陣的行號(hào)，k。intermediate_value就是pj列表元素的值，即pj乘以矩陣第k行第j列的元素的值。
第三步，匯總。把所有intermediate_key相同的中間結(jié)果放到一起。即是把第k行所有的intermediate_value放在一個(gè)列表intermediate_value_list內(nèi)。
第四步，Reduce。Reducer(intermediate_key, intermediate_value_list)做的事也很簡(jiǎn)單，就是把intermediate_value_list內(nèi)所有的值相加。最后形成的(output_key, output_value)就是結(jié)果向量第k行的元素值。
以上就是利用Map Reduce計(jì)算PageRank的簡(jiǎn)略過(guò)程。這個(gè)過(guò)程相當(dāng)粗略和不精確，只是為了揭示Map Reduce的工作過(guò)程和Google曾經(jīng)用來(lái)計(jì)算PageRank的大致方法。認(rèn)真的讀者應(yīng)該查閱其它更嚴(yán)謹(jǐn)?shù)闹鳌?/p>
最后，和上述計(jì)算矩陣和向量乘法的例子相似，Map Reduce也可以用來(lái)計(jì)算兩個(gè)向量的點(diǎn)乘。具體怎么做留給讀者自己去思考，一個(gè)提示是我們所有的intermediate_key都是相同的，可以取同一個(gè)值例如1。
這是一個(gè)“算法模式”。事實(shí)上，把Data Parallelism和下節(jié)將要提到的Task Parallelism都稱(chēng)之為一種“算法模式”我覺(jué)得有過(guò)于籠統(tǒng)之嫌。到最后，哪一種并行算法不是被分解為并行執(zhí)行的task呢（task parallelism）？ 而并行執(zhí)行的task不都是處理著各自的那份數(shù)據(jù)嗎（data parallelism）？所以如果硬要把Data Parallelism和Task Parallelism稱(chēng)為兩種算法模式，我只能說(shuō)它們的地位要高于其它的算法模式。它們是其它算法模式的基礎(chǔ)。只不過(guò)對(duì)于有些問(wèn)題而言，比較明顯的我們可以把它看成是Data Parallelism的或是Task Parallelism的。也許Data Parallelism模式和Task Parallelism模式特指的就是這類(lèi)比較明顯的問(wèn)題。
那么什么是Data Parallelism? 顧名思義，就是這類(lèi)問(wèn)題可以表達(dá)為同樣的一組操作被施加在不同的相互獨(dú)立的數(shù)據(jù)上。
一個(gè)比較典型的例子就是計(jì)算機(jī)圖形學(xué)里面的Ray tracing算法。Ray tracing算法可以大致描述為從一個(gè)虛擬相機(jī)的光心射出一條射線(xiàn)，透過(guò)屏幕的某個(gè)像素點(diǎn)，投射在要渲染的幾何模型上。找到射線(xiàn)和物體的交點(diǎn)后，再根據(jù)該點(diǎn)的材料屬性、光照條件等，算出該像素點(diǎn)的顏色值，賦給屏幕上的像素點(diǎn)。由于物體的幾何模型很多個(gè)小的三角面片表示，算法的第一步就是要求出射線(xiàn)與哪個(gè)三角面片有交點(diǎn)。射線(xiàn)與各個(gè)單獨(dú)的三角面片求交顯然是相互獨(dú)立的，所以這可以看做是Data Parallelism的例子。
Task Parallelism的算法模式可以表述為，一組互相獨(dú)立的Task各自處理自己的數(shù)據(jù)。和Data Parallelism不同，這里關(guān)注的重點(diǎn)不是數(shù)據(jù)的劃分，而是Task的劃分。
如前所述，Task Parallelism和Data Parallelism是密不可分的?；ハ嗒?dú)立的Task肯定也是運(yùn)行在互相獨(dú)立的數(shù)據(jù)上。這主要是看我們以什么樣的視角去看問(wèn)題。例如，上一節(jié)RayTracing的例子中，我們也可以把射線(xiàn)和一個(gè)獨(dú)立的三角面片求交看作是一個(gè)獨(dú)立的Task。這樣就也可以當(dāng)它做是Task Parallelism的例子。然而，咬文嚼字的去區(qū)分到底是Task Parallelism還是Data Parallelism不是我們的目的，我們關(guān)注的應(yīng)該是問(wèn)題本身。對(duì)于某一個(gè)具體問(wèn)題，從Data Parallelism出發(fā)考慮方便還是從Task Parallelism出發(fā)考慮方便，完全取決于問(wèn)題本身的應(yīng)用場(chǎng)景以及設(shè)計(jì)人員自身的經(jīng)驗(yàn)、背景。事實(shí)上，很多時(shí)候，不管你是從Task Parallelism出發(fā)還是從Data Parallelism出發(fā)，經(jīng)過(guò)不斷的優(yōu)化，最終的解決方案可能是趨同的。
下面一個(gè)矩陣乘法的例子很好的說(shuō)明了這個(gè)問(wèn)題。我們都知道矩陣乘法的定義：假如有n行k列的矩陣A乘以k行m列的矩陣B，那么我們可以得到一個(gè)n行m列的的矩陣C。矩陣C的第n行第m列的元素的值等于矩陣A的第n行和矩陣B的第m列的點(diǎn)乘。
從Task Parallelism的角度出發(fā)，我們可能把計(jì)算C的每一個(gè)元素當(dāng)做一個(gè)獨(dú)立的Task。接下來(lái)，為了提高CPU的緩存利用率，我們可能把鄰近幾個(gè)單元格的計(jì)算合并成一個(gè)大一點(diǎn)的Task。從Data Parallelism的角度出發(fā)，我們可能一開(kāi)始把C按行分成不同的塊。為了探索到底怎樣的劃分更加有效率，我們可能調(diào)整劃分的方式和大小，最后，可能發(fā)現(xiàn)，最有效率的做法是把A，B，C都分成幾個(gè)不同的小塊，進(jìn)行分塊矩陣的乘法?？梢钥吹?，這個(gè)結(jié)果實(shí)際上和從Task Parallelism出發(fā)考慮的方案是殊途同歸的。
Recursive Splitting指的是這樣一種算法模式：為了解決一個(gè)大問(wèn)題，把它分解為可以獨(dú)立求解的小問(wèn)題。分解出來(lái)的小問(wèn)題，可能又可以進(jìn)一步分解為更小的問(wèn)題。把問(wèn)題分解到足夠小的規(guī)模后，就可以直接求解了。最后，把各個(gè)小問(wèn)題的解合并為原始的大問(wèn)題的解。這實(shí)際上是我們傳統(tǒng)的串行算法領(lǐng)域里面也有的“divide and conquer”的思想。
舉兩個(gè)例子。第一個(gè)是傳統(tǒng)的歸并排序。例如，要排序下面的8個(gè)元素的數(shù)組，我們不管三七二十一先把它一分為二。排序4個(gè)元素的數(shù)組還是顯得太復(fù)雜了，于是又一分為二?，F(xiàn)在，排序2個(gè)元素的數(shù)組很簡(jiǎn)單，按照大小交換順序就行。最后，把排好序的數(shù)組按序依次組合起來(lái)，就得到我們最終的輸出結(jié)果。
第二個(gè)例子稍微有趣一點(diǎn)，是一個(gè)如何用程序解“數(shù)獨(dú)”游戲的例子?！皵?shù)獨(dú)”就是在一個(gè)9*9的大九宮格內(nèi)有9個(gè)3*3的小九宮格。里面有些格子已經(jīng)填入了數(shù)字，玩家必須在剩下的空格里也填入1到9的數(shù)字，使每個(gè)數(shù)字在每行、每列以及每個(gè)小九宮格內(nèi)只出現(xiàn)一次。
這里作為舉例說(shuō)明，我們考慮一個(gè)簡(jiǎn)單一點(diǎn)的情況：在一個(gè)4*4的格子里填入1~4的數(shù)字，使其在每行、每列以及每個(gè)2*2的格子里只出現(xiàn)一次。
解“數(shù)獨(dú)”游戲的算法可以有很多種。如果是人來(lái)解，大概會(huì)按照上圖的次序依次填入1,2,3到相應(yīng)的格子當(dāng)中。每填入一個(gè)新數(shù)字，都會(huì)重新按規(guī)則評(píng)估周?chē)目崭?，看能否按現(xiàn)有情況再填入一些數(shù)字。這個(gè)方法當(dāng)然沒(méi)錯(cuò)，不過(guò)看上去不太容易并行化。下面介紹一個(gè)按照“recursive splitting”的方法可以很容易做到并行化的解法。
1） 首先，將二維的數(shù)獨(dú)格子展開(kāi)成一個(gè)一維的數(shù)組。已經(jīng)有數(shù)字的地方是原來(lái)的數(shù)字，空格子的地方填上“0”。
2） 接下來(lái)，從前到后對(duì)數(shù)組進(jìn)行掃描。第一格是“3”，已經(jīng)有數(shù)字了，跳過(guò)。移動(dòng)搜索指針到下一格。
3） 第二格是“0”，意味著我們需要填入一個(gè)新的數(shù)字。這個(gè)新的數(shù)字有4種可能性：1， 2， 3， 4。所以創(chuàng)建4個(gè)新的搜索分支：
4） 接下來(lái)根據(jù)現(xiàn)有的數(shù)字信息檢查各個(gè)搜索分支。明顯，第三和第四個(gè)搜索分支是非法的。因?yàn)槲覀冊(cè)谕恍兄幸呀?jīng)有了數(shù)字“3”和“4”。所以忽略這兩個(gè)分支。第一和第二條分支用現(xiàn)有的數(shù)字檢查不出沖突，所以繼續(xù)從這兩個(gè)分支各派生出4條新的分支進(jìn)行搜索… …
這個(gè)思路像極了我們之前的歸并排序的例子，都是在算法運(yùn)行的過(guò)程中不斷產(chǎn)生出新的任務(wù)。所以實(shí)際上這也是一個(gè)“Task Parallelism”的例子。
“Pipeline”也是一種比較常見(jiàn)的算法模式。通常，我們都會(huì)用汽車(chē)裝配中的流水線(xiàn)、CPU中指令執(zhí)行的流水線(xiàn)來(lái)類(lèi)比的說(shuō)明這一模式。它說(shuō)的是我們會(huì)對(duì)一批數(shù)據(jù)進(jìn)行有序、分階段的處理，前一階段處理的輸出作為下一階段處理的輸入。每一個(gè)階段永遠(yuǎn)只重復(fù)自己這一階段的任務(wù)，不停的接受新的數(shù)據(jù)進(jìn)行處理。用一個(gè)軟件上的例子打比方，我們要打開(kāi)一批文本文件，將里面每一個(gè)單詞的字母全部改成大寫(xiě)，然后寫(xiě)到一批新的文件里面去，就可以創(chuàng)建一條有3個(gè)stage的流水線(xiàn)：讀文件，改大寫(xiě)，寫(xiě)文件。
“Pipeline”模式的概念看上去很容易理解，可是也不是每一個(gè)人都能一下子理解的那么透徹的。例如有這樣一個(gè)問(wèn)題：我們有一個(gè)for循環(huán)，循環(huán)體是一條有3個(gè)stage的pipeline，每個(gè)stage的運(yùn)行時(shí)間分別是10， 40， 和10個(gè)CPU的時(shí)鐘間隔。請(qǐng)問(wèn)這個(gè)for循環(huán)執(zhí)行N次大概需要多長(zhǎng)時(shí)間（N是一個(gè)很大的數(shù)）？
A. 60*N
B. 10*N
C. 60
D. 40*N
請(qǐng)仔細(xì)思考并選擇一個(gè)答案。:-)
答案是40*N。流水線(xiàn)總的執(zhí)行時(shí)間是由它最慢的一個(gè)stage決定的。原因請(qǐng)見(jiàn)下圖。
接下來(lái)這兩個(gè)算法模式看上去都顯得比較特殊化，只針對(duì)某些特定的應(yīng)用類(lèi)型。“Geometric decomposition”說(shuō)的是對(duì)于一些線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組），我們可以把數(shù)據(jù)切分成幾個(gè)連續(xù)的子集。因?yàn)檫@種切分模式看上去和把一塊幾何區(qū)域切分成連續(xù)的幾塊很類(lèi)似，我們就把它叫做”Geometric decomposition”。
最常用的例子是分塊矩陣的乘法。例如，為了計(jì)算兩個(gè)矩陣A，B的乘法。我們可以把他們切分成各自可以相乘的小塊。
結(jié)果矩陣當(dāng)然也是分塊的：
結(jié)果矩陣每一分塊的計(jì)算按照如下公式進(jìn)行：
例如：
最終的結(jié)果就是：
下面這幅圖顯示了兩個(gè)4*4的分塊矩陣A，B進(jìn)行乘法時(shí)，計(jì)算結(jié)果矩陣C的某一分塊時(shí)，需要依次訪(fǎng)問(wèn)的A，B矩陣的分塊。黑色矩陣分塊代表要計(jì)算的C的分塊，行方向上的灰色矩陣代表要訪(fǎng)問(wèn)的矩陣A的分塊，列方向上的灰色分塊代表要訪(fǎng)問(wèn)的矩陣B的分塊。
這個(gè)模式的名字取得很怪異，也有其他人把它叫做“Recursive Data”。不過(guò)相比而言，還是這個(gè)名字更為貼切。它指的是這一類(lèi)模式：有些問(wèn)題的處理使用傳統(tǒng)的方法，必須依賴(lài)于對(duì)數(shù)據(jù)進(jìn)行有序的訪(fǎng)問(wèn)，例如深度優(yōu)先搜索，這樣就很難并行化。但是假如我們?cè)敢饣ㄙM(fèi)一些額外的計(jì)算量，我們就能夠采用并行的方法來(lái)解決這個(gè)問(wèn)題。
常用的一個(gè)例子是如下的“尋找根節(jié)點(diǎn)”的問(wèn)題。假設(shè)我們有一個(gè)森林，里面每一個(gè)節(jié)點(diǎn)都只記錄了自己的前向節(jié)點(diǎn)，根節(jié)點(diǎn)的前向節(jié)點(diǎn)就是它自己。我們要給每一個(gè)節(jié)點(diǎn)找到它的根節(jié)點(diǎn)。用傳統(tǒng)的方法，我們只能從當(dāng)前節(jié)點(diǎn)出發(fā)，依次查找它的前向節(jié)點(diǎn)，直到前向節(jié)點(diǎn)是它自身。這種算法對(duì)每一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度是O(N)?？偟臅r(shí)間復(fù)雜度是N*O(N)。
如果我們能換一種思路來(lái)解這個(gè)問(wèn)題就可以將其并行化了。我們可以給每一個(gè)節(jié)點(diǎn)定義一個(gè)successor（后繼結(jié)點(diǎn)），successor的初始值都是其前向節(jié)點(diǎn)。然后我們可以同步的更新每一個(gè)節(jié)點(diǎn)的successor，令其等于“successor的successor”，直到successor的值不再變化為止。這樣對(duì)于上圖的例子，最快兩次更新，我們就可以找到每個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)了。這種方法能同時(shí)找到所有節(jié)點(diǎn)的根節(jié)點(diǎn)，總的時(shí)間復(fù)雜度是N*log (N)。
如前所述，“并行編程中的設(shè)計(jì)模式”是一個(gè)仍在不斷變化、發(fā)展的領(lǐng)域。這篇博文簡(jiǎn)要介紹了這一領(lǐng)域當(dāng)前的發(fā)展現(xiàn)狀，并選取八個(gè)常用的模式進(jìn)行了介紹。我涉足并行編程領(lǐng)域不久，很多理解也并不深入。所以文章的缺點(diǎn)錯(cuò)誤在所難免，真誠(chéng)希望能得到大家的批評(píng)指正。
本文的寫(xiě)作參考了如下資源，可以作為進(jìn)一步閱讀的材料：
· 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?
聯(lián)系客服
