并行算法的設計與分析-ch2課件

ParallelAlgorithms

Chapter

2

Fundamental

TechniquesofParallelAlgorithms2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1平衡樹方法2.2倍增技術

2.3分治策略

2.4劃分原理

2.5流水線技術

2023/7/6Y.XuCopyrightUSTC2.1平衡樹方法設計思想樹葉結點為輸入，中間結點為處理結點，由葉向根或由根向葉逐層并行處理。示例求最大值計算前綴和2023/7/6Y.XuCopyrightUSTC算法2.1SIMD-SM上求最大值算法Beginfork=m-1to0doforj=2k

to2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend時間分析t(n)=m×O(1)=O(logn)p(n)=n/2c(n)=O(nlogn)非成本最優(yōu)2.1平衡樹方法2023/7/6Y.XuCopyrightUSTC前綴和問題定義n個元素{x1,x2,…,xn}，前綴和是n個部分和：Si=x1*x2*…*xi,1≤i≤n

這里*可以是＋或×串行算法：Si=Si－1*xi

計算時間為O(n)并行算法：p56算法2.2SIMD-SM上非遞歸算法(高層描述)

p58算法2.3SIMD-SM上非遞歸算法(底層描述)

令A[i]=xi,i=1~n,B[h,j]和C[h,j]為輔助數(shù)組(h=0~logn,j=1~n/2h)

數(shù)組B記錄由葉到根正向遍歷樹中各結點的信息(求和)

數(shù)組C記錄由根到葉反向遍歷樹中各結點的信息(播送前綴和)2.1

平衡樹方法2023/7/6Y.XuCopyrightUSTCp56算法2.2SIMD-SM上非遞歸算法begin(1)forj=1tonpar-do//初始化B[0,j]=A[j]endif(2)forh=1tologndo//正向遍歷forj=1ton/2hpar-doB[h,j]=B[h-1,2j-1]*B[h-1,2j]endforendfor

時間分析:

(1)O(1)(2)O(logn)(3)O(logn)===>t(n)=O(logn),p(n)=n,c(n)=O(nlogn)(3)forh=lognto0do//反向遍歷

forj=1ton/2hpar-do(i)ifj=eventhen//該結點為其父結點的右兒子C[h,j]=C[h+1,j/2]endif(ii)ifj=1then//該結點為最左結點

C[h,1]=B[h,1]endif(iii)ifj=odd>1then//該結點為其父結點的左兒子

C[h,j]=C[h+1,(j-1)/2]*B[h,j]endifendforendforend2.1平衡樹方法2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1BalancedTreesMethod2.2DoublingTechniques

2.3Divide-and-ConquerStrategy2.4PartitioningPrinciple2.5PipeliningTechniques2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1平衡樹方法2.2倍增技術

2.3分治策略

2.4劃分原理

2.5流水線技術

2023/7/6Y.XuCopyrightUSTC設計思想又稱指針跳躍(pointerjumping)技術，特別適合于處理鏈表或有向樹之類的數(shù)據(jù)結構；當遞歸調(diào)用時，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過k步后即可完成距離為2k的所有數(shù)據(jù)的計算。示例表序問題求森林的根2.2倍增技術2023/7/6Y.XuCopyrightUSTC表序問題：問題描述

n個元素的列表L，求出每個元素在L

中的次第號(秩或位序或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注：遞歸計算位序r

(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]=02.2倍增技術2023/7/6Y.XuCopyrightUSTC表序問題：算法：P60算法2.4

(1)并行做：初始化p[k]和distance[k]//O(1)(2)執(zhí)行次//O(logn)

(2.1)對k并行地做//O(1)

如果k的后繼不等于k的后繼之后繼，則

(i)distance[k]=distance[k]+distance[p[k]](ii)p[k]=p[p[k]](2.2)對k并行地做rank[k]=distance[k]//O(1)

運行時間：t(n)=O(logn)p(n)=n2.2倍增技術2023/7/6Y.XuCopyrightUSTC求森林的根問題描述一組有向樹F中,如果<i,j>是F中的一條弧，則p[i]=j(即j是i的雙親)；若i為根，則p[i]=i。求每個結點j(j=1~n)的樹根s[j].示例初始時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]

2.2倍增技術2023/7/6Y.XuCopyrightUSTC求森林的根示例第一次迭代后第二次迭代后算法：p61算法2.5運行時間：t(n)=O(logn)2.2倍增技術2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1BalancedTreesMethod2.2DoublingTechniques2.3Divide-and-ConquerStrategy

2.4PartitioningPrinciple2.5PipeliningTechniques2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1平衡樹方法2.2倍增技術

2.3分治策略

2.4劃分原理

2.5流水線技術

2023/7/6Y.XuCopyrightUSTC設計思想將原問題劃分成若干個相同的子問題分而治之，若子問題仍然較大，則可以反復遞歸應用分治策略處理這些子問題，直至子問題易求解。求解步驟將輸入劃分成若干個規(guī)模相等的子問題；同時(并行地)遞歸求解這些子問題；并行地歸并子問題的解成為原問題的解。示例SIMD-SM模型上的FFT遞歸算法2.3分治策略2023/7/6Y.XuCopyrightUSTCFFT遞歸算法DFT離散富里葉變換的定義給定向量，DFT將A變換為，即

寫成矩陣形式為注：串行直接計算DFT需要O(n2)2.3分治策略2023/7/6Y.XuCopyrightUSTCFFT遞歸算法：將原問題的DFT劃分為兩個規(guī)模為n/2的子問題的DFTSIMD-SM模型上的算法：p64算法2.7

2.3分治策略2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1BalancedTreesMethod2.2DoublingTechniques2.3Divide-and-ConquerStrategy2.4PartitioningPrinciple

2.5PipeliningTechniques2023/7/6Y.XuCopyrightUSTC主要內(nèi)容2.1平衡樹方法2.2倍增技術

2.3分治策略

2.4劃分原理

2.5流水線技術

2023/7/6Y.XuCopyrightUSTC劃分原理：設計思想將原問題劃分成p個獨立的規(guī)模幾乎相等的子問題；p臺處理器并行地求解各子問題。Remark:劃分重點在于:子問題易解,組合成原問題的解方便;常見劃分方法均勻劃分?

方根劃分對數(shù)劃分?

功能劃分2.4劃分原理2023/7/6Y.XuCopyrightUSTC均勻劃分：方法:n個元素A[1..n]分成p組，每組A[(i-1)n/p+1..in/p]，i=1~p示例:MIMD-SM模型上的PSRS排序

begin(1)均勻劃分：將n個元素A[1..n]均勻劃分成p段，每個pi處理A[(i-1)n/p+1..in/p](2)局部排序：pi調(diào)用串行排序算法對A[(i-1)n/p+1..in/p]排序(3)選取樣本：pi從其有序子序列A[(i-1)n/p+1..in/p]中選取p個樣本元素(4)樣本排序：用一臺處理器對p2個樣本元素進行串行排序(5)選擇主元：用一臺處理器從排好序的樣本序列中選取p-1個主元，并播送給其他pi(6)主元劃分：pi按主元將有序段A[(i-1)n/p+1..in/p]劃分成p段(7)全局交換：各處理器將其有序段按段號交換到對應的處理器中(8)歸并排序：各處理器對接收到的元素進行歸并排序end.2.4劃分原理2023/7/6Y.XuCopyrightUSTC例PSRS排序過程。N=27，p=3，PSRS排序如下：2.4劃分原理2023/7/6Y.XuCopyrightUSTC對數(shù)劃分：方法:n個元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn，p=n/logn示例:PRAM-CREW上的對數(shù)劃分并行歸并排序

(1)歸并過程:設有序組A[1..n]和B[1..m]

j[i]=rank(bilogm:A)為bilogm在A中的位序，即A中小于等于bilogm的元素個數(shù)

(2)例：A=(4,6,7,10,12,15,18,20),B=(3,9,16,21)n=8,m=4,p=2=>logm=log4=2=>j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=…=8B0:3,9B1:16,21

A0:4,6,7A1:10,12,15,18,20

A和B歸并化為(A0,B0)和(A1,B1)的歸并

2.4劃分原理2023/7/6Y.XuCopyrightUSTC方根劃分：方法:n個元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2),p=n^(1/2)示例:SIMD-CREW模型上的Valiant歸并排序算法(1975年發(fā)表)

//有序組A[1..p]、B[1..q],(假設p<=q),處理器數(shù)k=(pq)^(1/2)

begin(1)方根劃分：A,B分別按ip^(1/2)和iq^(1/2)分成若干段；(2)段間比較：A劃分元與B劃分元比較(共有p^(1/2)q^(1/2)對)，確定A劃分元應插入B中的區(qū)段；(3)段內(nèi)比較：A劃分元與B相應段內(nèi)元素進行比較，并插入適當?shù)奈恢茫?4)遞歸歸并：B按插入的A劃分元重新分段，與A相應段(A除去原劃分元)構成了成對的段組，對每對段組遞歸執(zhí)行(1)~(3)，直至A組為0時，遞歸結束end.

時間復雜度：若p=q=n，t(n)=O(loglogn)p(n)=n2.4劃分原理2023/7/6Y.XuCopyrightUSTC功能劃分：方法:n個元素A[1..n]分成等長的p組，每組滿足某種特性。示例:(m,n)選擇問題(求出n個元素中前m個最小者)