202
多核時代：並行程序設計探討（9）——數據分解模式Data Decomposition
Data Decomposition
1.1 問題
如何將待解決的問題的數據分解為能夠並行運行的數據單元（units）？
1.2 上下文
並行算法的設計者必須首先詳細了解待解決的問題，除此之外，還必須識別如下幾個關鍵因素：
1）計算強相關的部分：待解決問題中的哪部分需要進行大量運算；
2）關鍵數據結構：主要是對什麼數據進行運算；如何進行運算。
當基本問題理解後，設計師必須考慮解決問題的需要完成哪些任務以及這些任務中包含哪些數據。為了創建並行算法，關鍵不是要進行哪種分解，而是首先從哪種分解開始，任務分解和數據分解都要進行。
什麼情況下該首先采用基於數據的分解方式呢？如果存在以下場景，則從數據分解開始時比較好的選擇：
1）待解決問題中計算強相關的部分都是圍繞數據進行組織的；
2）同樣的操作應用到數據結構的不同部分；
1.3 考慮因素
1.3.1 靈活
此時考慮靈活性主要是為了能夠讓設計能夠滿足不同的實現需求，這裏的實現就是具體采用的技術，例如采用Java編程，采用多CPU的小型機運行等，如果客戶不強製要求，在這個階段就不要限製這些。當然如果問題裏麵本身已經包含了這種實現，那就必須考慮這種實現的限製了。例如客戶要求隻能運行在小型機上麵，那麼設計的時候就需要考慮小型機的特點對人物分解的影響了。
1.3.2 有效
並行程序隻有在隨著並行計算機的規模增大時效率能夠按比例增長才有意義。對於任務分解來說，這就意味著我們需要足夠的任務來使得所有計算機都處於忙碌的狀態。
通過使每個任務有足夠的工作（Work）來彌補管理任務間的依賴帶來的效率損失才能達到這點。當然，效率提升會帶來靈活性的降低。
1.3.3 簡單
再怎麼好的程序也要人維護吧，所以再怎麼複雜怎麼好都要考慮怎麼維護。
以上三種因素互相製約，具體怎麼平衡，還是要看設計師的水平。
1.4 解決方法
如果已經基於任務進行了分解，則可以針對每個任務進行數據分解。如果定義良好且清晰的數據能夠和每個人物關聯，則數據分解就簡單了。
如果我們從數據分解開始進行分解，則這個時候還沒有任務，因此我們不能盯著任務進行分解了，而應該盯住最主要的數據結構，然後考慮如何將數據結構分解為數據塊，使得針對數據塊的操作能夠並行。一些常見的樣例如下：
1）線性數據結構：可以采用“分段方式”對數據進行分解，針對不同的數據段進行並行操作；如果是一個多維的數據結構，則可以采用多種方式進行分解：按列、按行、按數據塊。
2）遞歸數據結構：可以采用“遞歸方式”對數據進行分解，所謂“遞歸方式”就是指針對數據的一部分操作和針對整個數據的操作原理上是一樣的。典型的樣例就是“樹”這種數據結構了，每個子樹其實都是一顆樹，可以先對子樹進行計算，然後將子樹合並起來又是一顆樹，這樣就能夠通過並行來完成樹的計算了。
最後更新：2017-04-02 04:00:24