При построении параллельных способов выполнения матричного умножения наряду с рассмотрением матриц в виде наборов строк и столбцов широко используется блочное представление матриц.

Алгоритм Кэннона - блочный алгоритм умножения матриц.

Пусть поставлена задача C = A * B , где C,A,B - квадратные матрицы размером m*m, тогда для корректной работы алгоритма нам потребуется m*m=p процессоров. Разобьём каждую из матриц A и B на p квадратных блоков и зададим нумерацию процессоров P(i,j), где i = 1,m-1 , j = 1,m-1 и умножение блоков A(i,j) и B(i,j) привяжем к процессору P(i,j) соответственно.

Разбиение матриц на блоки в алгоритме Кэннона осуществляется таким образом, чтобы располагаемые блоки в процессорах могли быть перемножены без каких-либо дополнительных коммуникаций между процессорами, а так же чтобы передача данных между процессорами в процессе выполнения алгоритма могла быть осуществлена с помощью простых коммуникационных операций, таких как циклический сдвиг.

Сам алгоритм состоит из двух больших операций - это инициализация матриц, то есть подготовка к умножению, и основной цикл алгоритма.

Инициализация матриц:

1. для каждой строки i, кроме первой, циклический сдвиг блоков на i - 1 позиций влево;
2. для каждого столбца j, кроме первого, циклический сдвиг блоков на j - 1 позиций вверх.

Основной цикл:

Формально определим операции: (*) - циклический сдвиг влево блоков строки на 1 позицию (**) - циклический сдвиг вверх блоков столбца на 1 позицию

Тогда алгоритм выглядит следующим образом:

1. Для всех строк кроме первой производим коммуникационную операцию (*)
2. Для всех столбцов кроме первого производим коммуникационную операцию (**)
3. 1. Вычисляем C(i,j) = C(i,j) + A(i,j) * B(i,j)
   2. for (int i = 0; i <= m - 1; i++)
      {
      Для всех строк производим коммуникационную операцию (*).
      Для всех столбцов производим коммуникационную операцию (**).
      Вычисляем C(i,j) = C(i,j) + A(i,j) * B(i,j)
      }