淺談并行編程中任務(wù)分解模式

1、淺談并行編程中的任務(wù)分解模式      并行編程使用線程來(lái)使得多個(gè)操作能夠同時(shí)運(yùn)行。并行編程主要包括應(yīng)用程序中線程設(shè)計(jì)，開(kāi)發(fā)和部署以及線程間相互協(xié)調(diào)和各自的操作。      在下文中我們將討論怎樣分割適合線程化大小的編程任務(wù)來(lái)多任務(wù)化一個(gè)應(yīng)用程序。設(shè)計(jì)線程      不熟悉并行編程的開(kāi)發(fā)者通常對(duì)例如面向?qū)ο蟮膫鹘y(tǒng)的編程模式感到非常適應(yīng)。在傳統(tǒng)的編程模式下，程序以預(yù)先定義的起點(diǎn)開(kāi)始運(yùn)行，譬如main函數(shù)，然后接連地做完一系列任務(wù)。如果程序依賴用戶交

2、互，主要的工作代碼通常被封裝在一個(gè)處理用戶事件的循環(huán)里。      從一個(gè)約定事件開(kāi)始，譬如點(diǎn)擊按鈕，程序運(yùn)行一段已經(jīng)制定的順序行為，最終以等待用戶下個(gè)動(dòng)作結(jié)束。      當(dāng)設(shè)計(jì)這樣的程序時(shí)，程序員喜歡一個(gè)相對(duì)簡(jiǎn)單的編程模式因?yàn)樵谌我庖欢谓o定的時(shí)間內(nèi)只有一個(gè)事件發(fā)生。如果程序任務(wù)必須按某種方式順序運(yùn)行， 程序員必須在這些事件上特意安排順序。在這個(gè)過(guò)程的任一時(shí)刻，程序運(yùn)行一步接著下一步，最終基于預(yù)先確定的參數(shù)到達(dá)一個(gè)預(yù)見(jiàn)的結(jié)果。      從這種

3、線性的模式到并行編程模式，程序設(shè)計(jì)者必須重新思考程序的過(guò)程流。相比順序執(zhí)行序列限制，程序員應(yīng)該識(shí)別出那些能被并行化的行為。      要這樣做，他們必須把程序看作一組相互間有依賴關(guān)系的任務(wù)。把程序分解成一些獨(dú)立的任務(wù)并識(shí)別這些任務(wù)間的依賴性。這個(gè)過(guò)程被稱為分解。      一個(gè)問(wèn)題有許多分解方式: 按任務(wù)，數(shù)據(jù)，或者按數(shù)據(jù)流。下面的表總結(jié)了這些分解的形式。您將很快看到，這些不同分解形式對(duì)應(yīng)了不同的編程行為。分解類型設(shè)計(jì)評(píng)論任務(wù)不同的行為分配給不同的線程通常在GUI應(yīng)用數(shù)據(jù)多個(gè)線程對(duì)不同的數(shù)據(jù)集執(zhí)

4、行同樣的操作通常在音頻處理，做圖和科學(xué)編程數(shù)據(jù)流一個(gè)線程的輸出是第二個(gè)線程的輸入需要特別關(guān)注消除開(kāi)始和結(jié)束的延遲主要的分解形式總結(jié)任務(wù)分解      按功能分解一個(gè)程序被稱為任務(wù)分解。這是一種實(shí)現(xiàn)并行執(zhí)行最簡(jiǎn)單的方式。使用這種方法，每個(gè)任務(wù)被按目錄分類。      如果它們中的兩個(gè)能同時(shí)運(yùn)行，它們會(huì)被程序員按此調(diào)度。以這種方式并行運(yùn)行任務(wù)通常需要對(duì)每個(gè)函數(shù)做小量修改來(lái)避免沖突，并指出這些任務(wù)已經(jīng)不再連續(xù)。      以園藝工作舉例，任務(wù)分解會(huì)建議

5、園丁按工作本身的屬性分配任務(wù)：如果兩個(gè)園丁到達(dá)一個(gè)客戶家，一個(gè)修剪草坪，另一個(gè)鏟除雜草。修剪草坪和鏟除雜草是兩個(gè)被分開(kāi)的功能。      要完成這兩個(gè)功能，園丁們需要確保他們之間相互協(xié)調(diào)，這樣鏟除雜草的園丁就不會(huì)坐在待修剪草坪的中間。      舉個(gè)編程的例子，一個(gè)任務(wù)分解的典型案例是文字處理軟件，譬如微軟的Word。當(dāng)用戶打開(kāi)一個(gè)很長(zhǎng)的文檔的時(shí)候，他（她）能夠馬上開(kāi)始輸入文字。當(dāng)用戶輸入文字時(shí)，文檔分頁(yè)在后臺(tái)發(fā)生，于是他（她）能夠很容易地看到狀態(tài)欄中頁(yè)數(shù)的增加。  

6、0;   文檔輸入和分頁(yè)是兩個(gè)獨(dú)立的任務(wù)，程序員按功能將它們分開(kāi)來(lái)并行運(yùn)行。如果程序員沒(méi)有這樣設(shè)計(jì)，用戶將不得不在能夠輸入任何文字之前等待整個(gè)文檔被分頁(yè)。有些朋友可能回憶起這種現(xiàn)象在早期的個(gè)人電腦文字處理器中非常常見(jiàn)。數(shù)據(jù)分解      數(shù)據(jù)分解，也被認(rèn)為是數(shù)據(jù)級(jí)并行，將任務(wù)按它們處理的數(shù)據(jù)進(jìn)行分解，而不是按照任務(wù)本身的性質(zhì)。使用數(shù)據(jù)分解的程序通常有許多線程在執(zhí)行同樣的任務(wù)，只是處理的數(shù)據(jù)項(xiàng)不同。      舉個(gè)例子，假設(shè)在一個(gè)大的電子數(shù)據(jù)表里計(jì)算值。相比一個(gè)線程執(zhí)行所有的計(jì)

7、算，數(shù)據(jù)分解會(huì)建議有兩個(gè)線程，每個(gè)執(zhí)行一半的計(jì)算量，或者n個(gè)線程執(zhí)行1/n的工作量。      如果園丁應(yīng)用數(shù)據(jù)分解來(lái)分解他們的任務(wù)，他們兩個(gè)會(huì)同時(shí)修剪一半的草坪，然后兩個(gè)人分別鏟除一半的雜草。在計(jì)算領(lǐng)域，決定哪一種分解形式更高效取決于系統(tǒng)的限制。      舉例說(shuō)，如果需要修剪草坪的地塊非常小以至于沒(méi)必要有兩個(gè)人來(lái)修剪草坪，修剪草坪這個(gè)任務(wù)最好只被分配給一個(gè)園丁做，那么任務(wù)分解在這一步是最好的選擇。數(shù)據(jù)分解或許適用于其它的任務(wù)序列，譬如當(dāng)修剪草坪完成后，兩個(gè)園丁并行地來(lái)鏟除雜草。 &

8、#160;    隨著處理器核心數(shù)目的增加，數(shù)據(jù)分解使得任務(wù)處理規(guī)模增加。這允許在同樣的時(shí)間內(nèi)做更多的工作。      舉園丁的例子，假設(shè)有另外兩個(gè)園丁加入了工作。相比分配所有四個(gè)園丁到一個(gè)地塊工作，我們不如分配兩個(gè)新的園丁去另一個(gè)地塊，非常有效地增加我們總的任務(wù)處理量。      假設(shè)兩位新園丁和兩位老園丁能夠做同樣多的工作，兩個(gè)地塊的大小也是一樣的，我們已經(jīng)在同樣的時(shí)間內(nèi)把工作量翻倍了。數(shù)據(jù)流分解      許多

9、時(shí)候，當(dāng)分解一個(gè)問(wèn)題時(shí)，關(guān)鍵不是任務(wù)應(yīng)該做什么事情，而是數(shù)據(jù)在不同任務(wù)中怎樣傳遞。在這些情況下，數(shù)據(jù)流分解將問(wèn)題按數(shù)據(jù)在任務(wù)中傳遞的方式來(lái)分解。      生產(chǎn)者/消費(fèi)者問(wèn)題是數(shù)據(jù)流影響程序并行執(zhí)行能力的著名例子。這里，一個(gè)生產(chǎn)者任務(wù)的輸出，成為另一個(gè)消費(fèi)者的輸入。兩個(gè)任務(wù)被不同的線程執(zhí)行，直到生產(chǎn)者完成他的部分工作，消費(fèi)者不能開(kāi)始工作。      依然引用園丁的例子，一個(gè)園丁準(zhǔn)備工具，譬如他承擔(dān)為割草機(jī)加油，清掃剪刀等類似的任務(wù)來(lái)提供這些工具給另兩個(gè)園丁使用。直到這個(gè)準(zhǔn)備步驟基本結(jié)束，其他園丁

10、的園藝工作才能開(kāi)始。      由第一個(gè)任務(wù)引起的延遲為第二個(gè)任務(wù)產(chǎn)生一個(gè)暫停，在此之后兩個(gè)任務(wù)才能并行運(yùn)行。在計(jì)算機(jī)領(lǐng)域這樣的模式經(jīng)常發(fā)生。     在常見(jiàn)的編程任務(wù)里，生產(chǎn)者/消費(fèi)者問(wèn)題在多個(gè)典型的場(chǎng)景發(fā)生。譬如，必須對(duì)讀文檔做回應(yīng)的程序就符合這種場(chǎng)景：文件的輸入/輸出結(jié)果成為下一步可能被線程化的工作的輸入。下一步直到讀完或讀到其他處理需要的足夠信息才會(huì)開(kāi)始執(zhí)行。另一個(gè)編程的例子是分析：一個(gè)輸入文件必須在后端操作之前被分析或者語(yǔ)義分析，譬如編譯器的代碼生成。生產(chǎn)者/消費(fèi)者問(wèn)題有許多需要注意的方面：1)

11、 如果這種模式?jīng)]有正確地執(zhí)行，消費(fèi)者和生產(chǎn)者間產(chǎn)生的依賴性會(huì)引起重大的延遲。一個(gè)性能敏感的設(shè)計(jì)需要充分理解依賴關(guān)系的性質(zhì)以減小延遲的影響。這也是為了避免消費(fèi)者線程空閑等待生產(chǎn)者線程的情況。2) 在完美的情況下，生產(chǎn)者和消費(fèi)者間的傳遞是完全"清潔"的，就像在文件分析器的例子中一樣。輸出是上下文相關(guān)的，消費(fèi)者不需要知道生產(chǎn)者的任何事情。然而在很多時(shí)候，生產(chǎn)者和消費(fèi)者并不享受如此干凈的任務(wù)分割，安排他們間的互動(dòng)需要非常仔細(xì)的計(jì)劃。3) 如果當(dāng)生產(chǎn)者完全做好后消費(fèi)者開(kāi)始加工，那么當(dāng)其他線程忙著工作時(shí)一個(gè)線程就保持空閑。這個(gè)問(wèn)題破壞了一個(gè)并行處理的重要目標(biāo)，那就是負(fù)載均衡以使得所有能

12、用的線程保持忙碌。由于線程間的邏輯關(guān)系，要保持線程平等地被占用非常困難。      下面，我們看看流水線模式，它允許開(kāi)發(fā)者以可升級(jí)的模式解決生產(chǎn)者/消費(fèi)者問(wèn)題。不同分解的含義      不同的分解具有不同的優(yōu)勢(shì)。如果目標(biāo)是使編程簡(jiǎn)便，任務(wù)能夠清楚地按功能分割，那么任務(wù)分解通常更合適。      數(shù)據(jù)分解增加了一些額外的代碼級(jí)復(fù)雜度，因此他專供數(shù)據(jù)非常容易分解而性能又非常重要的情況使用。     

13、線程化程序的最常見(jiàn)原因就是性能。在這種情況下，分解方式的選擇就更加困難。在許多情況下，選擇依賴于問(wèn)題的領(lǐng)域：一些任務(wù)明顯更適合于其中一種分解方式。      但是一些任務(wù)沒(méi)有明顯的偏向。譬如視頻流中的圖像處理。在幀與幀間沒(méi)有依賴的格式，你需要作出分解模式的選擇。他們應(yīng)該選擇任務(wù)分解么，那樣一個(gè)線程解碼，另一個(gè)線程配色，諸如此類？或者選擇數(shù)據(jù)分解，每個(gè)線程做一幀上的所有工作，然后一起開(kāi)始處理新的一幀？      回到園丁的例子：如果兩個(gè)園丁需要修整兩塊草坪和鏟除兩塊花園的雜草，他們應(yīng)該怎樣工作？是

14、應(yīng)該一個(gè)園丁只修剪草坪，也就是他們選擇基于任務(wù)的分解呢？還是兩個(gè)人應(yīng)該同時(shí)修剪草坪然后同時(shí)鏟除雜草？      在一些情況下，答案很快顯現(xiàn)。例如當(dāng)一個(gè)資源限制存在，譬如只有一個(gè)割草機(jī)。其它情況下每一個(gè)園丁都有一個(gè)割草機(jī)，答案只能通過(guò)仔細(xì)分析行為要素來(lái)得出。在園丁的例子中，任務(wù)分解看起來(lái)更好，因?yàn)槿绻挥幸粋€(gè)割草機(jī)在使用，開(kāi)始的割草時(shí)間就被節(jié)省了。      最終，你通過(guò)仔細(xì)的計(jì)劃和測(cè)試來(lái)為你的應(yīng)用程序使用并行編程作出正確的選擇。 根據(jù)經(jīng)驗(yàn)估計(jì)在你決定并行程序設(shè)計(jì)時(shí)比標(biāo)準(zhǔn)的單線程編程中扮演更加重要

15、的角色。你將面對(duì)的挑戰(zhàn)      使用線程通過(guò)允許兩個(gè)或多個(gè)行為同時(shí)發(fā)生使得你顯著改進(jìn)性能。然而，開(kāi)發(fā)者不能不認(rèn)識(shí)到線程增加了復(fù)雜性度量，需要細(xì)致的考慮來(lái)正確引導(dǎo)。      這種復(fù)雜度源于程序中多于一個(gè)行為發(fā)生的自身性質(zhì)。管理同步行為和他們可能的交互使你面對(duì)下面四種問(wèn)題：1) 同步是兩個(gè)或多個(gè)線程協(xié)調(diào)他們行為的過(guò)程。譬如，一個(gè)線程在繼續(xù)運(yùn)行前等待另一個(gè)完成任務(wù)。2) 交互代表與線程間交換數(shù)據(jù)相關(guān)的帶寬和延遲問(wèn)題。3) 負(fù)載均衡表示任務(wù)在多個(gè)線程間的分配，因此他們都處理基本同樣的工作量。4) 可

16、擴(kuò)展性是當(dāng)軟件在更先進(jìn)的系統(tǒng)上運(yùn)行時(shí)高效利用許多線程的挑戰(zhàn)。譬如，如果一個(gè)程序被編寫(xiě)來(lái)充分利用四核處理器，當(dāng)它在一個(gè)八核處理器上運(yùn)行時(shí)它是否能適當(dāng)?shù)財(cái)U(kuò)展？      上述每個(gè)問(wèn)題都必須被仔細(xì)地處理來(lái)最大化程序的性能。并行編程模式      對(duì)于多年編寫(xiě)面向?qū)ο蟪绦虻某绦騿T，他們使用設(shè)計(jì)模式來(lái)邏輯地設(shè)計(jì)他們的應(yīng)用程序。并行編程和面向?qū)ο缶幊虥](méi)有什么不同，并行編程問(wèn)題通常對(duì)應(yīng)于許多知名的編程模式之一。      下面的表格顯示了一些常見(jiàn)的并行編程模式

17、和他們對(duì)應(yīng)的上述分解類型。模式分解任務(wù)級(jí)并行任務(wù)分離并戰(zhàn)勝任務(wù)/數(shù)據(jù)幾何分解數(shù)據(jù)流水線數(shù)據(jù)流波陣面數(shù)據(jù)流常見(jiàn)的并行編程模式      在這部分，我們將提供每種模式及其適用的問(wèn)題種類的簡(jiǎn)要概述，包括：1) 任務(wù)級(jí)并行編程模式。在許多情況下，完成并行執(zhí)行的最佳方法是直接關(guān)注任務(wù)本身。在這種情況下，任務(wù)級(jí)并行模式最合適。這種模式下，問(wèn)題被分解成一組獨(dú)立操作的任務(wù)。通常移除任務(wù)間的依賴性或使用復(fù)制來(lái)分離依賴性是必要的。適合這種模式的問(wèn)題包括線程間沒(méi)有依賴性，或線程間的依賴性可從每一個(gè)線程中移除。2) 分而治之模式。在分而治之模式中，問(wèn)題被分成許多并行的子問(wèn)題。每個(gè)子問(wèn)題被單獨(dú)解決。當(dāng)每個(gè)子問(wèn)題被解決時(shí)，結(jié)果合計(jì)到最后的結(jié)果中。因?yàn)槊總€(gè)子問(wèn)題都能被單獨(dú)解決，這些子問(wèn)題有可能被并行執(zhí)行。分而治之的方法被廣泛應(yīng)用于諸如合并分類的算法。這些算法非常容易被并行化。這種模式很好地處理了負(fù)載均衡，這點(diǎn)對(duì)緩存的有效利用非常重要。3) 幾何分解模式。幾何分解模式基于正在解決問(wèn)題的數(shù)據(jù)結(jié)構(gòu)的并行化。在幾何分解中，每個(gè)線程負(fù)責(zé)操作數(shù)據(jù)塊。這種模式可能適用于諸如熱流和聲波傳播之類的問(wèn)題。4) 流水線模式。流水線模式的意思類似于一條工廠的