并行編程中的設(shè)計(jì)模式

1、并行編程中的設(shè)計(jì)模式這篇文章是對(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)沒有達(dá)到統(tǒng)一 認(rèn)識(shí)的高度。也沒有一套業(yè)界普遍認(rèn)同的體系或者描述。這就造成了當(dāng)前這一領(lǐng)域的現(xiàn)狀: 從事研究的人有不同的背景，他們各自總結(jié)出的模式種類不盡相同。即使是同一個(gè)模式，不 同的團(tuán)隊(duì)給它們?nèi)〉妹忠部赡懿灰粯?。不過這并不妨礙我們對(duì)并行編程中的設(shè)計(jì)模式 進(jìn)行一定的了解，并在實(shí)際的軟件開發(fā)工作中有所借鑒。

2、本文分兩部分，第一部分會(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)用例子來幫助理 解。我始終相信，通過例子的學(xué)習(xí)是最容易理解的一種方式。并行編程模式的發(fā)展現(xiàn)狀在這一領(lǐng)域比較活躍的研究團(tuán)體包括：1.加州大學(xué)伯克利分校。其代表人物是Kurt Keutzer教授，他曾是Synopsys公司的CTO。Intel公司。代表

3、人物是Tim Mattson，他是Intel的Principle Engineer和并行計(jì)算 的布道師(evangelist)，是“Patterns for Parallel Programming” 一 書的作者。3.伊利諾伊大學(xué)。代表人物是Ralph Johnson教授。他是著名的設(shè)計(jì)模式“Gang of Four” 中的一員。這其中，我最為喜歡加州大學(xué)伯克利分校的體系：4.其他團(tuán)體：包括微軟、麻省理工大學(xué)等等。他們總結(jié)出的并行編程模式體系不盡相同，互相之間又有著緊密的聯(lián)系。主要有：加州大學(xué)伯克利分校的 A Pattern Language for Parallel Programming

4、 ver2.0伊利諾伊大學(xué)的 Parallel Programming PatternsTim Mattson 的著作 Patterns for Parallel Programming伯克利的研究人員認(rèn)為，寫出高質(zhì)量并行軟件的關(guān)鍵在于擁有好的軟件設(shè)計(jì)：從軟件的總體 架構(gòu)，一直到系統(tǒng)的底層實(shí)現(xiàn)。將這些好的設(shè)計(jì)以一種系統(tǒng)的方式描述出來，并在各個(gè)不 同的軟件項(xiàng)目當(dāng)中重用是解決構(gòu)建高質(zhì)量并行軟件問題的關(guān)鍵。這遠(yuǎn)比各種具體的編程模型 以及其支撐環(huán)境來得重要。因?yàn)閾碛辛艘粋€(gè)好的設(shè)計(jì)之后，我們可以很容易的在各種開發(fā)平 臺(tái)上編寫源代碼。伯克利的模式體系包含了幾個(gè)不同的層次，上自軟件架構(gòu)，下至程序指令執(zhí)行的策

5、略。最上 面的兩塊分別是架構(gòu)模式”(Structural patterns)和計(jì)算模式”(Computational patterns)。這兩塊并不單單包括并行軟件，也包括傳統(tǒng)的串行軟件模式。用我們常用來表 達(dá)系統(tǒng)架構(gòu)的線框圖打比方，架構(gòu)模式”指的就是那些箭頭和框框，它們表示的是程序總體 的組織結(jié)構(gòu)，以及各部分之間是怎么交互的。計(jì)算模式”指的是框框里面的計(jì)算類型。例如， 是基于圖的算法，還是有限狀態(tài)機(jī)，還是線性代數(shù)運(yùn)算，等等。程序設(shè)計(jì)師通常需要在這兩 大類模式之間翻來覆去的進(jìn)行選擇。例如，我們可能先選擇了一種架構(gòu)模式，然后考慮使用 某些合適的計(jì)算模式。但是選擇的計(jì)算模式可能更適合于在另一種架構(gòu)

6、模式下運(yùn)行，所以我 們又得重新選擇一種架構(gòu)模式如此反復(fù)。上面這張圖在架構(gòu)模式和計(jì)算模式這兩大 塊之間畫了兩個(gè)反復(fù)的箭頭，表達(dá)的就是這個(gè)意思。這張圖下方的三大塊就專指并行編程當(dāng)中的模式了。它們包括算法模式”(Algorithm strategy patterns)，實(shí)現(xiàn)模式(Implementation strategy patterns)和并行執(zhí)行模 式”(Parallel execution patterns)。顧名思義，算法模式指的是程序算法層面的模式。 它們表達(dá)的是，為了解決某一類實(shí)際問題，怎么樣在較高的算法層面實(shí)現(xiàn)并行。實(shí)現(xiàn)模式” 指的是我們?cè)诰帉懺创a的時(shí)候，利用什么樣的一些程序控制

7、結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)并行。 例如parallel_for，例如并行容器，等等。最后一個(gè)并行執(zhí)行模式指的是為了在計(jì)算機(jī) 中有效的執(zhí)行一個(gè)并行程序，我們應(yīng)該采取哪些方法。這包括指令的執(zhí)行模式，例如是MIMD 還是SIMD，也包括一些任務(wù)調(diào)度的策略。這三類模式是緊密聯(lián)系在一起的。例如，為了解 決一個(gè)問題，我們可能使用recursive splitting7的算法模式。而為了實(shí)現(xiàn)這個(gè)算法，我們 很有可能使用fork-join的實(shí)現(xiàn)模式。在執(zhí)行層面，并行程序庫則通常會(huì)用thread pool” 的并行執(zhí)行模式來支持fork-join的運(yùn)行。由于我們?cè)诰帉懗绦驎r(shí)，并行執(zhí)行模式往往由編譯器或并行程序庫例如T

8、BB的編寫人員 考慮，我們并不需要關(guān)心；實(shí)現(xiàn)模式和我們選擇的具體并行運(yùn)算平臺(tái)有關(guān)(OpenMP，TBB， MPI，.,，等等)，不同的平臺(tái)有不同的API； 計(jì)算模式則和具體的問題域聯(lián)接緊密。而 且，看上去伯克利所總結(jié)的計(jì)算模式”大部分和高性能計(jì)算有關(guān)，普通的應(yīng)用程序員并不熟 悉。所以在本文，我將只挑選和并行計(jì)算密切相關(guān)的兩個(gè)架構(gòu)模式和六個(gè)常見的算法模 式舉例進(jìn)行說明。2八個(gè)常用的并行編程模式2.1 Agent and RepositoryDm叫* 謫me ritconi rdf Mem這是一個(gè)架構(gòu)模式”，它針對(duì)這樣一類問題：我們有一組數(shù)據(jù)，它們會(huì)隨機(jī)的被一些不同的 對(duì)象進(jìn)行修改。解決這一類問題

9、的方案是，創(chuàng)建一個(gè)集中管理的數(shù)據(jù)倉庫(data repository)， 然后定義一組自治的agent來操作這些數(shù)據(jù)，可能還有一個(gè)manager來對(duì)agent的操作 進(jìn)行協(xié)調(diào)，并保證數(shù)據(jù)倉庫中數(shù)據(jù)的一致性。我們常見的源代碼版本控制軟件例如Perforce 就是實(shí)現(xiàn)這種架構(gòu)的典型代表：源代碼都存放在一個(gè)統(tǒng)一的服務(wù)器中(或是一組服務(wù)器中， 但對(duì)client而言是透明的)，不同的程序員們使用各自的客戶端對(duì)源代碼文件進(jìn)行讀，寫， 加，刪的操作。由Perforce負(fù)責(zé)保證源代碼數(shù)據(jù)的一致性。Map ReduceMap Reduce這個(gè)名詞原來是函數(shù)式編程里面的一個(gè)概念，但是自從Google于2004年

10、推出同名的并行計(jì)算程序庫后，提到這個(gè)名詞大家大多想到的是Google的這個(gè) Frameworko在這里，Map Reduce是一個(gè)架構(gòu)模式”的名稱。當(dāng)然，我們這里的Map Reduce指的就是類似Google Map Reduce工作原理的一類模式。那么什么是Map Reduce的模式呢？用較為簡(jiǎn)單的語言描述，它指的是這樣一類問題的解 決方案：我們可以分兩步來解決這類問題。第一步，使用一個(gè)串行的Mapper函數(shù)分別處 理一組不同的數(shù)據(jù)，生成一個(gè)中間結(jié)果。第二步，將第一步的處理結(jié)果用一個(gè)Reducer函 數(shù)進(jìn)行處理(例如，歸并操作)，生成最后的結(jié)果。從使用Google的Map Reduce程序

11、庫的角度而言，作為應(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ì)算誤差，通通被隱藏在程序庫內(nèi)。那么Map Reduce到底是什么樣的一個(gè)過程呢？我們講過，使用Map Reduce，程序員必須提供一組輸入數(shù)據(jù)，以及一個(gè)Mapper和一個(gè) Reducer函數(shù)。在這里，輸入數(shù)據(jù)必須是一個(gè)按(inpu

12、t_key,input_value)方式組織的列 表。mapper函數(shù)的任務(wù)是處理輸入列表中的某一個(gè)單元數(shù)據(jù)：mapper(input_key,input_value),并產(chǎn)生如下輸出結(jié)果:(InterMMliatejcey P irate &diate_viilae-r ,接下來，把對(duì)所有單元數(shù)據(jù)的處理結(jié)果按照intermediate_key歸類：同樣的 intermediate_key放在一起，它們的intermediate_value簡(jiǎn)單的串接起來，得到：in termed iar&_ kc/, jntem-ediu(bniermtd i M e_kev,. int e rmedjie_

13、vjl u e_li iLLJReducer函數(shù)的任務(wù)是對(duì)上述的中間結(jié)果進(jìn)行處理：reducer(intermediate_key, intermediate_value_list)，并產(chǎn)生如下最終輸出結(jié)果：| ou tput keyf o ut |ut_ vl u e(ou tpu t_k.ev. o utpu r_val ueLJ我們會(huì)舉兩個(gè)例子說明這一過程。第一個(gè)例子是一個(gè)簡(jiǎn)單的統(tǒng)計(jì)單詞出現(xiàn)次數(shù)的小程序。第 二個(gè)例子是Google曾經(jīng)怎樣使用Map Reduce FrameWork來計(jì)算Page Rank。第一個(gè)例子，假設(shè)我們要寫一個(gè)小程序，來統(tǒng)計(jì)在幾篇不同文章里所有出現(xiàn)過的單詞各自總

14、共出現(xiàn)的次數(shù)。我們應(yīng)該怎么做呢？下面描述的利用Map Reduce的方法肯定不是大多數(shù) 程序員第一感會(huì)想到的方法。但這種方法非常好的揭示了 Map Reduce的基本思想。并且， 這種方法很容易被擴(kuò)展到處理上千萬甚至是上億的文件數(shù)據(jù)，并且能夠在一個(gè)分布的計(jì)算機(jī) 集群里面運(yùn)行。這可不是傳統(tǒng)的方法能夠輕易做到的。具體而言，假設(shè)我們有如下三個(gè)文本文件，a.txt, b.txt和c.txt：mt： qmcJE勺 syce 匕 i-hsy&作 m仕 aiuiLl 彌眉宅由 f&r a man P *r；e 中立易力丘 le&p.；K&0 日 A1 細(xì)fl VAA W-J-Lts l-MV：AilI eT

15、etywtierc WhiiX ISaiy Trent,!Tla：骨玉t gw.對(duì)于輸入數(shù)據(jù)而言，input_key就是文件名，input_value就是一個(gè)大的string，包含的 是文件內(nèi)容。所以我們的輸入數(shù)據(jù)看上去會(huì)是這樣的：我們會(huì)寫一個(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é)果： TOC o 1-5 h z H flh BquictS 也 throw

16、n% 心 HiMl七 nr pwl in mwjr,n- ru叫m將所有三個(gè)文件的處理結(jié)果放在一起，我們得到:quLCk11 r 4 隹白Ji，f=diHp*cr。 lja rave-r*ff :f ，匕卜卷。 Z, 4 .丸，與甘七 E Cxey4 d號(hào)七 IK tMfy- Ik -LadP IL KE I!- PMvtn* 1皿 r 11, e113 1,耳# J lee-r :I Bwaj i| P W枇*:13.1 邛邛、珥 I%.lhswrrref.MRki.nd1 f 卻然后將中間結(jié)果按intermediate_key歸類：tPW：-EaK-;-BYrr- : 4 , -ijM-:

17、 L 町.，naJ : 時(shí)匚【!/ rlt3c，:L*ni七站：,，時(shí)皿 B (JJ.F?rF； Ir Hr rWpf41 i IL I4 i mt THWHl IF b to 1 e LJ j. 1 leajifa : 1 j ft=e r (,!. wn-3 1 L 土.S lr Ij r NtTESVm ljft 1, 1 SUE* r : !.)3)1J . /企日cP F ili, Lmfiw* lh PWL 1H j -whlJEi 11,11 j( jEax-1 j 幻鼻 lbfcbwn 1 1) t(-LAftyj B 1， CSilLSt1 4. 1)；. 。土 虹七 Ih

18、j LlSEEle* P pFMti fcj.11 step W L(icanJEiEid1 1 . 1.心為七 1 W 2 / fleeee H. -(flrey 】 尸dkM。Mf quitfe1,. 1“ pth*fc,引.(tfiACs 1J第二個(gè)例子，怎樣使用Map Reduce計(jì)算PageRank。什么是PageRank？可能大家都有 所了解，這是Google用來量度一個(gè)網(wǎng)頁的重要性的值。簡(jiǎn)單而言，有越多的其它網(wǎng)頁鏈接 到這個(gè)網(wǎng)頁，這個(gè)網(wǎng)頁的PageRank越高。鏈接到這個(gè)網(wǎng)頁的網(wǎng)頁P(yáng)ageRank越高，這個(gè) 網(wǎng)頁的PageRank也越高。假設(shè)我們一共有n個(gè)網(wǎng)頁0, 1,，n-1。

19、對(duì)第j個(gè)網(wǎng)頁我們給 它賦一個(gè)PageRank值。所有的qj組合起來成為一個(gè)向量q = (qD,q1, -qn-1)o這個(gè)向 量滿足概率分布。即的值都在0和1之間，并且所有的qj加起來等于1。越大，網(wǎng)頁的重要性越高。那么q是怎么計(jì)算出來的呢？答案是使用迭代的方法:我們從一個(gè)初始的PageRank向量分布P開始，乘以一個(gè)n*n的矩陣M，得到一個(gè)新的 PageRank向量。把新的PageRank向量繼續(xù)乘以M得到下一步的PageRank 如此迭代有限步后，PageRank向量的值會(huì)趨于收斂，于是我們得到最終的PageRank。這里需要回答兩個(gè)問題：1.如何確定初始的PageRank，即迭代的起點(diǎn)？答

20、案是任意選擇 一個(gè)概率分布就可以，無論你選擇什么初始值，都不影響其收斂到最終的結(jié)果。我們通常使 用均勻概率分布，即2.如何定義M？這個(gè)問題稍顯復(fù)雜，有興趣 的讀者可以參見 Michael Nielsen 的博文 Using MapReduce to compute PageRank 了解更詳細(xì)的內(nèi)容。在這里，我們將其簡(jiǎn)化的定義為一個(gè)描述網(wǎng)頁間互相鏈接結(jié)構(gòu)的超大矩 陣。假設(shè)網(wǎng)絡(luò)里有n個(gè)網(wǎng)頁，那么我們這個(gè)矩陣就是一個(gè)n*n的方陣。矩陣的每一列代表 一個(gè)網(wǎng)頁對(duì)外的超鏈接情況。例如，我們定義#(j)為第j個(gè)網(wǎng)頁對(duì)外的所有超鏈接的數(shù)量。 那么對(duì)于矩陣M的第j列而言，如果網(wǎng)頁j對(duì)網(wǎng)頁k沒有超鏈接，那么第k

21、行元素Mkj=0， 否則Mkj=1/#(j)。這里隱含的意思是當(dāng)一個(gè)讀者在瀏覽網(wǎng)頁j時(shí)，有1/#(j)的可能性跳轉(zhuǎn) 到網(wǎng)頁k。那么如何使用Map Reduce來計(jì)算PageRank呢？雖然整個(gè)迭代的過程必須是串行的，迭 代的每一步我們還是可以用Map Reduce來并行的計(jì)算的。這里也必須并行的計(jì)算因?yàn)檫@ 個(gè)矩陣和向量的規(guī)模是超大的(想象一下整個(gè)互聯(lián)網(wǎng)的網(wǎng)頁數(shù)量)。使用Map Reduce來 計(jì)算迭代的一步實(shí)際上是用Map Reduce來計(jì)算矩陣和向量的乘法。假設(shè)我們要計(jì)算如下 一個(gè)方陣和向量的乘法。其實(shí)質(zhì)是將第i個(gè)向量元素的值pi乘以矩陣第i列的每一元素，然 后放在矩陣元素原來的位置。最后，

22、把矩陣第i行的所有元素相加，得到結(jié)果向量的第i個(gè) 元素的值。(臨MgPa胡%M j類似的，我們可以得到用MapReduce計(jì)算PageRank的方法：第一步，輸入的(input_key, input_value)。input_key是某個(gè)網(wǎng)頁的編號(hào)，如j。input_value是一個(gè)列表，元素值是M矩陣的第j列元素，最后再加上一個(gè)0 就是當(dāng)前 網(wǎng)頁j的PageRank值。第二步，Map。Mapper(input_key, input_value)所做的事情很簡(jiǎn)單，就是把pj乘以列 表元素的每一個(gè)值，然后輸出一組(intermediate_key, intermediate_value)。int

23、ermediate_key就是矩陣的行號(hào)，k。intermediate_value就是pj列表元素的值，即 pj乘以矩陣第k行第j列的元素的值。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, outp

24、ut_value)就是結(jié)果向量第k行的元素值。以上就是利用Map Reduce計(jì)算PageRank的簡(jiǎn)略過程。這個(gè)過程相當(dāng)粗略和不精確，只 是為了揭示Map Reduce的工作過程和Google曾經(jīng)用來計(jì)算PageRank的大致方法。認(rèn) 真的讀者應(yīng)該查閱其它更嚴(yán)謹(jǐn)?shù)闹?。最后，和上述?jì)算矩陣和向量乘法的例子相似，Map Reduce也可以用來計(jì)算兩個(gè)向量的 點(diǎn)乘。具體怎么做留給讀者自己去思考，一個(gè)提示是我們所有的intermediate_key都是 相同的，可以取同一個(gè)值例如1。Data Parallelism這是一個(gè)算法模式”。事實(shí)上，把Data Parallelism和下節(jié)將要提到的Tas

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

26、sk Parallelism模式特指的就是這類比 較明顯的問題。那么什么是Data Parallelism?顧名思義，就是這類問題可以表達(dá)為同樣的一組操作被施 加在不同的相互獨(dú)立的數(shù)據(jù)上。一個(gè)比較典型的例子就是計(jì)算機(jī)圖形學(xué)里面的Ray tracing算法。Ray tracing算法可以大致描述為從一個(gè)虛擬相機(jī)的光心射出一條射線，透過屏幕的某個(gè)像素點(diǎn)，投射在要渲染的 幾何模型上。找到射線和物體的交點(diǎn)后，再根據(jù)該點(diǎn)的材料屬性、光照條件等，算出該像素 點(diǎn)的顏色值，賦給屏幕上的像素點(diǎn)。由于物體的幾何模型很多個(gè)小的三角面片表示，算法的 第一步就是要求出射線與哪個(gè)三角面片有交點(diǎn)。射線與各個(gè)單獨(dú)的三角面片求

27、交顯然是相互 獨(dú)立的，所以這可以看做是Data Parallelism的例子。Task ParallelismTask 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ù)上。這主要是看我們以什么樣的視角去看問題。例如，上一節(jié) RayTracing的例子中，我們也可以把射線和一個(gè)獨(dú)立的三角面片求交看作是一個(gè)獨(dú)立的 Task。這樣就也可

28、以當(dāng)它做是Task Parallelism的例子。然而，咬文嚼字的去區(qū)分到底是 Task Parallelism還是Data Parallelism不是我們的目的，我們關(guān)注的應(yīng)該是問題本身。對(duì)于某一個(gè)具體問題，從Data Parallelism出發(fā)考慮方便還是從Task Parallelism出發(fā) 考慮方便，完全取決于問題本身的應(yīng)用場(chǎng)景以及設(shè)計(jì)人員自身的經(jīng)驗(yàn)、背景。事實(shí)上，很多 時(shí)候，不管你是從Task Parallelism出發(fā)還是從Data Parallelism出發(fā)，經(jīng)過不斷的優(yōu) 化，最終的解決方案可能是趨同的。下面一個(gè)矩陣乘法的例子很好的說明了這個(gè)問題。我們都知道矩陣乘法的定義：假如有

29、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。 接下來，為了提高CPU的緩存利用率，我們可能把鄰近幾個(gè)單元格的計(jì)算合并成一個(gè)大一 點(diǎn)的Task。從Data Parallelism的角度出發(fā)，我們可能一開始把C按行分成不同的塊。 為了探索到底怎樣的劃分更加有效率，我們可能調(diào)整劃分的方式和大小，最后，可能發(fā)現(xiàn)， 最有效率的做法是把A，B，C都分成幾個(gè)不同的小塊，進(jìn)行分塊矩陣的乘法。可以看到， 這

30、個(gè)結(jié)果實(shí)際上和從Task Parallelism出發(fā)考慮的方案是殊途同歸的。Recursive SplittingRecursive Splitting指的是這樣一種算法模式：為了解決一個(gè)大問題，把它分解為可以獨(dú) 立求解的小問題。分解出來的小問題，可能又可以進(jìn)一步分解為更小的問題。把問題分解到 足夠小的規(guī)模后，就可以直接求解了。最后，把各個(gè)小問題的解合并為原始的大問題的解。 這實(shí)際上是我們傳統(tǒng)的串行算法領(lǐng)域里面也有的“divide and conquer”的思想。舉兩個(gè)例子。第一個(gè)是傳統(tǒng)的歸并排序。例如，要排序下面的8個(gè)元素的數(shù)組，我們不管 三七二十一先把它一分為二。排序4個(gè)元素的數(shù)組還是顯得

31、太復(fù)雜了，于是又一分為二。 現(xiàn)在，排序2個(gè)元素的數(shù)組很簡(jiǎn)單，按照大小交換順序就行。最后，把排好序的數(shù)組按序 依次組合起來，就得到我們最終的輸出結(jié)果。Merge sort example:Starting point:I3 6 4 1 5 7 3 2* Splits 幅3 6 4 1|5 7 3 2jSplit in two：(36(4 -I5 73 2Base case:3 61 45 7)2 3 Sort on merge;13 4 6)2 3 5 7Sort on merge:1 2334567第二個(gè)例子稍微有趣一點(diǎn)，是一個(gè)如何用程序解數(shù)獨(dú)”游戲的例子。數(shù)獨(dú)”就是在一個(gè)9*9 的大九宮格內(nèi)

32、有9個(gè)3*3的小九宮格。里面有些格子已經(jīng)填入了數(shù)字，玩家必須在剩下的 空格里也填入1到9的數(shù)字，使每個(gè)數(shù)字在每行、每列以及每個(gè)小九宮格內(nèi)只出現(xiàn)一次。這里作為舉例說明，我們考慮一個(gè)簡(jiǎn)單一點(diǎn)的情況:在一個(gè)4*4的格子里填入14的數(shù)字， 使其在每行、每列以及每個(gè)2*2的格子里只出現(xiàn)一次。解數(shù)獨(dú)游戲的算法可以有很多種。如果是人來解，大概會(huì)按照上圖的次序依次填入1,2,3 到相應(yīng)的格子當(dāng)中。每填入一個(gè)新數(shù)字，都會(huì)重新按規(guī)則評(píng)估周圍的空格，看能否按現(xiàn)有情 況再填入一些數(shù)字。這個(gè)方法當(dāng)然沒錯(cuò)，不過看上去不太容易并行化。下面介紹一個(gè)按照 recursive splitting”的方法可以很容易做到并行化的解法

33、。1）首先，將二維的數(shù)獨(dú)格子展開成一個(gè)一維的數(shù)組。已經(jīng)有數(shù)字的地方是原來的數(shù)字， 空格子的地方填上、0。2）接下來，從前到后對(duì)數(shù)組進(jìn)行掃描。第一格是3，已經(jīng)有數(shù)字了，跳過。移動(dòng)搜索指 針到下一格。3）第二格是0，意味著我們需要填入一個(gè)新的數(shù)字。這個(gè)新的數(shù)字有4種可能性：1，2,3， 4。所以創(chuàng)建4個(gè)新的搜索分支：4）接下來根據(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)

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

35、ine模式的概念看上去很容易理解，可是也不是每一個(gè)人都能一下子理解的那么透徹 的。例如有這樣一個(gè)問題：我們有一個(gè)for循環(huán)，循環(huán)體是一條有3個(gè)stage的pipeline， 每個(gè)stage的運(yùn)行時(shí)間分別是10，40，和10個(gè)CPU的時(shí)鐘間隔。請(qǐng)問這個(gè)for循環(huán) 執(zhí)行N次大概需要多長時(shí)間（N是一個(gè)很大的數(shù)）？ TOC o 1-5 h z 60*N10*N6040*N請(qǐng)仔細(xì)思考并選擇一個(gè)答案。：-）2.7 Geometric decomposition接下來這兩個(gè)算法模式看上去都顯得比較特殊化，只針對(duì)某些特定的應(yīng)用類型?！癎eometric decomposition”說的是對(duì)于一些線性的數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組），我們可以把 數(shù)據(jù)切分成幾個(gè)連續(xù)的子集。因?yàn)檫@種切分模式看上去和把一塊幾何區(qū)域切分成連續(xù)的幾塊 很類似，我們就把它叫做Geometric decomposition”。最常用的例子是分塊矩陣的乘法。例如，為了計(jì)算兩個(gè)矩陣A，B的乘法。我們可以把他們 切分成各自可以相乘的小塊。加4“一|聆 日皿I/L A.B H 七 B結(jié)果矩陣當(dāng)然也是分塊的:結(jié)果矩陣每一分塊的計(jì)算按照如下公式進(jìn)行:-瑚例如：C=.4吐T n FU 叫,*升此1切最終的結(jié)果就是:下面這幅圖顯示了兩個(gè)4*4的分塊矩陣A，B進(jìn)行乘法時(shí)，計(jì)算結(jié)果矩陣C的某