并行算法第五章并行算法的基本設(shè)計技術(shù)

單擊此處編輯母版標題樣式單擊此處編輯母版文本樣式第二級第三級第四級第五級

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

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

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

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

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

（6）主元劃分（7）全局交換

（8）歸并排序7

PSRS例

PSRS排序過程。N=27，p=38

5.2平衡樹設(shè)計技術(shù)設(shè)計思想將輸入元素作為葉子節(jié)點，中間結(jié)點為處理結(jié)點，由葉向根或由根向葉逐層進行并行處理示例求最大值計算前綴和平衡樹定義|左子樹的深度-右子樹深度|15.2.1求最大值葉子節(jié)點存放待處理的數(shù)據(jù)（需要比較的n個數(shù)）根節(jié)點表示問題的解（n個數(shù)中的最大值）樹中的同一深度上各個內(nèi)節(jié)點并行計算95.2.1求最大值若滿二叉樹的深度為m，待求最大值的n個數(shù)作為葉子節(jié)點，n=2m，則該樹中總的節(jié)點個數(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個數(shù)存放在數(shù)組A[n:2n-1]中輸出：最大數(shù)值置于A[1]中Beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend時間分析t(n)=m×O(1)=O(logn)p(n)=n/2135.2.2計算前綴和前綴和定義集合S上滿足結(jié)合律的運算*，及序列{x1,x2,…,xn}，所謂n個元素的前綴和是指按照如下方式定義的運算結(jié)果：Si=x1*x2*…*xi,1≤i≤n這里*可以是＋或×例：1+2+3+4+5+6+7+814計算前綴和—串行算法（1）s[1]=A[1];（2）for(i=2;i<=n;i++)

s[i]=s[i-1]*A[i]；串行算法：計算時間為O(n)15計算前綴和—并行算法令A(yù)[i]=xi,i=0~n-1B[h,j]和C[h,j]為輔助數(shù)組(h=0~log2n,j=0~2h-1)數(shù)組B記錄由葉到根正向遍歷樹中各結(jié)點的信息(求和)數(shù)組C記錄由根到葉反向遍歷樹中各結(jié)點的信息(播送前綴和)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é)點的右兒子elseif(j==0)C[i,j]=B[i,j]//父結(jié)點的最左結(jié)點else

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

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

5.3.1表序問題問題描述給定一個序列L，包含n個元素，求出每個元素在L中的次第號(秩或位序或rank(k))rank(k)：元素k至表尾的距離22表序問題rank(k)：元素k到表尾的距離next(k)：每個元素k中有一個指向另一個元素的next指針p(k)：元素k所指向的下一個元素distankce(k)：元素k到所指向的元素p(k)間的距離23輸入：n個元素的列表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不是最后一個元素24

5.3.2求森林的根問題描述給定一組有向有根樹F，構(gòu)成的森林:①如果<i,j>為F中的一條弧，則p[i]=j(即i的后繼為j)②若i為根，則p[i]=i問題：對于每個結(jié)點i，求出包含結(jié)點i的樹的根s(i)25求森林的根思想：①開始s(i)為i的后繼p(i)②用指針跳躍技術(shù)，用p(i)的后繼去修改i的后繼，不斷重復(fù)，i的后繼就越來越靠近根26求森林的根初始時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求森林的根第一次迭代后第二次迭代后運行時間：t(n)=O(logn)W(n)=O(nlogn)28輸入：森林F，弧由(i,p(i))指定，1≤i≤n輸出：對于每個節(jié)點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é)點i不是樹的根節(jié)點29洗衣為例Ann,Brian,Cathy,Dave

每人進行洗衣的動作：

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

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