Fox算法同样通过循环移位的办法来达到节省存储空间的目的,但与Cannon算法不同的是,它通过一对多广播的方式处理A的子矩阵块,而用象Cannon那样的循环移位方法处理B的子矩阵块。根据对称性,也可以对矩阵A的子阵进行循环移位而对矩阵B的子阵采取广播的方式,效果一样。设处理器个数p=q2,则算法的要点如下:
1. 所选中的对角线Aii向所在行的q个处理器进行一对多广播;
2. 各处理器将自己所拥有的A和B的子块进行矩阵相乘运算;
3. B矩阵的块向上循环移动一位,从下面接受一个新的B矩阵块;
4. 选择A的一个矩阵块作为广播源,选择方法是:如果Aij是上次的广播源,则本次的广播源是Ai,(j+1)%q。其中'%'表示取模运算。转步骤1。
图6.3.13是在16个处理器上完成Fox矩阵乘法的演示。Fox算法的性能分析在此不再给出。
(a)
(b)
(c)
(d)
图6.3.13 16个处理器上的Fox乘法演示
Cannon和Fox乘法可以看作一类算法,它们都通过通信与计算交叉的方式减少了计算所需要的存储量。如果说简单矩阵分块乘法的模式是"通信-计算"的话;那么Cannon和Fox乘法的模式则是"通信-计算-通信-计算-……"。
|