Пусть поставлена задача - C=A*B, где C,A,B - квадратные матрицы размером m*m.

Последовательный алгоритм

Последовательный алгоритм умножения матриц реализуется по определению:

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

Для корректной работы алгоритма нам потребуется n*n=p процессов.
Разобьём матрицы на n*n квадратных блоков. Пронумеруем процессы от P0,0 до Pn-1,n-1 и присвоим блоки Ai,j и Bi,j процессу Pi,j.
Расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы располагаемые блоки в процессорах могли бы быть перемножены без каких-либо дополнительных передач данных между процессорами. При этом подобное распределение блоков может быть организовано таким образом, что перемещение блоков между процессорами в ходе вычислений может осуществляться с использованием простых коммуникационных операций:

Алгоритм можно разделить на два этапа - это инициализация матриц и основной цикл алгоритма.

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

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

II. Основной цикл:
Основные коммуникационные операции - циклический сдвиг влево блоков строки (далее сдвиг влево) и циклический сдвиг вверх блоков столбца (далее сдвиг вверх).

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

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

Демонстрация

На рисунках 1-6 проиллюстрировано перемещение блоков Ai,j и Bi,j между процессами Pi,j (для n=4). Рис.1 и рис.2 соответствует приведению матриц к первоначальному состоянию. На рис.3 – рис.5 стрелками показано перемещение матриц между процессами. Рис. 6 – финальное расположение матриц.