606
搜狐
多核時代：並行程序設計探討（8）——任務分解模式Task Decomposition
Task Decomposition
從本章開始我們就正式來介紹每個模式了，參考設計模式的做法，每個模式我們都按照如下的內容進行介紹：問題（Problem）、上下文（context）、考慮因素（Forces）、解決方法（Solutions）。至於樣例，就請各位看官直接看原文了。
1.1 問題
如何將待解決的問題分解為能夠並行運行的“任務（task）”？
“任務”這個詞本身是比較概念化的，沒法精確衡量，因此分解得是否合理、是否優秀就要看設計師的水平了，但以我個人的經驗，分解時至少要保證任務是一個級別的。例如建房子，你可以分解為設計、建造、裝修三個任務，建造又可以分為打地基、框架建造、砌牆（僅供舉例用，專業人士勿笑）等任務，但不要把設計和打地基甚至安裝煤氣管道都算作一個級別的任務。
1.2 上下文
所有的並行算法設計都開始於同一個起點：對問題很好的理解。設計師必須理解問題中計算強相關的部分、關鍵數據結構，以及數據如何用作問題的解決的。
接下來就是識別出組成問題的任務、以及任務包含的數據，本質上來說每個並行算法都包含一組能夠並行運行的任務，關鍵的挑戰就在於找到這些任務然後設計出一個算法讓這些任務並行運行。
有的情況下，問題本身就天然的分解為一組相互獨立的任務，這種情況就比較容易采用基於任務分解（task-based decomposition）的方式開始進行分解；而有的情況下，問題很難分解為獨立的任務，這種情況下采用基於數據分解（Data-Based decomposition）是更好的選擇。
通常情況下並不是很容易看出應該采用哪種方法，這個時候就要兩種都考慮。但無論哪種情況，最後都要輸出能夠並行運行的任務。
1.3 考慮因素
1.3.1 靈活
此時考慮靈活性主要是為了能夠讓設計能夠滿足不同的實現需求，這裏的實現就是具體采用的技術，例如采用Java編程，采用多CPU的小型機運行等，如果客戶不強製要求，在這個階段就不要限製這些。當然如果問題裏麵本身已經包含了這種實現，那就必須考慮這種實現的限製了。例如客戶要求隻能運行在小型機上麵，那麼設計的時候就需要考慮小型機的特點對人物分解的影響了。
1.3.2 有效
並行程序隻有在隨著並行計算機的規模增大時效率能夠按比例增長才有意義。對於任務分解來說，這就意味著我們需要足夠的任務來使得所有計算機都處於忙碌的狀態。
通過使每個任務有足夠的工作（Work）來彌補管理任務間的依賴帶來的效率損失才能達到這點。當然，效率提升會帶來靈活性的降低。
1.3.3 簡單
再怎麼好的程序也要人維護吧，所以再怎麼複雜怎麼好都要考慮怎麼維護。
以上三種因素互相製約，具體怎麼平衡，還是要看設計師的水平。
1.4 解決方法
任務分解的兩個關鍵點：
1、保證任務間足夠獨立，這樣花費很小的代價就可以管理任務間的依賴關係；
2、保證任務能夠均勻的分布在所有的可執行單元上，這樣能夠充分利用係統性能；
任務分解的步驟：
1）首先識別盡可能多的任務，因為識別出很多任務後再合並比識別很少的任務再分解要容易得多。
2）識別出任務後，接下來就要分析任務中包含的數據的分解了，數據的分解在下一篇介紹。
那麼，哪些地方能夠發現任務呢？
1）函數調用：調用函數的地方就是一個任務，如果每個函數調用都作為一個任務，則這種分解方式又叫“函數分解”。這裏的函數是算法級的，不是代碼級的，例如書中給的樣例采用蒙特卡羅算法來進行圖像分析合成，其中蒙特卡羅算法就是一個函數，也可以理解為功能（英文都是function）。ss
2）算法循環：另外一個能夠找到函數的地方就是算法中的循環了。如果很多循環彼此獨立，這樣可以采用每個循環一個任務的分解方法，這種分解方法又叫做“循環分解”。
3）數據分解：若一個大的數據結構的不同部分分別被更新，則可以根據不同的數據塊來劃分任務，這種分解方法又叫做“數據分解”，後麵會詳細講解數據分解的方法。
最後更新：2017-04-02 04:00:24