并行算法的设计与分析课件.pptxVIP

ParallelAlgorithms

Chapter2

FundamentalTechniquesofParallelAlgorithms

ParallelAlgorithms1/Ch2

Y.XuCopyright

2023/10/19

USTC

n2.1平衡树方法

n2.2倍增技术

n2.3分治策略

n2.4划分原理

n2.5流水线技术

主要内容

ParallelAlgorithms2/Ch2

Y.XuCopyright

2023/10/19

USTC

n设计思想

•树叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层并行处理。

n示例

•求最大值

•计算前缀和

2.1平衡树方法

ParallelAlgorithms3/Ch2

Y.XuCopyright

2023/10/19

USTC

n算法2.1SIMD-SM上求最大值算法

Begin

fork=m-1to0do

forj=2kto2k+1-1par-do

A[j]=max{A[2j],A[2j+1]}

endfor

endfor

end

时间分析

t(n)=m×O(1)=O(logn)

p(n)=n/2

c(n)=O(nlogn)非成本最优

2.1平衡树方法

ParallelAlgorithms4/Ch2

Y.XuCopyright

2023/10/19

USTC

前缀和

n问题定义

n个元素{x1,x2,…,xn}，前缀和是n个部分和：

Si=x1*x2*…*xi,1≤i≤n这里*可以是＋或×

n串行算法：Si=Si－1*xi计算时间为O(n)

n并行算法：p56算法2.2SIMD-SM上非递归算法(高层描述)p58算法2.3SIMD-SM上非递归算法(底层描述)

令A[i]=xi,i=1~n,B[h,j]和C[h,j]为辅助数组(h=0~logn,j=1~n/2h)数组B记录由叶到根正向遍历树中各结点的信息(求和)

数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)

2.1平衡树方法

ParallelAlgorithms5/Ch2

Y.XuCopyright

2023/10/19

USTC

(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=odd1then//该结点为其父结点的左儿子C[h,j]=C[h+1,(j-1)/2]*B[h,j]

endif

endfor

endfor

end

p56算法2.2SIMD-SM上非递归算法

begin

(1)forj=1tonpar-do//初始化

B[0,j]=A[j]

endif

(2)forh=1tologndo//正向遍历forj=1ton/2hpar-do

B[h,j]=B[h-1,2j-1]*B[h-1,2j]endfor

endfor

时间分析:

(1)O(1)(2)O(logn)(3)O(logn)===t(n)=O(logn),p(n)=n,c(n)=O(nlogn)

2.1平衡树方法

ParallelAlgorithms6/Ch2

Y.XuCopyright

2023/10/19

USTC

n2.1BalancedTreesMethod

n2.2DoublingTechniques

n2.3Divide-and-ConquerStrategy

n2.4PartitioningPrinciple

n2.5PipeliningTechniques

主要内容

ParallelAlgorithms7/Ch2

Y.XuCopyright

2023/10/19

USTC

n2.1平衡树方法

n2.2倍增技术

n2.3分治策略

n2.4划分原理

n2.5流水线技术

主要内容

ParallelAlgorithms8/Ch2

Y.XuCopyright

2023/10/19

USTC

n设计思想

•又称指针跳跃(pointerjumping)技术，特别适合于处理链表或有向树之类