【正文】 任務(wù)的分配 :任務(wù)映射 ? 對很多的問題來說，在處理器。同樣的，為了均衡負載，有時候會把關(guān)系密切（需要很多的交互）的任務(wù)分配到不同的處理器 ? 由于這種沖突的存在，使得任務(wù)的分配變的更像一種藝術(shù)，而不是技術(shù)。比如，最小化處理器間交互可以用下面的方法很容易的達到：將需要交互的子任務(wù)分配到同一個處理器上。給出一個子任務(wù)集和一個可用處理器集，有很多種可能的方法來在它們之間建立某種映射關(guān)系，為了判斷哪種映射更好，我們需要使用下面的評價標準： – 分配給每個處理器的計算任務(wù)應(yīng)該均衡，這樣才能減少處理器因為等待其他處理器完成計算任務(wù)而造成的空閑； – 不同處理器之間的交互應(yīng)該最少，這樣處理器可以用更多的時間去完成有效的工作。 ? 快速排序也可以采用對輸入數(shù)據(jù)進行分解的方法，對快速排序采用輸入數(shù)據(jù)分解以及遞歸分解的方法可以得到一個更為高效的算法 任務(wù)的分配 :任務(wù)映射 ? 上一節(jié)中討論的分解算法可以用來識別出問題中可以提供的并行性，并且把計算分解為可以并行執(zhí)行的子任務(wù)。 ? 前面我們討論過快速排序算法，這個算法對大小為 n的序列排序時，可以產(chǎn)生 O(n)個子任務(wù)，但由于任務(wù)之間的依賴關(guān)系和任務(wù)分配的不均勻性，有效的并行性相當有限。 混合分解方法 ? 對問題進行任務(wù)分解需要靈活的應(yīng)用上面的方法。對有些問題來說，對輸入數(shù)據(jù)進行劃分效果比較好，而對有些問題，對輸出數(shù)據(jù)（計算結(jié)果）進行劃分要更好一些。 – 對輸出數(shù)據(jù)進行劃分 – 對中間數(shù)據(jù)進行劃分 – 對輸入數(shù)據(jù)進行劃分 數(shù)據(jù)分解 ? 一般的來說，當我們需要決定對數(shù)據(jù)如何劃分或者是對那些數(shù)據(jù)進行劃分時，我們需要看哪一種劃分能夠得到一個最好的（或者最簡單的）計算劃分。第一個步驟中，對計算操作的數(shù)據(jù)（或稱為域）進行劃分，第二個步驟根據(jù)數(shù)據(jù)的劃分來將對應(yīng)的計算組織成相應(yīng)的子任務(wù)。 數(shù)據(jù)分解 ? 對那些具有大型數(shù)據(jù)結(jié)構(gòu)的算法來說，數(shù)據(jù)分解是一種非常有用的方法。注意與前面的并行快速排序算法相反，這個分 治算法更多的計算時間花費在結(jié)果的組合階段。改寫后的算法如下（遞歸算法）： ? Minimum(A, n) { if (n == 1) return A[0]； lmin = Minimum(A, n/2)； rmin = Minimum(A+n/2,nn/2)； if (lmin rmin) return lmin； else return rmin； } ? 這個算法很好理解，思路與上面的快速排序幾乎一樣。 i++) if (A[i] min) min = A[i]； return min； } 遞歸分解 ? 這個算法本身沒有表現(xiàn)出任何的并行性（實際上與 min的使用有關(guān)）。下面的串行算法對 A采取逐個掃描的方法： ? Minimum(A, n) { min = A[0]； for (i=1。 遞歸分解 ? 遞歸分解處理的問題（的串行算法）并不一定是遞歸的。算法開始時，只有一個序列（樹的根節(jié)點），我們用一個處理器來完成對它的第一次分割。從上面的圖可以看出，對任務(wù)樹的每一層，每個子任務(wù)的繼續(xù)分割是可以并行執(zhí)行的，而且它們互相獨立。 遞歸分解 遞歸分解 ? 其中的深色的元素為選中的軸元素。對得到的子序列遞歸地進行上面的分割過程，然后用經(jīng)過排序的子序列組合成最后的結(jié)果序列 A39。快速排序算法是一種分治的算法。分 治策略表現(xiàn)出一種自然的并行性。這種方法將任務(wù)分解為獨立的子任務(wù)，這個分解的過程會遞歸的進行。 ? 其中的遞歸分解和數(shù)據(jù)分解可以被看成是相對通用的分解方法，因為它們可以用來對大多數(shù)的問題進行任務(wù)分解，而搜索分解要特殊一些，它只能應(yīng)用于某些特定類型的問題。 ? 下面介紹幾種用于任務(wù)分解的常用的方法。如何平衡沖突是并行算法設(shè)計中的藝術(shù)。交互少意味著處理器可以更專心的完成任務(wù)本身而不是其它由于通信和同步帶來的額外計算和等待。并行度越高意味著這個分解后的任務(wù)可以在越多的處理器上并行的執(zhí)行。對這樣的問題，我們需要將總的計算任務(wù)進行分解為一個可以并行執(zhí)行的子任務(wù)集，這個過程稱為任務(wù)分解。對這樣的任務(wù)圖，各個任務(wù)可以在多個處理器上進行調(diào)度，從而使得問題得以并行的完成。 分解技術(shù) ? 設(shè)計并行算法的一個基本的步驟是描述完成給定任務(wù)所需要的計算，并把這些計算分解為可以并行執(zhí)行的子任務(wù)集。 混合并行 ? 很多的問題中的并行性表現(xiàn)為數(shù)據(jù)并行性，任務(wù)并行性和流水并行性的混合，某個問題表現(xiàn)出的流水并行性的數(shù)量通常獨立于問題的規(guī)模，而任務(wù)和數(shù)據(jù)并行性則相反，他們通常會隨問題規(guī)模的增長而增長。在流水線上，計算的并行性表現(xiàn)為：每個處理器上運行一個不同的程序，它們構(gòu)成一個完整的處理流程，每個處理器把自己處理完的數(shù)據(jù)馬上傳遞給（邏輯上）的下一個處理器。 流水并行 ? 流水并行性是指在同一個數(shù)據(jù)流上同時的執(zhí)行多個程序（后續(xù)的程序處理的是前面程序處理過的數(shù)據(jù)流）。這種并行性表現(xiàn)為子任務(wù)的并行執(zhí)行，因此被稱為任務(wù)并行性。 任務(wù)并行 任務(wù)并行 ? 圖中的每個節(jié)點表示一個需要被計算的表（計算子任務(wù)），節(jié)點間的箭頭給出了任務(wù)間的依賴關(guān)系。然后在這些表上進行 Join操作，更詳細的說，數(shù)據(jù)庫將求出前兩個表的交集，從而得到 1996款的 Accord車的表，同時，將求出后兩個表的并，得到綠色或黑色的車的表，最后，用這兩個表求交集，就得到了最后的數(shù)據(jù)。 任務(wù)并行 ? 如果需要做如下的查詢： Select all where （（ MODEL=“Accord” AND YEAR=“1996”） AND （ COLOR=“Green” OR COLOR=“Black”））； ? 這個查詢尋找數(shù)據(jù)庫中所有 1996年產(chǎn)的綠色或黑色的Accord車的資料。數(shù)據(jù)并行問題的一個突出特點是對大多數(shù)的這類問題，數(shù)據(jù)并行性的程度（可以并行進行數(shù)據(jù)并行的操作數(shù)目）隨著問題規(guī)模的增加而增大，這意味著對于這類問題，可以用較多的處理器來有效的處理更大規(guī)模的問題。 ? 這種類型的并行性表現(xiàn)為：并行的在不同的數(shù)據(jù)上進行相同的操作，稱為 數(shù)據(jù)并行性 。下面是兩種常用調(diào)度模式： ? 經(jīng)理 /雇員模式 ? 非集中模式 wwwwwwwpppppp經(jīng) 理員 工映射判據(jù) ? 采用集中式負載平衡方案，是否存在通訊瓶頸？ ? 采用動態(tài)負載平衡方案，調(diào)度策略的成本如何？ 映射判據(jù) ? 1）如果采用集中式負載平衡方案，是否檢查了中央管理者不會成為瓶頸？ ? 2）如果采用動態(tài)負載平衡方案，是否衡量過不同策略的成本？ ? 3）如果采用概率或循環(huán)指派法，是否有足夠多的任務(wù)？一般地，任務(wù)數(shù)應(yīng)不少于處理器數(shù)的 10倍。在非集中模式中結(jié)束檢測則比較困難，因為沒有一個進程知道全局的情況。在經(jīng)理 /雇員模式中，經(jīng)理可以判斷雇員是否都空閑了。 ? 結(jié)束檢測 任務(wù)調(diào)度算法需要一種機制來檢測整個問題的計算何時結(jié)束。經(jīng)理 /雇員模式的缺點是經(jīng)理進程容易成為系統(tǒng)的瓶頸。在此模式中，雇員被分成不相交的集合，每個集合有一個小經(jīng)理。使用預(yù)取方法（以使計算和通信重疊）可以提高效率。常用的調(diào)度模式有經(jīng)理/雇員模式和非集中模式。 ? 總之，局部算法代價小，但當負載變化大時調(diào)整很慢；概率方法代價小，可擴展性好，但通信代價可能較大，且只適用于任務(wù)數(shù)遠多于處理器數(shù)的情況；循環(huán)映射技術(shù)是概率映射的一種形式，而概率方法比其它技術(shù)易于導(dǎo)致可觀的通信。它實際上是概率方法的一種形式。此法的優(yōu)點是低價和可擴展性好；缺點是要求跨處理器進行通信，并且只有當任務(wù)數(shù)遠遠多于處理器數(shù)時才能達到預(yù)期的效果。同時，遷移任務(wù)時往往通信量很大，而此方案只在局部遷移，有利于提高效率。反之，如果自己的負載重，而別的鄰居較空閑，則把自己的一部分負載遷給它。如果差異超過了某個閾值，就進行負載遷移。 ? 局部算法 局部負載平衡算法的思想是通過從近鄰遷入任務(wù)和向近鄰遷出任務(wù)來達到負載平衡。對于基于功能分解開發(fā)的算法，常常會產(chǎn)生一些由短暫任務(wù)組成的計算，它們只在執(zhí)行的開始與結(jié)束時需要與別的任務(wù)協(xié)調(diào)，此時可用任務(wù)調(diào)度算法進行任務(wù)分配。 對于某些基于域分解技術(shù)開發(fā)的算法，它們有固定數(shù)目的等尺寸的任務(wù)，通信結(jié)構(gòu)化強，此時映射較簡單。為了達到以上目的，可采用以下策略： 1）把能夠并發(fā)執(zhí)行的任務(wù)放在不同的處理器上以增加并行度； 2）把需頻繁通信的任務(wù)臵于同一處理器上以提高局部性。 映射 ? 方法描述 ? 負載平衡算法 ? 任務(wù)調(diào)度算法 ? 映射判據(jù) 方法描述 ? 映射 階段的任務(wù)是指定每個任務(wù)到哪個處理器上去執(zhí)行。 ? 6）如果組合減少了并行執(zhí)行的機會，是否已證實現(xiàn)在的并發(fā)性仍能適應(yīng)目前和將來的并行機？ ? 7）在不導(dǎo)致負載不平衡，不增加軟件工程代價和不減少可擴展性的前提下，任務(wù)數(shù)能否再進一步減少？在其它條件相同時，創(chuàng)建較少的粗粒度任務(wù)的算法通常是高效的。這幾個目的有時是相互矛盾的，要權(quán)衡其利弊。 ? 組合時的另一個問題是要盡量減少軟件工程的代價，尤其是并行化一個串行程序時應(yīng)盡量避免程序代碼的大量修改。粒度可由編譯或運行時的參數(shù)控制?？捎梅治瞿Ｐ徒Y(jié)合實際經(jīng)驗討論最優(yōu)的任務(wù)數(shù)。組合時往往會使問題的任務(wù)數(shù)的變化范圍受到限制。 重復(fù)計算 ? 示例：二叉樹上 N個處理器求 N個數(shù)的全和，要求每個處理器均保持全和。如果在每一級每個處理器均接收兩個數(shù)據(jù)，求和后再發(fā)送給上一級的兩個處理器，那么經(jīng)過 步后，每個處理器中就都得到了 N個數(shù)的全和。 重復(fù)計算 ? 示例：二叉樹上 N個處理器求 N個數(shù)的全和，要求每個處理器均保持全和。一種方法是先自葉向根求和，得到結(jié)果后再自根向葉播送，共需 2 步。它是指采用多余的計算來減少通信和 /或整個計算時間。這時就需要權(quán)衡，看哪種方案更好。那么顯然應(yīng)該將 A和 B組合成一個大任務(wù)，以避免通信對它們并行執(zhí)行造成的影響。實際上，實際問題的各小任務(wù)之間的通信很可能是不均勻的。對圖（ b）也可進行相同的分析，但是圖（ b）中每個通信要傳遞兩個數(shù)據(jù)，因此總的通信開銷比圖（ a）大。同理，向其它三個方向的通信各需時間 S+t。假設(shè)圖（ a）的通信方式是方向相同的所有通信同時執(zhí)行。仔細思考我們會發(fā)現(xiàn)在上例中，圖（ b）的通信開銷可能比圖（ a）大。這正是增加粒度可以減少通信的原因。雖然每次通信要傳遞兩個數(shù)據(jù)，但是相對于圖（ a），通信的次數(shù)和通信量都大大減少了。如上圖（ a）所示，每個箭頭表示一次通信。如果把計算每個元素算作一個任務(wù)，則有 16個任務(wù)。 ? 以二維平面上的雅可比有限差分法 5點格式為例。因此一個計算單元的通信與計算之比隨任務(wù)尺寸的增加而減小。但是大量的任務(wù)可能會增加通信開銷和任務(wù)創(chuàng)建開銷。 方法描述 ? 組合是由抽象到具體的過程，是將組合的任務(wù)能在一類并行機上有效的執(zhí)行； ? 合并小尺寸任務(wù)，減少任務(wù)數(shù)。在組合階段，我們將重新考察劃分和通信階段所作的選擇，力圖得到一個在某一類并行機上能有效執(zhí)行的并行算法。此時可考慮重新安排通信和計算的順序以改善這種情況。此時可試用分治策略來開發(fā)并行性。此時應(yīng)設(shè)法將全局通信換成局部通信。 通訊判據(jù) ? 所有任務(wù)是否執(zhí)行大致相當?shù)耐ㄓ?? ? 是否盡可能的局部通訊？ ? 通訊操作是否能并行執(zhí)行 ? ? 同步任務(wù)的計算能否并行執(zhí)行？ 通訊判據(jù) ? 1）所有任務(wù)是否執(zhí)行大致同樣多的通信？若不是，所設(shè)計的算法的可擴展性可能會不好。 全局通訊 ? 通訊非局部的 ? 例如： – All to All – MasterWorker 5 3 7 2 1 結(jié)構(gòu)化通訊 ? 每個任務(wù)的通訊模式是相同的； ? 下面是否存在一個相同通訊模式？ 非結(jié)構(gòu)化通訊 ? 沒有一個統(tǒng)一的通訊模式 ? 例如：無結(jié)構(gòu)化網(wǎng)格 非結(jié)構(gòu)化通訊 ? 非結(jié)構(gòu)化通信對算法設(shè)計的前期不會造成實質(zhì)性的困難，但會使任務(wù)組合和處理器映射更為復(fù)雜。這樣就可以避免全局通信，并提高算法的并行度。 全局通訊 ? 采用分治策略可以開拓求和的并行性： 上式右邊的兩個求和可以同時執(zhí)行，并且每一個仍可按同樣的方式進一步分解。 例如我們希望計算 ? 為此，我們使用一個根進程 S負責(zé)從各進程一次接收一個值（ xi）并進行累加。 局部通訊 ? 通訊限制在一個鄰域內(nèi) 全局通訊 ? 在全局通信中，有很多任務(wù)參與交換數(shù)據(jù)。如果采用 5點格式，迭代公式為 ? 假設(shè)在二維網(wǎng)格上計算，并且處于 (i,j)位臵上的處理器負責(zé)計算 xij。 局部通訊 ? 當一個任務(wù)僅要求與鄰近的其它任務(wù)通信時，就呈