c# - Cannon 的矩阵乘法算法

Question

我尝试实现 Cannon 的矩阵乘法算法。我阅读了关于 wikipedia 的描述提供下一个伪代码:

   row i of matrix a is circularly shifted by i elements to the left.
   col j of matrix b is circularly shifted by j elements up.
   Repeat n times:
       p[i][j] multiplies its two entries and adds to running total.
       circular shift each row of a 1 element left
       circular shift each col of b 1 element up

我接下来用 C# 实现了它:

    public static void ShiftLeft(int[][] matrix, int i, int count)
    {
        int ind = 0;
        while (ind < count)
        {
            int temp = matrix[i][0];
            int indl = matrix[i].Length - 1;
            for (int j = 0; j < indl; j++)
                matrix[i][j] = matrix[i][j + 1];
            matrix[i][indl] = temp;
            ind++;
        }
    }
    public static void ShiftUp(int[][] matrix, int j, int count)
    {
        int ind = 0;
        while (ind < count)
        {
            int temp = matrix[0][j];
            int indl = matrix.Length - 1;
            for (int i = 0; i < indl; i++)
                matrix[i][j] = matrix[i + 1][j];
            matrix[indl][j] = temp;
            ind++;
        }
    }

    public static int[][] Cannon(int[][] A, int[][] B)
    {
        int[][] C = new int[A.Length][];
        for (int i = 0; i < C.Length; i++)
            C[i] = new int[A.Length];
        for (int i = 0; i < A.Length; i++)
            ShiftLeft(A, i, i);

        for (int i = 0; i < B.Length; i++)
            ShiftUp(B, i, i);

        for (int k = 0; k < A.Length; k++)
        {
            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < B.Length; j++)
                {
                    var m = (i + j + k) % A.Length;
                    C[i][j] += A[i][m] * B[m][j];
                    ShiftLeft(A, i, 1);
                    ShiftUp(B, j, 1);
                }

            }
        };

        return C;

    }

这段代码返回正确的结果，但是执行起来很慢。甚至比简单的矩阵乘法算法慢得多。

对于矩阵 200x200，我得到了这个结果:

00:00:00.0490432 //naive algorithm
00:00:07.1397479 //Cannon's algorithm

我做错了什么？

---

编辑

感谢 SergeySlepov，并行执行它的尝试很糟糕。当我回到顺序实现时，我得到了下一个结果:

Count       Naive               Cannon's

200    00:00:00.0492098    00:00:08.0465076

250    00:00:00.0908136    00:00:22.3891375

300    00:00:00.1477764    00:00:58.0640621

350    00:00:00.2639114    00:01:51.5545524

400    00:00:00.4323984    00:04:50.7260942

好吧，这不是并行实现，但我该如何正确执行呢？

Answer 1

Cannon's algorithm专为“Distributed Memory”构建Machine'(处理器网格，每个处理器都有自己的内存)。这与您运行它的硬件(一些具有共享内存的处理器)非常不同，这就是您没有看到任何性能提升的原因。

您引用的伪代码中的“循环移位”实际上模拟了处理器之间的数据传输。在初始矩阵“倾斜”之后，网格中的每个处理器都会跟踪三个数字(a、b 和 c)并执行类似于以下的伪代码:

c += a * b;
pass 'a' to the processor to your left (wrapping around)
pass 'b' to the processor to 'above' you (wrapping around)
wait for the next iteration of k

我们可以使用 NxN 线程在 PC 上模仿这种行为，但是上下文切换(或生成 Task)的开销会扼杀所有乐趣。为了充分利用 PC 的 4 个(或更多)CPU，我们可以并行执行 i 循环。 k 上的循环需要按顺序进行(与您的解决方案不同)，否则您可能会面临竞争条件，因为 k 的每次迭代都会修改矩阵 A、B 和 C。在“分布式内存机器”竞争条件不是问题，因为处理器不共享任何内存。