【文章內(nèi)容簡(jiǎn)介】 ? 表序問(wèn)題 ? 求森林的根 倍增設(shè)計(jì)技術(shù) ? 設(shè)計(jì)思想 – 又稱指針跳躍 (pointer jumping)技術(shù)，特別適合于處理鏈表或有向樹(shù)之類的數(shù)據(jù)結(jié)構(gòu)； – 當(dāng)遞歸調(diào)用時(shí)，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過(guò) k步后即可完成距離為 2k的所有數(shù)據(jù)的計(jì)算。 ? 示例 – 表序問(wèn)題 – 求森林的根 表序問(wèn)題 ? 問(wèn)題描述 n個(gè)元素的列表 L，求出每個(gè)元素在 L 中的次第號(hào) (秩或位序或 rank(k))， rank(k)可視為元素 k至表尾的距離； ? 示例： n=7 (1)p[a]=b, p[b]=c, p[c]=d, p[d]=e, p[e]=f, p[f]=g, p[g]=g r[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1, r[g]=0 (2)p[a]=c, p[b]=d, p[c]=e, p[d]=f, p[e]=p[f]=p[g]=g r[a]=r[b]=r[c]=r[d]=r[e]=2, r[f]=1, r[g]=0 (3)p[a]=e, p[b]=f, p[c]=p[d]=p[e]=p[f]=p[g]=g r[a]=4, r[b]=4, r[c]=4, r[d]=3, r[e]=2, r[f]=1, r[g]=0 (4)p[a]=p[b]=p[c]=p[d]=p[e]=p[f]=p[g]=g r[a]=6, r[b]=5, r[c]=4, r[d]=3, r[e]=2, r[f]=1, r[g]=0 1 1 1 1 1 10022 22 2114424300421653( 1 )( 2 )( 3 )( 4 )a b c d e f g 表序問(wèn)題 ? 算法： P155算法 (1)并行做：初始化 p[k]和 distance[k] //O(1) (2)執(zhí)行 次 //O(logn) ()對(duì) k并行地做 //O(1) 如果 k的后繼不等于 k的后繼之后繼，則 (i) distance[k]= distance[k]+ distance[p[k]] (ii) p[k]=p[p[k]] ()對(duì) k并行地做 rank[k]=distance[k] //O(1) 運(yùn)行時(shí)間： t(n)=O(logn) p(n)=n ? ?nlog 求森林的根 ? 問(wèn)題描述 一組有向樹(shù) F中 , 如果 i, j是 F中的一條弧，則 p[i]=j(即 j是 i的雙親 )；若 i為根，則 p[i]=i。求每個(gè)結(jié)點(diǎn) j(j=1~n)的樹(shù)根 s[j]. ? 示例 初始時(shí) P[1]=p[2]=5 p[3]=p[4]=p[5]=6 P[6]=p[7]=8 p[8]=8 P[9]=10 p[10]=11 p[11]=12 p[12]=13 p[13]=13 s[i]=p[i] 863451 271 31 21 11 09( a ) 求森林的根 ? 示例 第一次迭代后 第二次迭代后 ? 算法： P157算法 ? 運(yùn)行時(shí)間： t(n)=O(logn) W(n)=O(nlogn) 8361 2457 1 21 31 11 09812345671 391 01 11 2( b ) ( c )流水線設(shè)計(jì)技術(shù) ? 設(shè)計(jì)思想 ? 5point DFT的計(jì)算 流水線設(shè)計(jì)技術(shù) ? 設(shè)計(jì)思想 – 將算法流程劃分成 p個(gè)前后銜接的任務(wù)片斷，每個(gè)任務(wù)片斷的輸出作為下一個(gè)任務(wù)片斷的輸入； – 所有任務(wù)片斷按同樣的速率產(chǎn)生出結(jié)果。 ? 評(píng)注 – 流水線技術(shù)是一種廣泛應(yīng)用在并行處理中的技術(shù)； – 脈動(dòng)算法 (Systolic algorithm)是其中一種流水線技術(shù)； 5point DFT的計(jì)算 ? 問(wèn)題描述 5point DFT的計(jì)算。應(yīng)用秦九韶 (Horner)法則， ??????????????????????????????????????????????????????????????????????????04142434440313233343021222324201112131410010203040021426316444021426312433021426384220112233441100102030400)))((()))((()))((()))((()))(((aaaaayaaaaayaaaaayaaaaayaaaaayaaaaabyaaaaabyaaaaabyaaaaabyaaaaaby???????????????????????????????????????? 5point DFT的計(jì)算 ? 示例： p(n)=n1, t(n)=2n2=O(n) ω4a41y01ω11( b )a4a4a4a4a4ω2ω3ω4ω3ω2ωy0ωω2ωy0y0y1y1y1y2y2y3a3a3a3a3a3a2a2a2a2a2a1a1a1a1a1a0a0a0a0a0ai n( a )Xo u tYo u tXi nYi nXi nXYi nXo u tYo u t+ a并行算法 3 一般設(shè)計(jì)過(guò)程 并行算法的一般設(shè)計(jì)過(guò)程 ? PCAM設(shè)計(jì)方法學(xué) ? 劃分 ? 通訊 ? 組合 ? 映射 ? 小結(jié) PCAM設(shè)計(jì)方法學(xué) ? 設(shè)計(jì)并行算法的四個(gè)階段 – 劃分 (Partitioning) – 通訊 (Communication) – 組合 (Agglomeration) – 映射 (Mapping) ? 劃分：分解成小的任務(wù)，開(kāi)拓并發(fā)性； ? 通訊：確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測(cè)劃分的合理性； ? 組合：依據(jù)任務(wù)的局部性，組合成更大的任務(wù)； ? 映射：將每個(gè)任務(wù)分配到處理器上，提高算法的性能。 PCAM設(shè)計(jì)過(guò)程 問(wèn) 題劃 分映 射組 合通 信劃分 ? 方法描述 ? 域分解 ? 功能分解 ? 劃分判據(jù) 劃分方法描述 ? 充分開(kāi)拓算法的并發(fā)性和可擴(kuò)放性； ? 先進(jìn)行數(shù)據(jù)分解 (稱域分解 )，再進(jìn)行計(jì)算功能的分解 (稱功能分解 )； ? 使數(shù)據(jù)集和計(jì)算集互不相交； ? 劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)； ? 能分為兩類劃分： – 域分解 (domain deposition) – 功能分解 (functional deposition) 域分解 ? 劃分的對(duì)象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)； ? 將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片； ? 劃分時(shí)考慮數(shù)據(jù)上的相應(yīng)操作； ? 如果一個(gè)任務(wù)需要?jiǎng)e的任務(wù)中的數(shù)據(jù)，則會(huì)產(chǎn)生任務(wù)間的通訊； 域分解 ? 域分解（ Domain Deposition）也叫數(shù)據(jù)劃分，劃分的對(duì)象是數(shù)據(jù)。這些數(shù)據(jù)可以是算法（或程序）的輸入數(shù)據(jù)、計(jì)算的中間結(jié)果或計(jì)算的輸出數(shù)據(jù)。 ? 域分解的步驟是：首先分解與問(wèn)題相關(guān)的數(shù)據(jù)，如果可能的話，應(yīng)使每份數(shù)據(jù)的數(shù)據(jù)量大體相等；然后再將每個(gè)計(jì)算關(guān)聯(lián)到它所操作的數(shù)據(jù)上。由此就產(chǎn)生出一些任務(wù)，每個(gè)任務(wù)包括一些數(shù)據(jù)及其上的操作。當(dāng)一個(gè)操作需要?jiǎng)e的任務(wù)中的數(shù)據(jù)時(shí)，就會(huì)產(chǎn)生通信要求。 ? 域分解的經(jīng)驗(yàn)方法是：優(yōu)先集中在最大數(shù)據(jù)的劃分和經(jīng)常被訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)上。在不同的階段，可能要對(duì)不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作或需要對(duì)同一數(shù)據(jù)結(jié)構(gòu)進(jìn)行不同的分解。在此情況下，要分別對(duì)待，然后再將各階段設(shè)計(jì)的分解與算法裝配到一起。 域分解 ? 示例：三維網(wǎng)格的域分解，各格點(diǎn)上計(jì)算都是重復(fù)的。下圖是三種分解方法： 圖 7 . 2‐1 D‐2 D‐3 D域分解 ? 不規(guī)則區(qū)域的分解示例： 功能分解 ? 劃分的對(duì)象是計(jì)算，將計(jì)算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解； ? 劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B， 意味著要重新進(jìn)行域分解和功能分解； ? 功能分解是一種更深層次的分解。 功能分解 ? 功能分解 （ Functional Deposition）也叫計(jì)算劃分，它首先關(guān)注被執(zhí)行的計(jì)算的分解，而不是計(jì)算所需的數(shù)據(jù)，然后，如果所作的計(jì)算劃分是成動(dòng)的，再繼續(xù)研究計(jì)算所需的數(shù)據(jù)。如果這些數(shù)據(jù)是不相交或相交很少的，就意味著劃分是成功的；如果這些數(shù)據(jù)有相當(dāng)?shù)闹丿B，就會(huì)產(chǎn)生大量的通信，此時(shí)就暗示應(yīng)考慮數(shù)據(jù)分解。 ? 盡管大多數(shù)并行算法采用域分解，但功能分解有時(shí)能揭示問(wèn)題的內(nèi)在結(jié)構(gòu)，展示出優(yōu)化的機(jī)會(huì)。單對(duì)數(shù)據(jù)進(jìn)行研究往往很難做到這一點(diǎn)。 ? 功能分解的一個(gè)例子是搜索樹(shù)。搜索樹(shù)沒(méi)有明顯的可分解的數(shù)據(jù)結(jié)構(gòu)，但易于進(jìn)行細(xì)粒度的功能分解：開(kāi)始時(shí)根生成一個(gè)任務(wù)，對(duì)其評(píng)價(jià)后，如果它不是一個(gè)解，就生成若干葉結(jié)點(diǎn)，這些葉結(jié)點(diǎn)可以分到各個(gè)處理器上并行地繼續(xù)搜索。 功能分解 ? 示例 1：搜索樹(shù) ? 示例 2：氣候模型 劃分判據(jù) ? 劃分是否具有靈活性？ ? 劃分是否避免了冗余計(jì)算和存儲(chǔ)？ ? 劃分任務(wù)尺寸是否大致相當(dāng)？ ? 任務(wù)數(shù)與問(wèn)題尺寸是否成比例？ ? 功能分解是一種更深層次的分解，是否合理？ 劃分判據(jù) ? 1）所劃分的任務(wù)數(shù)是否高于目標(biāo)機(jī)上處理器數(shù)目一個(gè)量級(jí)？若不是，在后面的設(shè)計(jì)步驟中將缺少靈活性。 ? 2）劃分是否避免了冗余的計(jì)算和存儲(chǔ)要求？若不是，則產(chǎn)生的算法對(duì)大型問(wèn)題可能不是可擴(kuò)展的。 ? 3）各任務(wù)的尺寸是否大致相當(dāng)？若不是，則分配處理器時(shí)很難做到負(fù)載平衡。 ? 4）劃分的任務(wù)數(shù)是否與問(wèn)題尺寸成比例？理想情況下，問(wèn)題尺寸的增加應(yīng)引起任務(wù)數(shù)的增加而不是任務(wù)尺寸的增加。若不是這樣，算法可能不能求解更大的問(wèn)題，盡管有更多的處理器。 ? 5）是否采用了幾種不同的劃分法？多考慮幾種選擇可以提高靈活性。同時(shí)既要考慮域分解又要考慮功能分解。 通訊 ? 方法描述 ? 四種通訊模式 ? 通訊判據(jù) 通訊方法描述 ? 通訊是 PCAM設(shè)計(jì)過(guò)程的重要階段； ? 劃分產(chǎn)生的諸任務(wù)，一般不能完全獨(dú)立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通訊； ? 功能分解確定了諸任務(wù)之間的數(shù)據(jù)流； ? 諸任務(wù)是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性； 四種通訊模式 ? 局部 /全局通訊 :局部通信中，每個(gè)任務(wù)只與少數(shù)的幾個(gè)近鄰任務(wù)通信；全局通信中，每個(gè)任務(wù)要與很多別的任務(wù)通信。 ? 結(jié)構(gòu)化 /非結(jié)構(gòu)化通訊 :結(jié)構(gòu)化通信中，一個(gè)任務(wù)和其近鄰形成規(guī)則的結(jié)構(gòu)（如樹(shù)、網(wǎng)格等）；非結(jié)構(gòu)化通信中，通信網(wǎng)可能是任意圖。 ? 靜態(tài) /動(dòng)態(tài)通訊 :靜態(tài)通信中，通信伙伴不隨時(shí)間變化；動(dòng)態(tài)通信中，通信伙伴可能動(dòng)態(tài)變化。 ? 同步 /異步通訊 :同步通信中，接收方和發(fā)送方協(xié)同操作；異步通信中，接收方獲取數(shù)據(jù)無(wú)需與