Matrix Multiply Example


Here is a complete 3 x 3 example of "in place" SIMD matrix
multiply, with rotations and active sets marked at each stage.

The idea is to implement the grid algorithm, as illustrated
below, with row and column rotations, restoring the matrix
to its original form, at the end.


   Multiply A * B, for                 b13
   3 x 3 matrices A & B,          b12  b23
   using 9 processors:       b11  b22  b33
                             b21  b32   V
                             b31   V    V

             a11  a12  a13   PE   PE   PE
        a21  a22  a23   >    PE   PE   PE
   a31  a32  a33   >    >    PE   PE   PE


Note that in the following, each underined pair of numbers is
multiplied, with the product being added to a sum accumulated
on the PE indicated.


Initial:  a11 b11   a12 b12   a13 b13   a>
   
          a21 b21   a22 b22   a23 b23

          a31 b31   a32 b32   a33 b33

            bV


Step 1:   a13 b31   a11 b12   a12 b13   a>
          -------
          a21 b11   a22 b22   a23 b23   a>

          a31 b21   a32 b32   a33 b33

            bV        bV


Step 2:   a12 b21   a13 b32   a11 b13   a>
          -------   -------
          a23 b31   a21 b12   a22 b23   a>
          -------
          a31 b11   a32 b22   a33 b33   a>

            bV        bV        bV


Step 3:   a11 b11   a12 b22   a13 b33   a>
          -------   -------   -------
          a22 b21   a23 b32   a21 b13   a>
          -------   -------
          a33 b31   a31 b12   a32 b23   a>
          -------
             bV       bV        bV


Step 4:   a13 b31   a11 b12   a12 b23  a>
                    -------   -------
          a21 b11   a22 b22   a23 b33  a>
          -------   -------   -------
          a32 b21   a33 b32   a31 b13  a>
          -------   -------
             bV        bV       bV


Step 5:   a12 b21   a13 b32   a11 b13  a>
                              -------
          a23 b31   a21 b12   a22 b23  a>
                    -------   -------
          a31 b11   a32 b22   a33 b33  a>
          -------   -------   -------
             bV        bV       bV


Step 6:   a11 b11   a12 b22   a13 b33
   
          a22 b21   a23 b32   a21 b13  a>
                              -------
          a33 b31   a31 b12   a32 b23  a>
                    -------   -------
                       bV       bV


Step 7:   a11 b11   a12 b12   a13 b23
   
          a21 b21   a22 b22   a23 b33

          a32 b31   a33 b32   a31 b13  a>
                              -------
                                bV


Final:    a11 b11   a12 b12   a13 b13
   
          a21 b21   a22 b22   a23 b23

          a31 b31   a32 b32   a33 b33