單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版文本樣式第二級(jí)第三級(jí)第四級(jí)第五級(jí)

12023/2/6s第五章并行算法的基本設(shè)計(jì)技術(shù)ShenLong1234劃分設(shè)計(jì)技術(shù)分治設(shè)計(jì)技術(shù)平衡樹技術(shù)倍增設(shè)計(jì)技術(shù)5.1劃分設(shè)計(jì)技術(shù)設(shè)計(jì)思想將原問(wèn)題劃分成p個(gè)獨(dú)立的規(guī)模幾乎相等的子問(wèn)題p臺(tái)處理器并行地求解各子問(wèn)題劃分原理常見劃分方法均勻劃分方根劃分對(duì)數(shù)劃分功能劃分5

均勻劃分技術(shù)劃分方法n個(gè)元素A[1..n]分成p組，每組A[(i-1)n/p+1..in/p]示例：并行正則采樣排序（PSRS）ParallelSortingbyRegularSampling6

均勻劃分技術(shù)（1）均勻劃分

（2）局部排序（3）選取樣本

（4）樣本排序（5）選擇主元

（6）主元?jiǎng)澐郑?）全局交換

（8）歸并排序7

PSRS例

PSRS排序過(guò)程。N=27，p=38

5.2平衡樹設(shè)計(jì)技術(shù)設(shè)計(jì)思想將輸入元素作為葉子節(jié)點(diǎn)，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)行并行處理示例求最大值計(jì)算前綴和平衡樹定義|左子樹的深度-右子樹深度|15.2.1求最大值葉子節(jié)點(diǎn)存放待處理的數(shù)據(jù)（需要比較的n個(gè)數(shù)）根節(jié)點(diǎn)表示問(wèn)題的解（n個(gè)數(shù)中的最大值）樹中的同一深度上各個(gè)內(nèi)節(jié)點(diǎn)并行計(jì)算95.2.1求最大值若滿二叉樹的深度為m，待求最大值的n個(gè)數(shù)作為葉子節(jié)點(diǎn)，n=2m，則該樹中總的節(jié)點(diǎn)個(gè)數(shù)為A[1]:求得的最大值10A[n]A[n+1]A[2n-1]…A[1]2n-111

SIMD上求最大值算法A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1k=m-1k=m-2k=0P1P1P2Pn/2-1Pn/2P1Pn/2-112

SIMD上求最大值算法輸入：n個(gè)數(shù)存放在數(shù)組A[n:2n-1]中輸出：最大數(shù)值置于A[1]中Beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend時(shí)間分析t(n)=m×O(1)=O(logn)p(n)=n/2135.2.2計(jì)算前綴和前綴和定義集合S上滿足結(jié)合律的運(yùn)算*，及序列{x1,x2,…,xn}，所謂n個(gè)元素的前綴和是指按照如下方式定義的運(yùn)算結(jié)果：Si=x1*x2*…*xi,1≤i≤n這里*可以是＋或×例：1+2+3+4+5+6+7+814計(jì)算前綴和—串行算法（1）s[1]=A[1];（2）for(i=2;i<=n;i++)

s[i]=s[i-1]*A[i]；串行算法：計(jì)算時(shí)間為O(n)15計(jì)算前綴和—并行算法令A(yù)[i]=xi,i=0~n-1B[h,j]和C[h,j]為輔助數(shù)組(h=0~log2n,j=0~2h-1)數(shù)組B記錄由葉到根正向遍歷樹中各結(jié)點(diǎn)的信息(求和)數(shù)組C記錄由根到葉反向遍歷樹中各結(jié)點(diǎn)的信息(播送前綴和)B樹1612435678371115102636B[3,j]B[2,j]B[1,j]B[0,j]B[i,j]=B[i+1,2j]*B[i+1,2j+1]C樹1713106152128363102136103636C[3,j]C[2,j]C[1,j]C[0,j]C[i,j]=C[i-1,(j-1)/2]j%2=1C[i,j]=B[i,j]j=0C[i,j]=B[i,j]*C[i-1,j/2-1]j>0&&j%2=018begin(1)forj=0ton-1par-do//初始化

B[m,j]=A[j]

(2)fori=m-1to0do//正向遍歷forj=0to2i-1par-do

B[i,j]=B[i+1,2j]*B[i+1,2j+1]

(3)fori=0tomdo//反向遍歷

forj=0to2i-1par-doif(j%2==1)C[i,j]=C[i-1,(j-1)/2]//父結(jié)點(diǎn)的右兒子elseif(j==0)C[i,j]=B[i,j]//父結(jié)點(diǎn)的最左結(jié)點(diǎn)else

C[i,j]=C[i-1,j/2-1]*B[i,j]//父結(jié)點(diǎn)的左兒子

endSIMD-SM上非遞歸算法例假定序列為{1,3,5,7,9,11,13,15},試用算法求其前綴和19205.3倍增設(shè)計(jì)技術(shù)設(shè)計(jì)思想又稱指針跳躍(pointerjumping)技術(shù)，特別適合于處理鏈表或有向樹之類的數(shù)據(jù)結(jié)構(gòu)；當(dāng)遞歸調(diào)用時(shí)，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過(guò)k步后即可完成距離為2k的所有數(shù)據(jù)的計(jì)算。示例表序問(wèn)題求森林的根21

5.3.1表序問(wèn)題問(wèn)題描述給定一個(gè)序列L，包含n個(gè)元素，求出每個(gè)元素在L中的次第號(hào)(秩或位序或rank(k))rank(k)：元素k至表尾的距離22表序問(wèn)題rank(k)：元素k到表尾的距離next(k)：每個(gè)元素k中有一個(gè)指向另一個(gè)元素的next指針p(k)：元素k所指向的下一個(gè)元素distankce(k)：元素k到所指向的元素p(k)間的距離23輸入：n個(gè)元素的列表L輸出：rank(k)(1)forallk∈Lpar-do(1.1)p(k)=next(k);(1.2)if(p(k)!=k)distance(k)=1;elsedistance(k)=0;

(2)fori=1to

(2.1)forallk∈Lpar-doif(p(k)!=p(p(k)){distance(k)=distance(k)+distance(p(k));

p(k)=p(p(k));}(2.2)forallk∈Lpar-do

rank(k)=distance(k)

//O(1)//O(log2n)//O(1)元素k不是最后一個(gè)元素24

5.3.2求森林的根問(wèn)題描述給定一組有向有根樹F，構(gòu)成的森林:①如果<i,j>為F中的一條弧，則p[i]=j(即i的后繼為j)②若i為根，則p[i]=i問(wèn)題：對(duì)于每個(gè)結(jié)點(diǎn)i，求出包含結(jié)點(diǎn)i的樹的根s(i)25求森林的根思想：①開始s(i)為i的后繼p(i)②用指針跳躍技術(shù)，用p(i)的后繼去修改i的后繼，不斷重復(fù)，i的后繼就越來(lái)越靠近根26求森林的根初始時(shí)P(1)=p(2)=5p(3)=p(4)=p(5)=6P(6)=p(7)=8p(8)=8P(9)=10p(10)=11p(11)=12p(12)=13p(13)=13s(i)=p(i)27求森林的根第一次迭代后第二次迭代后運(yùn)行時(shí)間：t(n)=O(logn)W(n)=O(nlogn)28輸入：森林F，弧由(i,p(i))指定，1≤i≤n輸出：對(duì)于每個(gè)節(jié)點(diǎn)i，輸出包含i的樹的根s(i)for1≤i≤npar-do(1)s(i)=p(i);(2)while(s(i)!=s(s(i)))dos(i)=s(s(i));求森林的根—并行算法節(jié)點(diǎn)i不是樹的根節(jié)點(diǎn)29洗衣為例Ann,Brian,Cathy,Dave

每人進(jìn)行洗衣的動(dòng)作：

wash,dry,andfoldwasher需要30minutesDryer需要40minutes“Folder”

需要20minutesABCD5.4流水線設(shè)計(jì)技術(shù)30順序完成這些任務(wù)需要6hoursfor4loads如果采用流水作業(yè),需要多長(zhǎng)時(shí)間?ABCD3040203040203040203040206PM7891011MidnightTaskOrderTime31流水作業(yè)完成四人的洗衣任務(wù)只需要3.5hoursABCD6PM7891011MidnightTaskOrderTime304040404020原則上盡可能早地讓工作開始32流水線技術(shù)要點(diǎn)流水線技術(shù)并不能提高單個(gè)任務(wù)的執(zhí)行效率，它可以提高整個(gè)系統(tǒng)的吞吐率流水線中的瓶頸是最慢的那一段多個(gè)任務(wù)同時(shí)執(zhí)行，但使用不同的資源其潛在的加速比＝流水線的級(jí)數(shù)流水端所需時(shí)間不均衡將降低加速比流水線存在裝入時(shí)間和排空時(shí)間，使得加速比降低由于存在相關(guān)問(wèn)題，會(huì)導(dǎo)致流水線停頓33流水線設(shè)計(jì)技術(shù)設(shè)計(jì)思想將算法流程劃分成p個(gè)前后銜