14 Cannon乘法 141 Cannon乘法的原理 Cannon算法是一种存储有效的算法。为了使两矩阵下标满足相乘的要求,它和上一节 的并行分块乘法不同,不是仅仅让B矩阵的各列块循环移动,而是有目的地让A的各行块 以及B的各列块皆施行循环移位,从而实现对C的子块的计算。将矩阵A和B分成p个方 块A和Bn,(0≤,j≤VP-1,每块大小为「mx「mF,并将它们分配给√Px√P个处 理器(P00,Po1,P p-1√p-1 开始时处理器Pg存放块A和B,并负责计算块Cy,然 后算法开始执行: (1)将块A向左循环移动i步;将块B向上循环移动j步; (2)P执行乘加运算后将块A向左循环移动1步,块Bn向上循环移动1步 (3)重复第(2)步,总共执行√P次乘加运算和√P次块A1和Bn的循环单步移位 142 Cannon乘法的并行算法 图13示例了在16个处理器上,用 Cannon算法执行A×x4XB4x4的过程。其中(a)和(b) 对应于上述算法的第(1)步;(c)、(d)、(e)、(f)对应于上述算法的第(2)和第(3)步。在算法第(l) 步时,A矩阵的第0列不移位,第Ⅰ行循环左移1位,第2行循环左移2位,第3行循环左 移3位:类似地,B矩阵的第0行不移位,第1列循环上移Ⅰ位,第2列循环上移2列,第 3列循环上移3列。这样 Cannon算法具体描述如下: 算法187 Cannon乘法算法 输入:Anxn,Bn 输出:C 对所有处理器 my_ rank( my rank=0,…p-1)同时执行如下的算法 (1)计算子块的行号r= my rank/sqrt(p) 计算子块的列号产 my rank mod sqrt(p) if(p>k) then Leftmoveonestep(a) end if/*a循环左移至同行相邻处理器中* if(>k)then Up tep(b) end if/b循环上移至同列相邻处理器中* end for (4 )for k=0 to p for i=0 to m-1 d1.4 Cannon 乘法 1.4.1 Cannon 乘法的原理 Cannon 算法是一种存储有效的算法。为了使两矩阵下标满足相乘的要求，它和上一节 的并行分块乘法不同，不是仅仅让 B 矩阵的各列块循环移动，而是有目的地让 A 的各行块 以及 B 的各列块皆施行循环移位，从而实现对 C 的子块的计算。将矩阵 A 和 B 分成 p 个方 块 Aij和 Bij，(0  i, j  p −1) ，每块大小为 n/ p   n/ p  ，并将它们分配给 p  p 个处 理器 ( , ,..., ) 00 01 p−1 p−1 P P P 。开始时处理器 Pij 存放块 Aij 和 Bij，并负责计算块 Cij，然 后算法开始执行： ⑴将块 Aij 向左循环移动 i 步；将块 Bij 向上循环移动 j 步； ⑵Pij 执行乘加运算后将块 Aij 向左循环移动 1 步，块 Bij 向上循环移动 1 步； ⑶重复第⑵步，总共执行 p 次乘加运算和 p 次块 Aij 和 Bij 的循环单步移位。 1.4.2 Cannon 乘法的并行算法 图 1.3 示例了在 16 个处理器上，用 Cannon 算法执行 A4×4×B4×4 的过程。其中(a)和(b) 对应于上述算法的第⑴步；(c)、(d)、(e)、(f)对应于上述算法的第⑵和第⑶步。在算法第⑴ 步时，A 矩阵的第 0 列不移位，第 1 行循环左移 1 位，第 2 行循环左移 2 位，第 3 行循环左 移 3 位；类似地，B 矩阵的第 0 行不移位，第 1 列循环上移 1 位，第 2 列循环上移 2 列，第 3 列循环上移 3 列。这样 Cannon 算法具体描述如下： 算法 18.7 Cannon 乘法算法 输入：An×n，Bn×n 输出：Cn×n Begin 对所有处理器 my_rank(my_rank=0,…,p-1)同时执行如下的算法: (1)计算子块的行号 i=my_rank/sqrt(p) 计算子块的列号 j=my_rank mod sqrt(p) (2)for k=0 to p -1 do if (i>k) then Leftmoveonestep(a) end if /* a 循环左移至同行相邻处理器中*/ if (j>k) then Upmoveonestep(b) end if /* b 循环上移至同列相邻处理器中*/ end for (3)for i=0 to m-1 do for j=0 to m-1 do c[i,j]=0 end for end for (4)for k=0 to p -1 do for i=0 to m-1 do for j=0 to m-1 do for k1=0 to m-1 do