Cannon's algorithm

There are many more matrix multiplications, and some that are slightly more efficient than those presented here. We now consider (last but not least) the implementation of Cannon's algorithm (1969).

Cannon's algorithm uses a mesh of $ s^2$ processes that are connected as a torus. Process $ (i,j)$ at location $ (i,j)$ initially begins with submatrices $ \mathsf{A}_{i,j}$ and $ \mathsf{B}_{i,j}$. As the algorithm progresses, the submatrices are passed left and upwards.

\includegraphics[width=2in]{SystolicAlgorithms/matrix-cannon.eps}

  1. Initially $ P_{i,j}$ begins with $ \mathsf{A}_{i,j}$ and $ \mathsf{B}_{i,j}$.
  2. Elements are moved from their initial positions to align them so that the correct submatrices are multiplied with one another. Note that submatrices on the diagonal don't actually require alignment. Alignment is done by shifting the $ i$-th row of $ \mathsf{A}$ $ i$ positions left and the $ j$-th column of $ \mathsf{B}$ $ j$ positions up.
  3. Each process, $ P_{i,j}$ multiplies its current submatrices and adds to a cumulative sum.
  4. The submatrices are shifted left and upwards.
  5. The above two steps are repeated through the remaining submatrices.

aaron@csse.unimelb.edu.au Tue Oct 11 09:33:58 EST 2011