中科院计算所谭光明老师课件C05-数据分布与性能优化.ppt

Systolic乘法 Systolic算法 //输入: Am×n, Bn×k; 输出: Cm×k Begin for i=1 to m par- do for j=1 to k par-do (i) ci,j = 0 (ii) while Pi,j 收到a和b时 do ci,j = ci,j +ab if i m then 发送b给Pi+1,j endif if j k then 发送a给Pi,j+1 endif endwhile endfor endfor End 上机作业 实现并行矩阵向量乘法 实现并行矩阵乘法 THANKS * * * 矩阵乘法 行块分解的串行矩阵乘法 简单分块并行矩阵乘法 Cannon矩阵乘法(棋盘划分) Fox矩阵乘法 Systolic矩阵乘法 Cannon乘法(基于棋盘分解) 算法简介： Cannon算法是一种存储有效的算法。 与并行分块乘法不同，阵列的各行和各列不是施行多到多的广播，而是有目的地在各行和各列实施循环移位，从而降低各处理器的存储量 Cannon乘法 分块: A、B和C分成 的方块阵Ai,j、Bi,j和Ci,j, 大小均为 p个处理器编号为 , Pi,j存放Ai,j、Bi,j和Ci,j(n p) P0,0 P1,0 P2,0 P3,0 P0,1 P1,1 P2,1 P3,1 P0,2 P1,2 P2,2 P3,2 P0,3 P1,3 P2,3 P3,3 Cannon乘法 算法原理 (非形式描述) ①块Ai,j(0≤i,j≤ )向左循环移动i步(按行移位)； 块Bi,j(0≤i,j≤ )向上循环移动j步(按列移位)； ②所有处理器Pi,j做执行Ai,j和Bi,j的乘-加运算; ③A的每个块向左循环移动一步; B的每个块向上循环移动一步; ④转②执行 次; Cannon乘法 A0,0 B0,0 A1,0 B1,0 A2,0 B2,0 A3,0 B3,0 A0,1 B0,1 A1,1 B1,1 A2,1 B2,1 A3,1 B3,1 A0,2 B0,2 A1,2 B1,2 A2,2 B2,2 A3,2 B3,2 A0,3 B0,3 A1,3 B1,3 A2,3 B2,3 A3,3 B3,3 示例： A4×4， B4×4, p=16 Cannon乘法 Initial alignment of A Initial alignment of B A0,0 A1,0 A2,0 A3,0 A0,1 A1,1 A2,1 A3,1 A0,2 A1,2 A2,2 A3,2 A0,3 A1,3 A2,3 A3,3 B0,0 B1,0 B2,0 B3,0 B0,1 B1,1 B2,1 B3,1 B0,2 B1,2 B2,2 B3,2 B0,3 B1,3 B2,3 B3,3 A0,0 B0,0 A1,1 B1,0 A2,2 B2,0 A3,3 B3,0 A0,1 B1,1 A1,2 B2,1 A2,3 B3,1 A3,0 B0,1 A0,2 B2,2 A1,3 B3,2 A2,0 B0,2 A3,1 B1,2 A0,3 B3,3 A1,0 B0,3 A2,1 B1,3 A3,2 B2,3 Cannon乘法 After first shift A0,1 B1,0 A1,2 B2,0 A2,3 B3,0 A3,0 B0,0 A0,2 B2,1 A1,3 B3,1 A2,0 B0,1 A3,1 B3,1 A0,3 B3,2 A1,0 B0,2 A2,1 B1,2 A3,2 B2,2 A0,0 B0,3 A1,1 B1,3 A2,2 B2,3 A3,3 B3,3 After second shift A0,2 B2,0 A1,3 B3,0 A2,0 B0,0 A3,1 B1,0 A0,3 B3,1 A1,0 B0,1 A2,1 B1,1 A3,2 B2,1 A0,0 B0,2 A1,1 B1,2 A2,2 B2,2 A3,3 B3,2 A0,1 B1,3 A1,2 B2,3 A2,3 B3,3 A3,0 B0