并行算法第五章并行算法的基本设计技术

单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级

12023/2/6s第五章并行算法的基本设计技术ShenLong1234划分设计技术分治设计技术平衡树技术倍增设计技术5.1划分设计技术设计思想将原问题划分成p个独立的规模几乎相等的子问题p台处理器并行地求解各子问题划分原理常见划分方法均匀划分方根划分对数划分功能划分5

均匀划分技术划分方法n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]示例：并行正则采样排序（PSRS）ParallelSortingbyRegularSampling6

均匀划分技术（1）均匀划分

（2）局部排序（3）选取样本

（4）样本排序（5）选择主元

（6）主元划分（7）全局交换

（8）归并排序7

PSRS例

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

5.2平衡树设计技术设计思想将输入元素作为叶子节点，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理示例求最大值计算前缀和平衡树定义|左子树的深度-右子树深度|15.2.1求最大值叶子节点存放待处理的数据（需要比较的n个数）根节点表示问题的解（n个数中的最大值）树中的同一深度上各个内节点并行计算95.2.1求最大值若满二叉树的深度为m，待求最大值的n个数作为叶子节点，n=2m，则该树中总的节点个数为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个数存放在数组A[n:2n-1]中输出：最大数值置于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上满足结合律的运算*，及序列{x1,x2,…,xn}，所谓n个元素的前缀和是指按照如下方式定义的运算结果：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[i]=xi,i=0~n-1B[h,j]和C[h,j]为辅助数组(h=0~log2n,j=0~2h-1)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)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]//父结点的右儿子elseif(j==0)C[i,j]=B[i,j]//父结点的最左结点else

C[i,j]=C[i-1,j/2-1]*B[i,j]//父结点的左儿子

endSIMD-SM上非递归算法例假定序列为{1,3,5,7,9,11,13,15},试用算法求其前缀和19205.3倍增设计技术设计思想又称指针跳跃(pointerjumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。示例表序问题求森林的根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，构成的森林:①如果<i,j>为F中的一条弧，则p[i]=j(即i的后继为j)②若i为根，则p[i]=i问题：对于每个结点i，求出包含结点i的树的根s(i)25求森林的根思想：①开始s(i)为i的后继p(i)②用指针跳跃技术，用p(i)的后继去修改i的后继，不断重复，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输出：对于每个节点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));求森林的根—并行算法节点i不是树的根节点29洗衣为例Ann,Brian,Cathy,Dave

每人进行洗衣的动作：

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

需要20minutesABCD5.4流水线设计技术30顺序完成这些任务需要6hoursfor4loads如果采用流水作业,需要多长时间?ABCD3040203040203040203040206PM7891011MidnightTaskOrderTime31流水作业完成四人的洗衣任务只需要3.5hoursABCD6PM7891011MidnightTaskOrderTime304040404020原则上尽可能早地让工作开始32流水线技术要点流水线技术并不能提高单个任务的执行效率，它可以提高整个系统的吞吐率流水线中的瓶颈是最慢的那一段多个任务同时执行，但使用不同的资源其潜在的加速比＝流水线的级数流水端所需时间不均衡将降低加速比流水线存在装入时间和排空时间，使得加速比降低由于存在相关问题，会导致流水线停顿33流水线设计技术设计思想将算法流程划分成p个前后衔