P4
P5
P6
P7
(3,0) (3,1) (3,2) (3,3) (7,0) (7,1) (7,2) (7,3) (0,4) (0,5) (0,6) (0,7) (4,4) (4,5) (4,6) (4,7)
P8
P9
P10
P11
(1,4) (1,5) (1,6) (1,7) (5,4) (5,5) (5,6) (5,7) (2,4) (2,5) (2,6) (2,7) (6,4) (6,5) (6,6) (6,7)
P4
P5
P6
P7
(3,0) (3,1)(3,2) (3,3)(3,4) (3,5)(3,6) (3,7) (4,0) (4,1)(4,2) (4,3)(4,4) (4,5)(4,6) (4,7)
P8
P9
P10
P11
(5,0) (5,1)(5,2) (5,3)(5,4) (5,5)(5,6) (5,7) (6,0) (6,1)(6,2) (6,3)(6,4) (6,5)(6,6) (6,7)
4
第九章 稠密矩阵运算
9.1 矩阵的划分
9.1.1 带状划分 9.1.2 棋盘划分
9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法
带状划分（1）
16×16阶矩阵，p=4
列块带状划分
国家高性能计算中心（合肥）
行循环带状划分
6
带状划分（2）
示例：p＝3，27× 27矩阵的3种带状划分
(3,7) (4,7)
4
5
6
7
(5,0) (2,0)
(5,4) (5,1) (2,4) (2,1)
(5,5)(5,2) (2,5)(2,2)
(5,6) (5,3) (5,7) (2,6) (2,3) (2,7)
8
9
10
11
(5,0) (6,0)
(5,1) (5,2) (5,3) (5,4) (6,1) (6,2) (6,3) (6,4)
9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法
9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法
9.4 矩阵乘法
求Y=AX
矩阵-向量乘法
⎜⎛ y0 ⎟⎞ ⎜⎛ a0,0
⎜ ⎜ ⎜⎜⎝
y1 #
yn−1
⎟ ⎟ ⎟⎟⎠
=
⎜ ⎜ ⎜⎜⎝
(2)网孔连接的计算时间
Tp
=
n2 p
+
2(
p
− 1)ts
+
n p
tw ( p − 1)
// 前1项是乘法时间， 后 2项是多到多的播送时间
=
n2 p
+
2ts (
p − 1) + nt w
// p充分大时
国家高性能计算中心（合肥）
21
带状划分的矩阵-向量乘法（2）
示例
国家高性能计算中心（合肥）
a1,0 #
an−1,0
a0,1 a1,1 #
an−1,1
" a0,n−1 ⎟⎞⎜⎛ x0 ⎟⎞
a1,n−1 ⎟⎜ x1 ⎟
"
# an−1,n
−1
⎟⎜ ⎟⎟⎠⎜⎜⎝
# xn−1
⎟ ⎟⎟⎠
n−1
∑ yi = aij ⋅x j j=0
串行算法计算时间t(n)=O(n2)
国家高性能计算中心（合肥）
19
第九章 稠密矩阵运算
(0,0) (0,4) (0,1) (0,5) (0,2) (0,6) (0,3) (0,7)
(1,0) (2,0)
0
1
2
3Leabharlann (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7)
0
1
2
3
(4,0) (1,0)
划分方法
带状划分(striped partitioning): one dimensional, row or column, block or cyclic
棋盘划分(checkerboard partitioning): two dimensional, block or cyclic
国家高性能计算中心（合肥）
22
第九章 稠密矩阵运算
9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法
9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法
9.4 矩阵乘法
棋盘划分的矩阵-向量乘法（1）
划分(块棋盘划分): Pij存放ai,j, xi置入Pi,i中 算法: 对p=n2情形
(1,6) (1,7)(3,6) (3,7) (5,6) (5,7) (7,6) (7,7)
通(讯a 步)
转(置b 后)
国家高性能计算中心（合肥）
图9.4
13
棋盘划分的矩阵转置（3）
超立方连接

划分:
An×n划分成p个大小为
n×
p
n 子块
p
算法:
①将A＝⎜⎜⎝⎛
A11 A21
A12 A22
并行计算
Parallel Computing
主讲人 徐 云
Spring, 2014
第三篇 并行数值算法
第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 第十二章 数值计算的基本支撑技术
第九章 稠密矩阵运算
9.1 矩阵的划分
9.1.1 带状划分 9.1.2 棋盘划分
9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法
10
第九章 稠密矩阵运算
9.1 矩阵的划分 9.2 矩阵转置
9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置
9.3 矩阵-向量乘法 9.4 矩阵乘法
棋盘划分的矩阵转置（1）
网孔连接
情形1: p=n2。
通讯步
国家高性能计算中心（合肥）
转置后
12
棋盘划分的矩阵转置（2）
情形2: p<n2。
①每个Pi向其他处理器播送xi(多到多播送)；
②每个Pi做相应计算；
注: 对p<n情形,算法中Pi要播送X中相应的n/p个分量
(1)超立方连接的计算时间
Tp
=
n2 p
+
ts
log
p
+
n p
tw( p
− 1)
// 前1项是乘法时间， 后 2项是多到多的播送时间
=
n2 p
+
ts
log
p
+
nt w
// p充分大时
P12
P13
P14
P15
(3,4) (3,5) (3,6) (3,7) (7,4) (7,5) (7,6) (7,7)
(a)
(b)
6
7
14
15
2
3
10
11
4
5
12
13
国家高性能计算中心0 （合肥） 1
8
9
15
第九章 稠密矩阵运算
9.1 矩阵的划分 9.2 矩阵转置
9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置
⎟⎟⎠⎞转置为⎜⎜⎝⎛
A11 A12
A21 A22
⎟⎟⎠⎞
②对Aij递归应用①进行转置，直至分块矩阵的元素处于同一处理器； ③进行同一处理器的内部转置。
运行时间:
Tp
=
n2 2p
+
2（ts
+ tw
n2 p
) log
p
// 内部转置
n2 2p
，选路：2（t
s
+
tw
n2 p
)，递归步：log
p
=
n2 2p
8
9
10
11
(1,4) (1,5)(3,4) (3,5) (5,4) (5,5) (7,4) (7,5) (0,6) (0,7)(2.6) (2,7) (4,6) (4,7) (6,6) (6,7)
12
13
14
15
12
13
14
15
(7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7)
①每个Pi,i向Pj,i播送xi(一到多播送)； ②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结 果为yi；
注: 对p<n2情形,p个处理器排成 p × p的二维网孔，
(1.)X..按按网算中列行孔法相一单连中应到点接P分i多积的,i向量播累计P置j送的算,i入播时时时P送i间间间,i的X::T中(通tps((+相tC讯s ∴+Tn应p时)nt:Tpw的间p)nt≈lw/o):gnlpot2psg++pts+pnl个top+hg(ttw分ph (+p+量t−hpn1p−)p1tw) log p + 3th
9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法
9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法
9.4 矩阵乘法
带状划分的矩阵-向量乘法（1）
划分(行带状划分): Pi存放xi和ai,0,ai,1,…,ai,n-1, 并输出yi 算法: 对p=n情形
P12
P13