并 行 计 算中国科学技术大学计算机科学与技术系国家高性能计算中心 (合肥 )
2003年 9月第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 52009-7-24
均匀划分技术? 划分方法
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调用串行排序算法对 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.
国家高性能计算中心（合肥） 62009-7-24
均匀划分技术
例 6.1 PSRS排序过程。 N=27,p=3,PSRS排序如下,
1 5 4 6 4 8 9 3 3 9 6 7 2 9 1 1 4 3 6 6 9 4 0 8 9 6 1 9 7 1 2 2 1 5 4 5 3 9 7 8 4 5 8 3 2 2 7 3 3 7 2 2 0
6 1 4 1 5 3 9 4 6 4 8 7 2 9 1 9 3 1 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 7 2 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
6 3 9 7 2 1 2 4 0 6 9 2 0 3 3 7 2
6
1 2 2 0 3 3 3 9 4 0 6 9 7 2 7 2
3 3 6 9
6 1 4 1 5 3 9 4 6 4 8 7 2 9 1 9 3 1 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 7 2 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
6 1 4 1 5
6 1 4 1 5 3 9 4 6 4 8 7 29 1 9 31 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 72 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
3 9 4 6 4 8 7 2 9 1 9 31 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 72 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
图 6,1
( a ) 均 匀 划 分,
( b ) 局 部 排 序,
( c ) 正 则 采 样,
( d ) 采 样 排 序,
( e ) 选 择 主 元,
( f ) 主 元 划 分,
( h ) 归 并 排 序,
( g ) 全 局 交 换,
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 82009-7-24
方根划分技术
划分方法
n个元素 A[1..n]分成 A[(i-1)n^(1/2)+1..in^(1/2)],i=1~n^(1/2)
示例,SIMD-CREW模型上的 Valiant归并 (1975年发表 )
//有序组 A[1..p],B[1..q],(假设 p<=q),处理器数
begin
(1)方根划分,A,B分别按 ；
(2)段间比较,A划分元与 B划分元比较 (至多 对 )，
确定 A划分元应插入 B中的区段；
(3)段内比较,A划分元与 B相应段内元素进行比较，并插入适当的位置；
(4)递归归并,B按插入的 A划分元重新分段，与 A相应段 (A除去原划分元 )
构成了成对的段组，对每对段组递归执行 (1)~(3)，直至 A
组为 0时，递归结束 ; 各组仍按 分配处理器；
end.
pqk?
pqk?
）、分成若干段（和 qjpiqjpi ~1~1
qp?
pqk?
国家高性能计算中心（合肥） 92009-7-24
方根划分技术
示例,A={1,3,8,9,1 1,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9
A,1 3 8 * 9 1 1 1 3 * 1 5 1 6
B,2 4 5 * 6 7 1 0 * 1 2 1 4 1 7 *
)2,3,8 ppp（
)3,3,9 qqq（
( 1 ) ( 2 )
A,1 3 8 * 9 1 1 1 3 * 1 5 1 6
B,2 4 5 * 6 7 1 0 * 1 2 1 4 1 7 *
( 3 )
A
1
,1 3 ( p
1
= 2 ) A
2
,9 1 1 ( p
2
= 2 ) A
2
,1 5 1 6
B
1
,2 4 5 6 7 8 ( q
1
= 6 ) B
2
,1 0 1 2 1 3 ( q
2
= 3 ) B
3
,1 4 1 7
A
1
,1 3 * ( p
1
= 2 ),,,,,,,,,,,,
B
1
,2 4 5 * 6 7 8 * ( q
1
= 6 ),,,,,,,,,,,,
A
1 1
,1 * A
1 1
,.,,,,,,,,,,,
B
1 1
,2 3 * B
1 2
,4 5 6 7 8,,,,,,,,,,,,
A,
B,1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7
国家高性能计算中心（合肥） 102009-7-24
方根划分技术
算法 分析
(1 ) 算法在并行递归过程中所需的处理器数 ≤
pqk?
段间比较,
qp?
比较对数 ≤
kpq ＝；
段内比较,
kpqqp ＝）－（ 1
递归调用,设 A,B 分成若干子段对为 (p
1
,q
1
),(p
2
,q
2
),……
则∑ p
i
≤ p,∑ q
i
≤ q,由 Ca uch y 不等式 ＝ >
kpqqpqpqp iiiiii
综上,整个过程可用处理器数
pqk?
完成。
(2 ) 时间分析记 λ
i
是第 i 次递归后的 A 组最大长度，＝ >
p?
0
,
i
p
ii
2
1
算法在
C
i
常数
时终止递归，即
Cp
i
常数?
2 ＝ >
1
l o gl o g Cpi 常数
由 (1) 知算法中其他各步的时间为 O( 1),所以 V ali ant 归并算法时间
qppOqpt
k
)l o g( l o g),(
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 122009-7-24
对数划分技术? 划分方法
n个元素 A[1..n]分成 A[(i-1)logn+1..ilogn],i=1~n/logn
示例,PRAM-CREW上的对数划分并行归并排序
(1)归并过程,设有序组 A[1..n]和 B[1..m]
j[i]=rank(bilogm:A)为 bilogm在 A中的位序，即 A中小于等于 bilogm的元素个数
(2)例,A=(4,6,7,10,12,15,18,20),B=(3,9,16,21) n=8,m=4
=>logm=log4=2
=> j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=…=8
B0,3,9 B1,16,21
A0,4,6,7 A1,10,12,15,18,20
A和 B归并 化为 (A0,B0)和 (A1,B1)的归并
b
1
b
l o g m
B =
B
1
B
i
a
1
A =
A
1
A
i
.,,
.,,.,,
.,,
b
l o g m
+ 1
.,,
.,,
a
j ( 1 )
a
j ( 1 ) + 1
a
j ( 2 )
.,,
.,,
b
2 l o g m
b
i l o g m
+ 1
b
( i + 1 ) l o g m
a
j ( i
) + 1
a
j ( i + 1 )
.,,
.,,
A
0
B
0
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 142009-7-24
功能划分技术
划分方法
n个元素 A[1..n]分成等长的 p组，每组满足某种特性。
示例,(m,n)选择问题 (求出 n个元素中前 m个最小者 )
功能划分：要求每组元素个数必须大于 m；
算法,p148算法 6.4
输入,A=(a1,…,an); 输出：前 m个最小者；
Begin
(1) 功能划分：将 A划分成 g=n/m组，每组含 m个元素；
(2) 局部排序：使用 Batcher排序网络将各组并行进行排序；
(3) 两两比较：将所排序的各组两两进行比较，从而形成 MIN序列；
(4) 排序 -比较：对各个 MIN序列，重复执行第 (2)和第 (3)步，直至选出 m个最小者。
End
国家高性能计算中心（合肥） 152009-7-24
功能划分技术
( M )
m
m
m
m
m ( M )m
mm
M A X M I N
M A X M I N
图 6,3 ( m - n ) - 选 择 过 程
S
S
S
S
S
S
.
.
.
.
.
.
第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.2 分治设计技术
6.2.1 并行分治设计步骤
6.2.2 双调归并网络国家高性能计算中心（合肥） 182009-7-24
并行分治设计步骤
将输入划分成若干个规模相等的子问题；
同时 (并行地 )递归求解这些子问题；
并行地归并子问题的解，直至得到原问题的解。
6.2 分治设计技术
6.2.1 并行分治设计步骤
6.2.2 双调归并网络国家高性能计算中心（合肥） 202009-7-24
双调归并网络
双调序列 (p149定义 6.2)
(1,3,5,7,8,6,4,2,0)
(8,7,6,4,2,0,1,3,5)
(1,2,3,4,5,6,7,8)
以上都是双调序列
Batcher定理给定双调序列 (x0,x1,…,xn-1),对于 si=min{xi,xi+n/2}和
li=max{xi,xi+n/2},则小序列 (s0,s1,…,sn-1)和大序列 (l0,l1,…,ln-1)
仍是双调序列国家高性能计算中心（合肥） 212009-7-24
双调归并网络
(4,4)双调归并网络国家高性能计算中心（合肥） 222009-7-24
双调归并网络
Batcher双调归并算法输入：双调序列 X=(x0,x1,…,xn-1)
输出：非降有序序列 Y=(y0,y1,…,yn-1)
Procedure BITONIC_MERG(x)
Begin
(1)for i=0 to n/2-1 par-do
(1.1) si=min{xi,xi+n/2}
(1.2) li=max{xi,xi+n/2}
end for
(2)Recursive Call:
(2.1)BITONIC_MERG(MIN=(s0,…,sn/2-1))
(2.2)BITONIC_MERG(MIN=(l0,…,ln/2-1))
(3)output sequence MIN followed by sequence MAX
End
第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.3 平衡树设计技术
6.3.1 设计思想
6.3.2 求最大值
6.3.3 计算前缀和国家高性能计算中心（合肥） 252009-7-24
平衡树设计技术
设计思想以树的叶结点为输入，中间结点为处理结点，
由叶向根或由根向叶逐层进行并行处理。
示例
求最大值
计算前缀和
6.3 平衡树设计技术
6.3.1 设计思想
6.3.2 求最大值
6.3.3 计算前缀和国家高性能计算中心（合肥） 272009-7-24
求最大值
算法 6.8,SIMD-TC(SM)上求最大值算法
Begin
for k=m-1 to 0 do
for j=2k to 2k+1-1 par-do
A[j]=max{A[2j],A[2j+1]}
end for
end for
end
图示
时间分析
t(n)=m× O(1)=O(logn)
p(n)=n/2
A1
An/4 An/2-1
An/2 An/2+1 An-2 An-1
An An+1An+2 An+3 A2n-4 A2n-3A2n-2 A2n-1
K=m-1
K=m-2
K=0P1
P1 P2 Pn/2-1 Pn/2
P1 Pn/2-1
6.3 平衡树设计技术
6.3.1 设计思想
6.3.2 求最大值
6.3.3 计算前缀和国家高性能计算中心（合肥） 292009-7-24
计算前缀和
问题定义
n个元素 {x1,x2,…,xn}，前缀和是 n个部分和：
Si=x1*x2*…*xi,1≤i≤n 这里 *可以是＋或 ×
串行算法,Si=Si－ 1*xi 计算时间为 O(n)
并行算法,p154算法 6.9 SIMD-TC上非递归算法令 A[i]=xi,i=1~n,
B[h,j]和 C[h,j]为辅助数组 (h=0~logn,j=1~n/2h)
数组 B记录由叶到根正向遍历树中各结点的信息 (求和 )
数组 C记录由根到叶反向遍历树中各结点的信息 (播送前缀和 )
国家高性能计算中心（合肥） 302009-7-24
计算前缀和
例,n=8,p=8,C01~C08为前缀和第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.4 倍增设计技术
6.4.1 设计思想
6.4.2 表序问题
6.4.3 求森林的根国家高性能计算中心（合肥） 332009-7-24
倍增设计技术
设计思想
又称指针跳跃 (pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构；
当递归调用时，所要处理数据之间的距离逐步加倍，
经过 k步后即可完成距离为 2k的所有数据的计算。
示例
表序问题
求森林的根
6.4 倍增设计技术
6.4.1 设计思想
6.4.2 表序问题
6.4.3 求森林的根国家高性能计算中心（合肥） 352009-7-24
表序问题
问题描述
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
(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]=0
1 1 1 1 1 1
0
0
2
2 2
2 2
1
1
4
4
2
4
3
0
0
4
2
1
6
5
3
( 1 )
( 2 )
( 3 )
( 4 )
a b c d e f g
国家高性能计算中心（合肥） 362009-7-24
表序问题
算法,P155算法 6.10
(1)并行做：初始化 p[k]和 distance[k] //O(1)
(2)执行 次 //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)=n
nlog
6.4 倍增设计技术
6.4.1 设计思想
6.4.2 表序问题
6.4.3 求森林的根国家高性能计算中心（合肥） 382009-7-24
求森林的根
问题描述一组有向树 F中,如果 <i,j>是 F中的一条弧，则 p[i]=j(即
j是 i的双亲 )；若 i为根，则 p[i]=i。求每个结点 j(j=1~n)
的树根 s[j].
示例初始时
P[1]=p[2]=5 p[3]=p[4]=p[5]=6
P[6]=p[7]=8 p[8]=8 P[9]=10
p[10]=11 p[11]=12 p[12]=13 p[13]=13
s[i]=p[i]
8
6
3
4
5
1 2
7
1 3
1 2
1 1
1 0
9
( a )
国家高性能计算中心（合肥） 392009-7-24
求森林的根
示例第一次迭代后 第二次迭代后
算法,P157算法 6.11
运行时间,t(n)=O(logn) W(n)=O(nlogn)
8
3
6
1 2
4
5
7 1 2
1 3
1 1
1 0
9
8
1
2
3
4
5
6
7
1 3
9
1 0
1 1
1 2
( b ) ( c )
第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.5 流水线设计技术
6.5.1 设计思想
6.5.2 5-point DFT的计算国家高性能计算中心（合肥） 422009-7-24
流水线设计技术
设计思想
将算法流程划分成 p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入；
所有任务片断按同样的速率产生出结果。
评注
流水线技术是一种广泛应用在并行处理中的技术；
脉动算法 (Systolic algorithm)是其中一种流水线技术；
6.5 流水线设计技术
6.5.1 设计思想
6.5.2 5-point DFT的计算国家高性能计算中心（合肥） 442009-7-24
5-point DFT的计算
问题描述
5-point DFT的计算。应用秦九韶 (Horner)法则，
0
4
1
4
2
4
3
4
44
0
3
1
3
2
3
3
3
43
0
2
1
2
2
2
3
2
42
0
1
1
1
2
1
3
1
41
0
0
1
0
2
0
3
0
40
0
2
1
4
2
6
3
16
444
0
2
1
4
2
6
3
12
433
0
2
1
4
2
6
3
8
422
0
1
1
2
2
3
3
4
411
0
0
1
0
2
0
3
0
400
)))( ( (
)))( ( (
)))( ( (
)))( ( (
)))( ( (
aaaaay
aaaaay
aaaaay
aaaaay
aaaaay
aaaaaby
aaaaaby
aaaaaby
aaaaaby
aaaaaby
国家高性能计算中心（合肥） 452009-7-24
5-point DFT的计算
示例,p(n)=n-1,t(n)=2n-2=O(n)
ω
4
a
4
1
y
0
1ω
1
1
( b )
a
4
a
4
a
4
a
4
a
4
ω
2
ω
3
ω
4
ω
3
ω
2
ω
y
0
ω
ω
2
ω
y
0
y
0
y
1
y
1
y
1
y
2
y
2
y
3
a
3
a
3
a
3
a
3
a
3
a
2
a
2
a
2
a
2
a
2
a
1
a
1
a
1
a
1
a
1
a
0
a
0
a
0
a
0
a
0
a
i n
( a )
X
o u t
Y
o u t
X
i n
Y
i n
X
i n
X
Y
i n
X
o u t
Y
o u t
+ a
2003年 9月第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 52009-7-24
均匀划分技术? 划分方法
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调用串行排序算法对 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.
国家高性能计算中心（合肥） 62009-7-24
均匀划分技术
例 6.1 PSRS排序过程。 N=27,p=3,PSRS排序如下,
1 5 4 6 4 8 9 3 3 9 6 7 2 9 1 1 4 3 6 6 9 4 0 8 9 6 1 9 7 1 2 2 1 5 4 5 3 9 7 8 4 5 8 3 2 2 7 3 3 7 2 2 0
6 1 4 1 5 3 9 4 6 4 8 7 2 9 1 9 3 1 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 7 2 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
6 3 9 7 2 1 2 4 0 6 9 2 0 3 3 7 2
6
1 2 2 0 3 3 3 9 4 0 6 9 7 2 7 2
3 3 6 9
6 1 4 1 5 3 9 4 6 4 8 7 2 9 1 9 3 1 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 7 2 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
6 1 4 1 5
6 1 4 1 5 3 9 4 6 4 8 7 29 1 9 31 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 72 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
3 9 4 6 4 8 7 2 9 1 9 31 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 72 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7
图 6,1
( a ) 均 匀 划 分,
( b ) 局 部 排 序,
( c ) 正 则 采 样,
( d ) 采 样 排 序,
( e ) 选 择 主 元,
( f ) 主 元 划 分,
( h ) 归 并 排 序,
( g ) 全 局 交 换,
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 82009-7-24
方根划分技术
划分方法
n个元素 A[1..n]分成 A[(i-1)n^(1/2)+1..in^(1/2)],i=1~n^(1/2)
示例,SIMD-CREW模型上的 Valiant归并 (1975年发表 )
//有序组 A[1..p],B[1..q],(假设 p<=q),处理器数
begin
(1)方根划分,A,B分别按 ；
(2)段间比较,A划分元与 B划分元比较 (至多 对 )，
确定 A划分元应插入 B中的区段；
(3)段内比较,A划分元与 B相应段内元素进行比较，并插入适当的位置；
(4)递归归并,B按插入的 A划分元重新分段，与 A相应段 (A除去原划分元 )
构成了成对的段组，对每对段组递归执行 (1)~(3)，直至 A
组为 0时，递归结束 ; 各组仍按 分配处理器；
end.
pqk?
pqk?
）、分成若干段（和 qjpiqjpi ~1~1
qp?
pqk?
国家高性能计算中心（合肥） 92009-7-24
方根划分技术
示例,A={1,3,8,9,1 1,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9
A,1 3 8 * 9 1 1 1 3 * 1 5 1 6
B,2 4 5 * 6 7 1 0 * 1 2 1 4 1 7 *
)2,3,8 ppp（
)3,3,9 qqq（
( 1 ) ( 2 )
A,1 3 8 * 9 1 1 1 3 * 1 5 1 6
B,2 4 5 * 6 7 1 0 * 1 2 1 4 1 7 *
( 3 )
A
1
,1 3 ( p
1
= 2 ) A
2
,9 1 1 ( p
2
= 2 ) A
2
,1 5 1 6
B
1
,2 4 5 6 7 8 ( q
1
= 6 ) B
2
,1 0 1 2 1 3 ( q
2
= 3 ) B
3
,1 4 1 7
A
1
,1 3 * ( p
1
= 2 ),,,,,,,,,,,,
B
1
,2 4 5 * 6 7 8 * ( q
1
= 6 ),,,,,,,,,,,,
A
1 1
,1 * A
1 1
,.,,,,,,,,,,,
B
1 1
,2 3 * B
1 2
,4 5 6 7 8,,,,,,,,,,,,
A,
B,1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7
国家高性能计算中心（合肥） 102009-7-24
方根划分技术
算法 分析
(1 ) 算法在并行递归过程中所需的处理器数 ≤
pqk?
段间比较,
qp?
比较对数 ≤
kpq ＝；
段内比较,
kpqqp ＝）－（ 1
递归调用,设 A,B 分成若干子段对为 (p
1
,q
1
),(p
2
,q
2
),……
则∑ p
i
≤ p,∑ q
i
≤ q,由 Ca uch y 不等式 ＝ >
kpqqpqpqp iiiiii
综上,整个过程可用处理器数
pqk?
完成。
(2 ) 时间分析记 λ
i
是第 i 次递归后的 A 组最大长度，＝ >
p?
0
,
i
p
ii
2
1
算法在
C
i
常数
时终止递归，即
Cp
i
常数?
2 ＝ >
1
l o gl o g Cpi 常数
由 (1) 知算法中其他各步的时间为 O( 1),所以 V ali ant 归并算法时间
qppOqpt
k
)l o g( l o g),(
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 122009-7-24
对数划分技术? 划分方法
n个元素 A[1..n]分成 A[(i-1)logn+1..ilogn],i=1~n/logn
示例,PRAM-CREW上的对数划分并行归并排序
(1)归并过程,设有序组 A[1..n]和 B[1..m]
j[i]=rank(bilogm:A)为 bilogm在 A中的位序，即 A中小于等于 bilogm的元素个数
(2)例,A=(4,6,7,10,12,15,18,20),B=(3,9,16,21) n=8,m=4
=>logm=log4=2
=> j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=…=8
B0,3,9 B1,16,21
A0,4,6,7 A1,10,12,15,18,20
A和 B归并 化为 (A0,B0)和 (A1,B1)的归并
b
1
b
l o g m
B =
B
1
B
i
a
1
A =
A
1
A
i
.,,
.,,.,,
.,,
b
l o g m
+ 1
.,,
.,,
a
j ( 1 )
a
j ( 1 ) + 1
a
j ( 2 )
.,,
.,,
b
2 l o g m
b
i l o g m
+ 1
b
( i + 1 ) l o g m
a
j ( i
) + 1
a
j ( i + 1 )
.,,
.,,
A
0
B
0
6.1 划分设计技术
6.1.1 均匀划分技术
6.1.2 方根划分技术
6.1.3 对数划分技术
6.1.4 功能划分技术国家高性能计算中心（合肥） 142009-7-24
功能划分技术
划分方法
n个元素 A[1..n]分成等长的 p组，每组满足某种特性。
示例,(m,n)选择问题 (求出 n个元素中前 m个最小者 )
功能划分：要求每组元素个数必须大于 m；
算法,p148算法 6.4
输入,A=(a1,…,an); 输出：前 m个最小者；
Begin
(1) 功能划分：将 A划分成 g=n/m组，每组含 m个元素；
(2) 局部排序：使用 Batcher排序网络将各组并行进行排序；
(3) 两两比较：将所排序的各组两两进行比较，从而形成 MIN序列；
(4) 排序 -比较：对各个 MIN序列，重复执行第 (2)和第 (3)步，直至选出 m个最小者。
End
国家高性能计算中心（合肥） 152009-7-24
功能划分技术
( M )
m
m
m
m
m ( M )m
mm
M A X M I N
M A X M I N
图 6,3 ( m - n ) - 选 择 过 程
S
S
S
S
S
S
.
.
.
.
.
.
第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.2 分治设计技术
6.2.1 并行分治设计步骤
6.2.2 双调归并网络国家高性能计算中心（合肥） 182009-7-24
并行分治设计步骤
将输入划分成若干个规模相等的子问题；
同时 (并行地 )递归求解这些子问题；
并行地归并子问题的解，直至得到原问题的解。
6.2 分治设计技术
6.2.1 并行分治设计步骤
6.2.2 双调归并网络国家高性能计算中心（合肥） 202009-7-24
双调归并网络
双调序列 (p149定义 6.2)
(1,3,5,7,8,6,4,2,0)
(8,7,6,4,2,0,1,3,5)
(1,2,3,4,5,6,7,8)
以上都是双调序列
Batcher定理给定双调序列 (x0,x1,…,xn-1),对于 si=min{xi,xi+n/2}和
li=max{xi,xi+n/2},则小序列 (s0,s1,…,sn-1)和大序列 (l0,l1,…,ln-1)
仍是双调序列国家高性能计算中心（合肥） 212009-7-24
双调归并网络
(4,4)双调归并网络国家高性能计算中心（合肥） 222009-7-24
双调归并网络
Batcher双调归并算法输入：双调序列 X=(x0,x1,…,xn-1)
输出：非降有序序列 Y=(y0,y1,…,yn-1)
Procedure BITONIC_MERG(x)
Begin
(1)for i=0 to n/2-1 par-do
(1.1) si=min{xi,xi+n/2}
(1.2) li=max{xi,xi+n/2}
end for
(2)Recursive Call:
(2.1)BITONIC_MERG(MIN=(s0,…,sn/2-1))
(2.2)BITONIC_MERG(MIN=(l0,…,ln/2-1))
(3)output sequence MIN followed by sequence MAX
End
第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.3 平衡树设计技术
6.3.1 设计思想
6.3.2 求最大值
6.3.3 计算前缀和国家高性能计算中心（合肥） 252009-7-24
平衡树设计技术
设计思想以树的叶结点为输入，中间结点为处理结点，
由叶向根或由根向叶逐层进行并行处理。
示例
求最大值
计算前缀和
6.3 平衡树设计技术
6.3.1 设计思想
6.3.2 求最大值
6.3.3 计算前缀和国家高性能计算中心（合肥） 272009-7-24
求最大值
算法 6.8,SIMD-TC(SM)上求最大值算法
Begin
for k=m-1 to 0 do
for j=2k to 2k+1-1 par-do
A[j]=max{A[2j],A[2j+1]}
end for
end for
end
图示
时间分析
t(n)=m× O(1)=O(logn)
p(n)=n/2
A1
An/4 An/2-1
An/2 An/2+1 An-2 An-1
An An+1An+2 An+3 A2n-4 A2n-3A2n-2 A2n-1
K=m-1
K=m-2
K=0P1
P1 P2 Pn/2-1 Pn/2
P1 Pn/2-1
6.3 平衡树设计技术
6.3.1 设计思想
6.3.2 求最大值
6.3.3 计算前缀和国家高性能计算中心（合肥） 292009-7-24
计算前缀和
问题定义
n个元素 {x1,x2,…,xn}，前缀和是 n个部分和：
Si=x1*x2*…*xi,1≤i≤n 这里 *可以是＋或 ×
串行算法,Si=Si－ 1*xi 计算时间为 O(n)
并行算法,p154算法 6.9 SIMD-TC上非递归算法令 A[i]=xi,i=1~n,
B[h,j]和 C[h,j]为辅助数组 (h=0~logn,j=1~n/2h)
数组 B记录由叶到根正向遍历树中各结点的信息 (求和 )
数组 C记录由根到叶反向遍历树中各结点的信息 (播送前缀和 )
国家高性能计算中心（合肥） 302009-7-24
计算前缀和
例,n=8,p=8,C01~C08为前缀和第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.4 倍增设计技术
6.4.1 设计思想
6.4.2 表序问题
6.4.3 求森林的根国家高性能计算中心（合肥） 332009-7-24
倍增设计技术
设计思想
又称指针跳跃 (pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构；
当递归调用时，所要处理数据之间的距离逐步加倍，
经过 k步后即可完成距离为 2k的所有数据的计算。
示例
表序问题
求森林的根
6.4 倍增设计技术
6.4.1 设计思想
6.4.2 表序问题
6.4.3 求森林的根国家高性能计算中心（合肥） 352009-7-24
表序问题
问题描述
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
(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]=0
1 1 1 1 1 1
0
0
2
2 2
2 2
1
1
4
4
2
4
3
0
0
4
2
1
6
5
3
( 1 )
( 2 )
( 3 )
( 4 )
a b c d e f g
国家高性能计算中心（合肥） 362009-7-24
表序问题
算法,P155算法 6.10
(1)并行做：初始化 p[k]和 distance[k] //O(1)
(2)执行 次 //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)=n
nlog
6.4 倍增设计技术
6.4.1 设计思想
6.4.2 表序问题
6.4.3 求森林的根国家高性能计算中心（合肥） 382009-7-24
求森林的根
问题描述一组有向树 F中,如果 <i,j>是 F中的一条弧，则 p[i]=j(即
j是 i的双亲 )；若 i为根，则 p[i]=i。求每个结点 j(j=1~n)
的树根 s[j].
示例初始时
P[1]=p[2]=5 p[3]=p[4]=p[5]=6
P[6]=p[7]=8 p[8]=8 P[9]=10
p[10]=11 p[11]=12 p[12]=13 p[13]=13
s[i]=p[i]
8
6
3
4
5
1 2
7
1 3
1 2
1 1
1 0
9
( a )
国家高性能计算中心（合肥） 392009-7-24
求森林的根
示例第一次迭代后 第二次迭代后
算法,P157算法 6.11
运行时间,t(n)=O(logn) W(n)=O(nlogn)
8
3
6
1 2
4
5
7 1 2
1 3
1 1
1 0
9
8
1
2
3
4
5
6
7
1 3
9
1 0
1 1
1 2
( b ) ( c )
第六章 并行算法的基本设计技术
6.1 划分设计技术
6.2 分治设计技术
6.3 平衡树设计技术
6.4 倍增设计技术
6.5 流水线设计技术
6.5 流水线设计技术
6.5.1 设计思想
6.5.2 5-point DFT的计算国家高性能计算中心（合肥） 422009-7-24
流水线设计技术
设计思想
将算法流程划分成 p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入；
所有任务片断按同样的速率产生出结果。
评注
流水线技术是一种广泛应用在并行处理中的技术；
脉动算法 (Systolic algorithm)是其中一种流水线技术；
6.5 流水线设计技术
6.5.1 设计思想
6.5.2 5-point DFT的计算国家高性能计算中心（合肥） 442009-7-24
5-point DFT的计算
问题描述
5-point DFT的计算。应用秦九韶 (Horner)法则，
0
4
1
4
2
4
3
4
44
0
3
1
3
2
3
3
3
43
0
2
1
2
2
2
3
2
42
0
1
1
1
2
1
3
1
41
0
0
1
0
2
0
3
0
40
0
2
1
4
2
6
3
16
444
0
2
1
4
2
6
3
12
433
0
2
1
4
2
6
3
8
422
0
1
1
2
2
3
3
4
411
0
0
1
0
2
0
3
0
400
)))( ( (
)))( ( (
)))( ( (
)))( ( (
)))( ( (
aaaaay
aaaaay
aaaaay
aaaaay
aaaaay
aaaaaby
aaaaaby
aaaaaby
aaaaaby
aaaaaby
国家高性能计算中心（合肥） 452009-7-24
5-point DFT的计算
示例,p(n)=n-1,t(n)=2n-2=O(n)
ω
4
a
4
1
y
0
1ω
1
1
( b )
a
4
a
4
a
4
a
4
a
4
ω
2
ω
3
ω
4
ω
3
ω
2
ω
y
0
ω
ω
2
ω
y
0
y
0
y
1
y
1
y
1
y
2
y
2
y
3
a
3
a
3
a
3
a
3
a
3
a
2
a
2
a
2
a
2
a
2
a
1
a
1
a
1
a
1
a
1
a
0
a
0
a
0
a
0
a
0
a
i n
( a )
X
o u t
Y
o u t
X
i n
Y
i n
X
i n
X
Y
i n
X
o u t
Y
o u t
+ a
