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

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

并行編程使用線程來使得多個操作能夠同時運行。并行編程主要包括應(yīng)用程序中線程設(shè)計，開發(fā)和部署以及線程間相互協(xié)調(diào)和各自的操作。

在下文中我們將討論怎樣分割適合線程化大小的編程任務(wù)來多任務(wù)化一個應(yīng)用程序。設(shè)計線程

不熟悉并行編程的開發(fā)者通常對例如面向?qū)ο蟮膫鹘y(tǒng)的編程模式感到非常適應(yīng)。在傳統(tǒng)的編程模式下，程序以預(yù)先定義的起點開始運行，譬如main函數(shù)，然后接連地做完一系列任務(wù)。如果程序依賴用戶交互，主要的工作代碼通常被封裝在一個處理用戶事件的循環(huán)里。

從一個約定事件開始，譬如點擊按鈕，程序運行一段已經(jīng)制定的順序行為，最終以等待用戶下個動作結(jié)束。

當(dāng)設(shè)計這樣的程序時，程序員喜歡一個相對簡單的編程模式因為在任意一段給定的時間內(nèi)只有一個事件發(fā)生。如果程序任務(wù)必須按某種方式順序運行，程序員必須在這些事件上特意安排順序。在這個過程的任一時刻，程序運行一步接著下一步，最終基于預(yù)先確定的參數(shù)到達一個預(yù)見的結(jié)果。

從這種線性的模式到并行編程模式，程序設(shè)計者必須重新思考程序的過程流。相比順序執(zhí)行序列限制，程序員應(yīng)該識別出那些能被并行化的行為。

要這樣做，他們必須把程序看作一組相互間有依賴關(guān)系的任務(wù)。把程序分解成一些獨立的任務(wù)并識別這些任務(wù)間的依賴性。這個過程被稱為分解。

一個問題有許多分解方式:按任務(wù)，數(shù)據(jù)，或者按數(shù)據(jù)流。下面的表總結(jié)了這些分解的形式。您將很快看到，這些不同分解形式對應(yīng)了不同的編程行為。分解類型設(shè)計評論任務(wù)不同的行為分配給不同的線程通常在GUI應(yīng)用數(shù)據(jù)多個線程對不同的數(shù)據(jù)集執(zhí)行同樣的操作通常在音頻處理，做圖和科學(xué)編程數(shù)據(jù)流一個線程的輸出是第二個線程的輸入需要特別關(guān)注消除開始和結(jié)束的延遲主要的分解形式總結(jié)任務(wù)分解

按功能分解一個程序被稱為任務(wù)分解。這是一種實現(xiàn)并行執(zhí)行最簡單的方式。使用這種方法，每個任務(wù)被按目錄分類。

如果它們中的兩個能同時運行，它們會被程序員按此調(diào)度。以這種方式并行運行任務(wù)通常需要對每個函數(shù)做小量修改來避免沖突，并指出這些任務(wù)已經(jīng)不再連續(xù)。

以園藝工作舉例，任務(wù)分解會建議園丁按工作本身的屬性分配任務(wù)：如果兩個園丁到達一個客戶家，一個修剪草坪，另一個鏟除雜草。修剪草坪和鏟除雜草是兩個被分開的功能。

要完成這兩個功能，園丁們需要確保他們之間相互協(xié)調(diào)，這樣鏟除雜草的園丁就不會坐在待修剪草坪的中間。

舉個編程的例子，一個任務(wù)分解的典型案例是文字處理軟件，譬如微軟的Word。當(dāng)用戶打開一個很長的文檔的時候，他（她）能夠馬上開始輸入文字。當(dāng)用戶輸入文字時，文檔分頁在后臺發(fā)生，于是他（她）能夠很容易地看到狀態(tài)欄中頁數(shù)的增加。

文檔輸入和分頁是兩個獨立的任務(wù)，程序員按功能將它們分開來并行運行。如果程序員沒有這樣設(shè)計，用戶將不得不在能夠輸入任何文字之前等待整個文檔被分頁。有些朋友可能回憶起這種現(xiàn)象在早期的個人電腦文字處理器中非常常見。數(shù)據(jù)分解

數(shù)據(jù)分解，也被認為是數(shù)據(jù)級并行，將任務(wù)按它們處理的數(shù)據(jù)進行分解，而不是按照任務(wù)本身的性質(zhì)。使用數(shù)據(jù)分解的程序通常有許多線程在執(zhí)行同樣的任務(wù)，只是處理的數(shù)據(jù)項不同。

舉個例子，假設(shè)在一個大的電子數(shù)據(jù)表里計算值。相比一個線程執(zhí)行所有的計算，數(shù)據(jù)分解會建議有兩個線程，每個執(zhí)行一半的計算量，或者n個線程執(zhí)行1/n的工作量。

如果園丁應(yīng)用數(shù)據(jù)分解來分解他們的任務(wù)，他們兩個會同時修剪一半的草坪，然后兩個人分別鏟除一半的雜草。在計算領(lǐng)域，決定哪一種分解形式更高效取決于系統(tǒng)的限制。

舉例說，如果需要修剪草坪的地塊非常小以至于沒必要有兩個人來修剪草坪，修剪草坪這個任務(wù)最好只被分配給一個園丁做，那么任務(wù)分解在這一步是最好的選擇。數(shù)據(jù)分解或許適用于其它的任務(wù)序列，譬如當(dāng)修剪草坪完成后，兩個園丁并行地來鏟除雜草。

隨著處理器核心數(shù)目的增加，數(shù)據(jù)分解使得任務(wù)處理規(guī)模增加。這允許在同樣的時間內(nèi)做更多的工作。3)負載均衡表示任務(wù)在多個線程間的分配，因此他們都處理基本同樣的工作量。4)可擴展性是當(dāng)軟件在更先進的系統(tǒng)上運行時高效利用許多線程的挑戰(zhàn)。譬如，如果一個程序被編寫來充分利用四核處理器，當(dāng)它在一個八核處理器上運行時它是否能適當(dāng)?shù)財U展？

上述每個問題都必須被仔細地處理來最大化程序的性能。并行編程模式

對于多年編寫面向?qū)ο蟪绦虻某绦騿T，他們使用設(shè)計模式來邏輯地設(shè)計他們的應(yīng)用程序。并行編程和面向?qū)ο缶幊虥]有什么不同，并行編程問題通常對應(yīng)于許多知名的編程模式之一。

下面的表格顯示了一些常見的并行編程模式和他們對應(yīng)的上述分解類型。模式分解任務(wù)級并行任務(wù)分離并戰(zhàn)勝任務(wù)/數(shù)據(jù)幾何分解數(shù)據(jù)流水線數(shù)據(jù)流波陣面數(shù)據(jù)流常見的并行編程模式

在這部分，我們將提供每種模式及其適用的問題種類的簡要概述，包括：1)任務(wù)級并行編程模式。在許多情況下，完成并行執(zhí)行的最佳方法是直接關(guān)注任務(wù)本身。在這種情況下，任務(wù)級并行模式最合適。這種模式下，問題被分解成一組獨立操作的任務(wù)。通常移除任務(wù)間的依賴性或使用復(fù)制來分離依賴性是必要的。適合這種模式的問題包括線程間沒有依賴性，或線程間的依賴性可從每一個線程中移除。2)分而治之模式。在分而治之模式中，問題被分成許多并行的子問題。每個子問題被單獨解決。當(dāng)每個子問題被解決時，結(jié)果合計到最后的結(jié)果中。因為每個子問題都能被單獨解決，這些子問題有可能被并行執(zhí)行。分而治之的方法被廣泛應(yīng)用于諸如合并分類的算法。這些算法非常容易被并行化。這種模式很好地處理了負載均衡，這點對緩存的有效利用非常重要。3)幾何分解模式。幾何分解模式基于正在解決問題的數(shù)據(jù)結(jié)構(gòu)的并行化。在幾何分解中，每個線程負責(zé)操作數(shù)據(jù)塊。這種模式可能適用于諸如熱流和聲波傳播之類的問題。4)流水線模式。流水線模式的意思類似于一條工廠的產(chǎn)品裝配線。這種尋找并發(fā)的方式使計算被分割成一系列階段，每個線程在不同的階段同時工作。5)波陣面模式。波陣面模式在處理二維網(wǎng)格中延對角線的數(shù)據(jù)元素時非常有用。如下圖