第
第PAGE1页共NUMPAGES4页
5.4题：
原理：把n个数根据处理器的数目分配，每个处理器有B＝n/p个数，然后进行根据超立方体的维度d，进行1到d次循环，每次循环都把大于主元的数按维度发到编号比它大的节点上去，经过d次循环后，大编号节点的数据都比比小编号节点的数据大。因此对各个节点做一次局部排序后，按节点编号大小连接，就成为一个有序的序列。
举例：在2维超立方上执行串排序（33，21，13，54，82，33，40，72）
4个处理器编号分别为：（00，01，10，11）,d=log4=2
初始各个处理器分配的数：B(00)={33,21}，B(01)={13,54},B(10)={82,33}，B(11)={40,72}
第一次循环i=1，选择主元x=33，按第1维方向发送和接收数据处理器（00），B1={21,33},B2=?，无发送数据
处理器（01），B1={13},B2={54}，发送数据B2给11处理器（10），B1={33},B2={82}，发送数据B1给00处理器（11），B1=?,B2={40,72}，无发送数据
第一次循环后，各个处理器：B(00)={21,33,33}，B(01)={13}，B(10)={82}，B(11)={40,72,54}
第二次循环i=2，选择主元x=33，按第2维方向发送和接收数据处理器（00），B1={21,33,33},B2=?，无发送数据
处理器（01），B1={13},B2=?，发送数据B1给00处理器（10），B1=?},B2={82}，发送数据B2给11处理器（11），B1=?,B2={40,54,72}，无发送数据
第一次循环后，各个处理器：B(00)={21,33,33,13}，B(01)=?，B(10)=?，B(11)={40,54,72,82}
各个处理器局部排序后，再按编号连接成一个有序的序列。
7.4题：计算次数：
7.4题：
计算次数：NlogN
通信次数：NlogN（斜的线才要通信）
5.6题：
（1）失效函数：F(1)=0，F(2)=1，F(3)=1，F(4)=2
由KMP算法：
(4)
(5)
a b a b(matched) (j=1,k=5)
a
b a
b
（2）KMP算法的原理：不论何时，只要能够预测到字符串的不匹配，则可能将搜索字符串
右移不止一个位置，KMP使用失效函数来控制右移，不能直接并行化。
j
1
2
3
4
F(j)
0
1
1
2
T：
b
a
b
a
a
b
a
b
a
a
(1)
a
b
a
b
(j=1,k=1,F(1)=0)
(2)
a
b
a
b
(j=1,k=2,F(4)=2)
(3)
a
b
a
b
(j=2,k=5,F(2)=1)
6.3
6.3题：
（1）对数划分算法6.3的时间复杂度为O(logm)。
（2）A=(0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34)
B=(3,4,5,6,8,10,12,13,14,15,20,21,22,26,29,31)
m=16，logm=4，k(4)=m/logm=4A0=(0,1,2)，A1=(7,9,11)，A2=(18,19)，A3=(23,24,25,27,28,30,33,34)
B0=(3,4,5,6)，B1=(8,10,12,13)，B2=(14,15,20,21)，B3=(22,26,29,31)
Σ7
Σ
7
0
Σ
7
7
7
7
7
7
7
0
Σ0 Σ0 Σ0 Σ0 Σ0 Σ0
Σ
3
0
Σ
3
0
Σ
3
0
Σ
3
0
Σ
7
4
Σ
7
4
Σ
7
4 Σ
7
4
Σ
1
0
Σ
1
0
Σ
3
2
Σ
3
5
5
7
7
2
Σ4 Σ4 Σ6 Σ6
0
1
2
3
4
5
6
7
9.10题
（1）A矩阵的第i行要比第i-1行滞后1个时间单位。B矩阵的第j列要比第j-1列滞后1个时间单位。
（2）没有Pi,4和P5,j两个处理器，无需继续发送。
12.10
12.10题：
（1）相并行：
Sum=0
fori=0toN-1par-doC[i]=A[i]*B[i]
endfor
fori=0toN-1
Sum=Sum+C[i]endfor
分治并行：
Sum=0
fori=0toN-1par-doC[i]=A[i]*B[i]
endfor
fori=0tologN-1par-doforj=0toN/2i+