計(jì)算分解

數(shù)據(jù)分解

搜索分解

遞歸分解

混合分解方法

針對(duì)要處理的問題靈活運(yùn)動(dòng)數(shù)據(jù)分解、搜索分解和遞歸分解

任務(wù)映射與負(fù)載均衡

在將計(jì)算分解為多個(gè)可以并行處理的子任務(wù)后，下一步是將子任務(wù)分配給可用的處理器來處理。給出一個(gè)子任務(wù)集合可用處理器集，那么怎么來判斷如何分配，即建立映射的方式是最好的呢？

• 分配給每個(gè)處理器的計(jì)算任務(wù)應(yīng)該均衡，這樣才能減少處理器等待其他處理器處理而造成的空閑
• 不同處理器直接的交互減少
  對(duì)很多的問題來說，在處理器中均勻分配計(jì)算任務(wù)并不一定能保證所有處理器都被有效的使用。對(duì)具有依賴關(guān)系的任務(wù)來說，尤其如此。比如采用遞歸分解的快速排序算法，遞歸樹中每一層的計(jì)算量都是O(n)，但如果我們將每一層的任務(wù)分配給一個(gè)不同的處理器，這樣看起來每個(gè)處理器具有相同的計(jì)算量，但由于下層的任務(wù)需要在上層的任務(wù)結(jié)束后完成，所以，實(shí)際上這種分配導(dǎo)致了全局的串行計(jì)算。因此，任務(wù)之間的依賴關(guān)系是任務(wù)分配的主要約束關(guān)系，在調(diào)度的時(shí)候必須考慮這一點(diǎn)。

負(fù)載平衡技術(shù)

• 靜態(tài)負(fù)載平衡
• 動(dòng)態(tài)負(fù)載平衡
  簡(jiǎn)單的選擇負(fù)載平衡的原則就是：如果能提前預(yù)知任務(wù)分布規(guī)模和情況的則用靜態(tài)分配，這樣實(shí)現(xiàn)過程簡(jiǎn)單，而對(duì)于只能在任務(wù)啟動(dòng)后分配的任務(wù)或者是在任務(wù)執(zhí)行過程中又不斷產(chǎn)生任務(wù)的，則采用動(dòng)態(tài)分配。

靜態(tài)分解

數(shù)組分步策略--塊分布
當(dāng)數(shù)組的每個(gè)元素相關(guān)的計(jì)算是均衡的時(shí)候，我們可以采用簡(jiǎn)單的塊分布策略：為每個(gè)處理器分配相同數(shù)量的數(shù)組元素。
例子：矩陣乘法

數(shù)組分步策略--塊輪轉(zhuǎn)分布