1
N 2tC tM t A
E
N

S
N
N

1 1 2K

1 1 k 2
• 5 二维卷积并行算法设计与分析： • （1）算法：
开始 在由行组成的一阶阵列上执行数据累加ACCUM
q=0
在行矩阵上计算一维卷积S[q](i,j)注1
每个处理器的T值在列 方向上进行一次网格路由 q=q+1 q=M? 在每一列上执行相邻和计算AdjacentSum，得到C2D(i,j)注2 结束
2 2
2
r q 1 N P r qN
r Pq N
2
N
2N
2
PM
2
PN
M
1
C dyn
P P
1N
2
PM
2
N
S opt
( sta )

T opt max i {t i t i
( comm )
}
t cal max i {t i 3 L
共 q 行
q
M 1
… …
行
… …
… …
(P -1 )
#
I Y ' [ P 1 q r .. Pq M r 2 ]
共
C
Y
[ P 1 q r .. Pq r 1 ]
共 q 行
q
M 1
行
• （2）基于动态负载平衡的卷积算法：
共
C
Y
[ rq r .. r 1 q r 1 ]
共 q 行
q
M 1
行
(r+ 1 )
#
I Y ' [ r 1 q r .. r 2 q M r 2 ]
共
C
Y
[ r 1 q r .. r 2 q r 1 ]
( tcp )
(2 N
2
PM
2
MN N ) ( o
( tcp )
o
( udp )
)}
S opt
( dyn )

T opt max i {t i t i
( comm )
}
t cal max i {t i 2 ( n i 1) L
( tcp )
[N
2
M
2
n i ( N 1)] ( o
( tcp )
o
( udp )
)}
• 3 试验结论 • • • • （1）单机模拟＋静态负载平衡； （2）多机模拟＋静态负载平衡； （3）单机模拟＋动态负载平衡； （4）多机模拟＋动态负载平衡；
P q + r - 1 + M -1
进 程
需 要 原 始 矩 阵
计 算 结 果 矩 阵
0
#
I Y ' [ 0 .. q M 1 ]
I Y ' [ q 1 .. 2 q M
… …
共
q
M

行
C
C
Y
[ 0 .. q ]
共 q+1 行
1
#
]
共
q
M

行
Y
[ q 1 .. 2 q 1
(r-1 )q+ r-1
rq + r - 1 + M - 1 q + M -1
rq + r
( r + 1 ) q + r -1 + M - 1
( P - 1 )q + r q N -1 N + M -2 P q + r-1 q + M -1
( P - 1 )q + r
M a s te r 中 添 M - 1 行 S la v e 中 添 M - 1 列
• (2) 分析：
tc
2D
( M 1 ) t C M ( t M t A t C ) * M Mt
C
( M 1 )( 2 t C t A )
E
N
2

S
N
2
N
2

1 1 K

1 1 k 4
• 6 问题： 相邻和操作能否改换一种方式，以减少 循环移位次数？
• 三 网络并行环境下的卷积算法：
首先把T矩阵和I矩阵发送给所有的slave.
• 2 并行算法分析 • （1）常用指标分析；
• （2）LogP模型下的算法分析
C sta P r q M N P r q M 1 N PM Pq PM P r N PM N PM P N PM
• 2 说明：
• 3 基本操作： 循环移位 ； 数据累加 ； 相邻和 。
• 4 一维卷积并行算法设计与分析： • （1）算法： • （2）分析：
SN T
*
TN

NMt
Байду номын сангаас
M
N ( M 1) t A
( 2 M 1) t C M ( t M t A )

N (t M t A ) 2tC t M t A
第七章 卷积并行算法设计与分析
• 卷积运算的重要意义：
• 一 串行卷积： • 1 公式：
M 1
C 1D [i ]

u0
I [( i u ) mod N ] * T [ u ],
0 i N
M 1 M 1
C 2 D [i, j ]

u0 v0
I [( i u ) mod N , ( j v ) mod N ] * T [ u , v ],
• 1 并行算法设计： • （1）基于静态负载平衡的卷积算法
I ’矩 阵
0 0 N -1
计算结果
0 q+1 q q+1 q+1 2 q +1 q+M 2 q + 1 +M -1 q+M q + M -1 q+1 0
需要的原始数据
(r-1 )q+ r-1 q+1 rq + r - 1 rq + r q ( r + 1 ) q + r -1 q+M
… …
]共 q + 1 行
… …
(r-1 )
#
I Y ' [ r 1 q r 1 .. rq M r 2 ]
共
C
Y
[ r 1 q r 1 .. rq r 1 ]
共 q+1 行
q
M

行
r
#
I Y ' [ rq r .. r 1 q M r 2 ]
0 i, j N
• 2 复杂度分析：
卷积类别 复数运算次数 实数运算次数 乘法 加法 乘法 加法
一维卷积
NM
二维卷积
N ( M 1)
4 NM
2 N ( 2 M 1)
N M
2
2
N
2
(M
2
1)
4N M
2
2
2N
2
(2 M
2
1)
• 二 基于SIMD模型的卷积并行算法： • 1 系统结构：