【正文】 ? 任務(wù)調(diào)度算法 任務(wù)調(diào)度算法的最關(guān)鍵之處是任務(wù)的分配策略。常用的調(diào)度模式有經(jīng)理/雇員模式和非集中模式。 ? 經(jīng)理 /雇員模式 在此模式中，有一個(gè)進(jìn)程（經(jīng)理）負(fù)責(zé)分配任務(wù)，每個(gè)雇員向經(jīng)理請(qǐng)求任務(wù)，得到任務(wù)后執(zhí)行任務(wù)。使用預(yù)取方法（以使計(jì)算和通信重疊）可以提高效率。 ? 這種方案的一種變體是 層次經(jīng)理 /雇員模式 。在此模式中，雇員被分成不相交的集合，每個(gè)集合有一個(gè)小經(jīng)理。雇員們從小經(jīng)理那里領(lǐng)取任務(wù)，小經(jīng)理從經(jīng)理處領(lǐng)取任務(wù)。經(jīng)理 /雇員模式的缺點(diǎn)是經(jīng)理進(jìn)程容易成為系統(tǒng)的瓶頸。 ? 非集中模式 它就是無(wú)中心管理者的分布式調(diào)度法。 ? 結(jié)束檢測(cè) 任務(wù)調(diào)度算法需要一種機(jī)制來(lái)檢測(cè)整個(gè)問(wèn)題的計(jì)算何時(shí)結(jié)束。否則，空閑的雇員們將永不停止地發(fā)出任務(wù)請(qǐng)求。在經(jīng)理 /雇員模式中，經(jīng)理可以判斷雇員是否都空閑了。所有的雇員都空閑了就意味著整個(gè)問(wèn)題的計(jì)算結(jié)束了。在非集中模式中結(jié)束檢測(cè)則比較困難，因?yàn)闆](méi)有一個(gè)進(jìn)程知道全局的情況。 任務(wù)調(diào)度算法 ? 任務(wù)放在集中的或分散的任務(wù)池中，使用任務(wù)調(diào)度算法將池中的任務(wù)分配給特定的處理器。下面是兩種常用調(diào)度模式： ? 經(jīng)理 /雇員模式 ? 非集中模式 wwwwwwwpppppp經(jīng) 理員 工映射判據(jù) ? 采用集中式負(fù)載平衡方案，是否存在通訊瓶頸？ ? 采用動(dòng)態(tài)負(fù)載平衡方案，調(diào)度策略的成本如何？ 映射判據(jù) ? 1）如果采用集中式負(fù)載平衡方案，是否檢查了中央管理者不會(huì)成為瓶頸？ ? 2）如果采用動(dòng)態(tài)負(fù)載平衡方案，是否衡量過(guò)不同策略的成本？ ? 3）如果采用概率或循環(huán)指派法，是否有足夠多的任務(wù)？一般地，任務(wù)數(shù)應(yīng)不少于處理器數(shù)的 10倍。 ? 4）如果要為一個(gè)問(wèn)題設(shè)計(jì)一個(gè) SPMD程序，是否考慮過(guò)基于動(dòng)態(tài)任務(wù)創(chuàng)建和消除的算法？ 小 結(jié) ? 劃分 – 域分解和功能分解 ? 通訊 – 任務(wù)間的數(shù)據(jù)交換 ? 組合 – 任務(wù)的合并使得算法更有效 ? 映射 – 將任務(wù)分配到處理器，并保持負(fù)載平衡 并發(fā)的類(lèi)型 ? 并行程序必須以某種形式給出任務(wù)的并行性，它們可以以下面的方式給出： – 數(shù)據(jù)并行 – 任務(wù)并行 – 流水并行 – 混合并行 數(shù)據(jù)并行 ? 考慮下面的矩陣加法： A， B， C都是 n n的矩陣，計(jì)算 C=A+B 為了計(jì)算 C的每個(gè)元素，需要進(jìn)行如下的計(jì)算： Ci,j=ai,j+bi,j 注意計(jì)算 C的每個(gè)元素的操作都是一次加法，只是操作數(shù)不同而已，而且，每個(gè)元素的計(jì)算都是獨(dú)立的，它們可以并行執(zhí)行。 ? 這種類(lèi)型的并行性表現(xiàn)為：并行的在不同的數(shù)據(jù)上進(jìn)行相同的操作，稱(chēng)為 數(shù)據(jù)并行性 。表現(xiàn)出這種并行性的問(wèn)題通常稱(chēng)為 數(shù)據(jù)并行 （的問(wèn)題）。數(shù)據(jù)并行問(wèn)題的一個(gè)突出特點(diǎn)是對(duì)大多數(shù)的這類(lèi)問(wèn)題，數(shù)據(jù)并行性的程度（可以并行進(jìn)行數(shù)據(jù)并行的操作數(shù)目）隨著問(wèn)題規(guī)模的增加而增大，這意味著對(duì)于這類(lèi)問(wèn)題，可以用較多的處理器來(lái)有效的處理更大規(guī)模的問(wèn)題。這是一種比較簡(jiǎn)單的并行方式，幸運(yùn)的是，在實(shí)際的應(yīng)用中，有很多有趣的問(wèn)題都是數(shù)據(jù)并行的。 任務(wù)并行 ? 如果需要做如下的查詢(xún)： Select all where （（ MODEL=“Accord” AND YEAR=“1996”） AND （ COLOR=“Green” OR COLOR=“Black”））； ? 這個(gè)查詢(xún)尋找數(shù)據(jù)庫(kù)中所有 1996年產(chǎn)的綠色或黑色的Accord車(chē)的資料。在關(guān)系數(shù)據(jù)庫(kù)中，這個(gè)查詢(xún)通常需要?jiǎng)?chuàng)建幾個(gè)中間表，一種可能的情形如下：一個(gè)表包含所有的Accord車(chē)數(shù)據(jù)，一個(gè)表包含所有 1996款的車(chē)，一個(gè)表包含所有綠色車(chē)，一個(gè)表包含所有的黑色車(chē)。然后在這些表上進(jìn)行 Join操作，更詳細(xì)的說(shuō)，數(shù)據(jù)庫(kù)將求出前兩個(gè)表的交集，從而得到 1996款的 Accord車(chē)的表，同時(shí)，將求出后兩個(gè)表的并，得到綠色或黑色的車(chē)的表，最后，用這兩個(gè)表求交集，就得到了最后的數(shù)據(jù)。上面的操作可以用下面的圖來(lái)形象的表示。 任務(wù)并行 任務(wù)并行 ? 圖中的每個(gè)節(jié)點(diǎn)表示一個(gè)需要被計(jì)算的表（計(jì)算子任務(wù)），節(jié)點(diǎn)間的箭頭給出了任務(wù)間的依賴(lài)關(guān)系。 ? 在上面圖中，只要所有必需的子任務(wù)已經(jīng)完成，后續(xù)子任務(wù)就可以進(jìn)行，因此，通常來(lái)說(shuō)，很多的子任務(wù)都可以并行的執(zhí)行。這種并行性表現(xiàn)為子任務(wù)的并行執(zhí)行，因此被稱(chēng)為任務(wù)并行性。任務(wù)并行性比數(shù)據(jù)并行性要復(fù)雜一些（實(shí)際上，用任務(wù)并行性完全可以描述數(shù)據(jù)并行性的問(wèn)題）。 流水并行 ? 流水并行性是指在同一個(gè)數(shù)據(jù)流上同時(shí)的執(zhí)行多個(gè)程序（后續(xù)的程序處理的是前面程序處理過(guò)的數(shù)據(jù)流）。流水并行性通常也被稱(chēng)為流水線。在流水線上，計(jì)算的并行性表現(xiàn)為：每個(gè)處理器上運(yùn)行一個(gè)不同的程序，它們構(gòu)成一個(gè)完整的處理流程，每個(gè)處理器把自己處理完的數(shù)據(jù)馬上傳遞給（邏輯上）的下一個(gè)處理器。這樣實(shí)際上形成了處理器間的一個(gè)流水線，因此稱(chēng)為 流水并行性 。 混合并行 ? 很多的問(wèn)題中的并行性表現(xiàn)為數(shù)據(jù)并行性，任務(wù)并行性和流水并行性的混合，某個(gè)問(wèn)題表現(xiàn)出的流水并行性的數(shù)量通常獨(dú)立于問(wèn)題的規(guī)模，而任務(wù)和數(shù)據(jù)并行性則相反，他們通常會(huì)隨問(wèn)題規(guī)模的增長(zhǎng)而增長(zhǎng)。通常情況下，任務(wù)并行性可以用來(lái)開(kāi)發(fā)粗粒度的并行性，而數(shù)據(jù)并行性用來(lái)開(kāi)發(fā)細(xì)粒度的并行性，因此，任務(wù)并行性和數(shù)據(jù)并行性的組合可以用來(lái)有效的開(kāi)發(fā)應(yīng)用在大量處理器上的并行算法。 分解技術(shù) ? 設(shè)計(jì)并行算法的一個(gè)基本的步驟是描述完成給定任務(wù)所需要的計(jì)算，并把這些計(jì)算分解為可以并行執(zhí)行的子任務(wù)集。對(duì)很多的問(wèn)題來(lái)說(shuō)，它們的任務(wù)圖都包含了足夠的并行性。對(duì)這樣的任務(wù)圖，各個(gè)任務(wù)可以在多個(gè)處理器上進(jìn)行調(diào)度，從而使得問(wèn)題得以并行的完成。但不幸的是，很多的問(wèn)題的任務(wù)圖中并不表現(xiàn)出如此豐富（或者稱(chēng)為直觀）的并行性，相反的，它們往往包含一個(gè)任務(wù)或者多個(gè)需要串行執(zhí)行的任務(wù)。對(duì)這樣的問(wèn)題，我們需要將總的計(jì)算任務(wù)進(jìn)行分解為一個(gè)可以并行執(zhí)行的子任務(wù)集，這個(gè)過(guò)程稱(chēng)為任務(wù)分解。一個(gè)好的任務(wù)分解應(yīng)該具有下面的特點(diǎn)： – 它應(yīng)該有很高的并行度。并行度越高意味著這個(gè)分解后的任務(wù)可以在越多的處理器上并行的執(zhí)行。 – 子任務(wù)間的交互（通信和同步）應(yīng)該盡可能的少。交互少意味著處理器可以更專(zhuān)心的完成任務(wù)本身而不是其它由于通信和同步帶來(lái)的額外計(jì)算和等待。 分解技術(shù) ? 很多情況下，這兩個(gè)要求會(huì)產(chǎn)生沖突，也就是說(shuō)，有很高的并行度的任務(wù)分解，通常需要子任務(wù)間的大量交互操作。如何平衡沖突是并行算法設(shè)計(jì)中的藝術(shù)。這一節(jié)中主要考慮如何提高子任務(wù)的并行度，關(guān)于子任務(wù)間的交互的討論在下一節(jié)進(jìn)行。 ? 下面介紹幾種用于任務(wù)分解的常用的方法。對(duì)不同的問(wèn)題，這些方法并不總是可行，而且也不一定會(huì)得到最有效的并行算法，但對(duì)很多問(wèn)題來(lái)說(shuō)，這些方法可以提供一個(gè)好的并行化的“著眼點(diǎn)”。 ? 其中的遞歸分解和數(shù)據(jù)分解可以被看成是相對(duì)通用的分解方法，因?yàn)樗鼈兛梢杂脕?lái)對(duì)大多數(shù)的問(wèn)題進(jìn)行任務(wù)分解，而搜索分解要特殊一些，它只能應(yīng)用于某些特定類(lèi)型的問(wèn)題。 遞歸分解 ? 遞歸分解通常用來(lái)對(duì)采用 Divideandconquer(分治 )方法的問(wèn)題進(jìn)行任務(wù)分解。這種方法將任務(wù)分解為獨(dú)立的子任務(wù)，這個(gè)分解的過(guò)程會(huì)遞歸的進(jìn)行。問(wèn)題的答案是所有的子任務(wù)的答案的組合。分 治策略表現(xiàn)出一種自然的并行性。 ? 考慮下面的問(wèn)題：對(duì) n個(gè)元素的序列 A進(jìn)行快速排序?？焖倥判蛩惴ㄊ且环N分治的算法。算法首先選取一個(gè)軸元素 x，然后把 A分成兩個(gè)子序列 A0和 A1，其中 A0中的所有元素小于 x,而 A1中的所有元素大于等于 x,這是算法的分割部分。對(duì)得到的子序列遞歸地進(jìn)行上面的分割過(guò)程，然后用經(jīng)過(guò)排序的子序列組合成最后的結(jié)果序列 A39。快速排序的過(guò)程可以用下面的圖來(lái)示例。 遞歸分解 遞歸分解 ? 其中的深色的元素為選中的軸元素。 ? 現(xiàn)在考慮如何根據(jù)算法的分 治特性來(lái)對(duì)快速排序算法進(jìn)行任務(wù)分解。從上面的圖可以看出，對(duì)任務(wù)樹(shù)的每一層，每個(gè)子任務(wù)的繼續(xù)分割是可以并行執(zhí)行的，而且它們互相獨(dú)立。因此對(duì)計(jì)算的分解實(shí)際上也是一棵樹(shù)。算法開(kāi)始時(shí)，只有一個(gè)序列（樹(shù)的根節(jié)點(diǎn)），我們用一個(gè)處理器來(lái)完成對(duì)它的第一次分割。分割完成后，我們得到了第一層中的2個(gè)子序列，對(duì)這兩個(gè)子序列的分割可以在兩個(gè)處理器上分別進(jìn)行，（如果序列足夠長(zhǎng)）樹(shù)中的第 i層中會(huì)出現(xiàn) 2i個(gè)子序列，它們可以由 2i個(gè)處理器獨(dú)立并行完成。 遞歸分解 ? 遞歸分解處理的問(wèn)題（的串行算法）并不一定是遞歸的。比如下面的問(wèn)題： n個(gè)元素的未排序序列 A，求 A的最小值。下面的串行算法對(duì) A采取逐個(gè)掃描的方法： ? Minimum(A, n) { min = A[0]； for (i=1。 in。 i++) if (A[i] min) min = A[i]； return min； } 遞歸分解 ? 這個(gè)算法本身沒(méi)有表現(xiàn)出任何的并行性（實(shí)際上與 min的使用有關(guān)）。一種可行的解決辦法是采用分治的策略來(lái)重新得到一個(gè)算法，然后采用遞歸分解的方法來(lái)開(kāi)發(fā)并行性。改寫(xiě)后的算法如下（遞歸算法）： ? 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； } ? 這個(gè)算法很好理解，思路與上面的快速排序幾乎一樣。上面算法的遞歸樹(shù)如下圖（對(duì) 8個(gè)元素的序列進(jìn)行操作）所示： 遞歸分解 遞歸分解 ? 現(xiàn)在對(duì)任務(wù)的分解就簡(jiǎn)單多了。注意與前面的并行快速排序算法相反，這個(gè)分 治算法更多的計(jì)算時(shí)間花費(fèi)在結(jié)果的組合階段。因此，這個(gè)算法的并行版本在執(zhí)行時(shí)，最開(kāi)始有 n個(gè)任務(wù)可以并行執(zhí)行（雖然不需要），然后可以并行執(zhí)行的任務(wù)依次減半（沿著樹(shù)往上走），到根節(jié)點(diǎn)時(shí)，只能由一個(gè)處理器執(zhí)行來(lái)的到最后的結(jié)果。 數(shù)據(jù)分解 ? 對(duì)那些具有大型數(shù)據(jù)結(jié)構(gòu)的算法來(lái)說(shuō)，數(shù)據(jù)分解是一種非常有用的方法。它可以分為兩個(gè)步驟。第一個(gè)步驟中，對(duì)計(jì)算操作的數(shù)據(jù)（或稱(chēng)為域）進(jìn)行劃分，第二個(gè)步驟根據(jù)數(shù)據(jù)的劃分來(lái)將對(duì)應(yīng)的計(jì)算組織成相應(yīng)的子任務(wù)。對(duì)數(shù)據(jù)的劃分可以用下面的方法進(jìn)行。 – 對(duì)輸出數(shù)據(jù)進(jìn)行劃分 – 對(duì)中間數(shù)據(jù)進(jìn)行劃分 – 對(duì)輸入數(shù)據(jù)進(jìn)行劃分 數(shù)據(jù)分解 ? 一般的來(lái)說(shuō)，當(dāng)我們需要決定對(duì)數(shù)據(jù)如何劃分或者是對(duì)那些數(shù)據(jù)進(jìn)行劃分時(shí)，我們需要看哪一種劃分能夠得到一個(gè)最好的（或者最簡(jiǎn)單的）計(jì)算劃分。因?yàn)閿?shù)據(jù)劃分的目的只不過(guò)是為了得到一種合理的計(jì)算劃分。對(duì)有些問(wèn)題來(lái)說(shuō)，對(duì)輸入數(shù)據(jù)進(jìn)行劃分效果比較好，而對(duì)有些問(wèn)題，對(duì)輸出數(shù)據(jù)（計(jì)算結(jié)果）進(jìn)行劃分要更好一些。在使用數(shù)據(jù)分解的時(shí)候，需要對(duì)所有可能的數(shù)據(jù)劃分方式進(jìn)行考察。 混合分解方法 ? 對(duì)問(wèn)題進(jìn)行任務(wù)分解需要靈活的應(yīng)用上面的方法。遞歸分解，數(shù)據(jù)分解和搜索分解雖然有不同，但它們之間卻不一定相互排斥，因此，在實(shí)際的應(yīng)用中，為了得到更高的并行度，可以將這些分解方法組合使用。 ? 前面我們討論過(guò)快速排序算法，這個(gè)算法對(duì)大小為 n的序列排序時(shí)，可以產(chǎn)生 O(n)個(gè)子任務(wù)，但由于任務(wù)之間的依賴(lài)關(guān)系和任務(wù)分配的不均勻性，有效的并行性相當(dāng)有限。比如，第一個(gè)任務(wù)（將初始序列分割為兩個(gè)子序列）復(fù)雜度為 O(n)，這確定了并行算法的時(shí)間復(fù)雜度的下界。 ? 快速排序也可以采用對(duì)輸入數(shù)據(jù)進(jìn)行分解的方法，對(duì)快速排序采用輸入數(shù)據(jù)分解以及遞歸分解的方法可以得到一個(gè)更為高效的算法 任務(wù)的分配 :任務(wù)映射 ? 上一節(jié)中討論的分解算法可以用來(lái)識(shí)別出問(wèn)題中可以提供的并行性，并且把計(jì)算分解為可以并行執(zhí)行的子任務(wù)。要完成對(duì)問(wèn)題的計(jì)算，下一步是將這些子任務(wù)分配給可用的處理器來(lái)執(zhí)行。給出一個(gè)子任務(wù)集和一個(gè)可用處理器集，有很多種可能的方法來(lái)在它們之間建立某種映射關(guān)系，為了判斷哪種映射更好，我們需要使用下面的評(píng)價(jià)標(biāo)準(zhǔn)： – 分配給每個(gè)處理器的計(jì)算任務(wù)應(yīng)該均衡，這樣才能減少處理器因?yàn)榈却渌幚砥魍瓿捎?jì)算任務(wù)而造成的空閑； – 不同處理器之間的交互應(yīng)該最少，這樣處理器可以用更多的時(shí)間去完成有效的工作。 任務(wù)的分配 :任務(wù)映射 ? 不幸的是，這兩個(gè)目標(biāo)經(jīng)常會(huì)相互沖突。比如，最小化處理器間交互可以用下面的方法很容易的達(dá)到：將需要交互的子任務(wù)分配到同一個(gè)處理器上。有些情況下（很少），這種方法對(duì)負(fù)載平衡影響不大，但更多的時(shí)候，它會(huì)帶來(lái)系統(tǒng)的負(fù)載不均衡。同樣的，為了均衡負(fù)載，有時(shí)候會(huì)把關(guān)系密切（需要很多的交互）的任務(wù)分配到不同的處理器 ? 由于這種沖突的存在，使得任務(wù)的分配變的更像一種藝術(shù)，而不是技術(shù)。通常采用的一種策略是在任務(wù)分配中，先集中目標(biāo)使負(fù)載盡量均衡，然后再對(duì)任務(wù)分配進(jìn)行調(diào)整，使得交互盡量少。 任務(wù)的分配 :任務(wù)映射 ? 對(duì)很多的問(wèn)題來(lái)說(shuō)，在處