Будем считать, что количество процессорных элементов p вычислительной системы является степенью числа 4.

Рассмотрим задачу вычисления произведения квадратных матриц X = A*B размерности n на вычислительной системе с n процессорными элементами. Матрицы A и B рассмотрим, как блочные матрицы 2*2 с квадратными блоками размера (n/2) * (n/2). Всего в каждой матрице получается по 4 блока. Обозначим A_ij , i,j = 1,2, блоки матрицы A. Аналогично обозначим блоки матрицы B.

Множество всех процессорных элементов разобьем на 4 равных группы с номерами 0, 1, 2, 3. Разместим элементы обоих матриц поблочно – в каждой группе модулей памяти по одному:

Блок A_ij , i,j = 1,2, матрицы A разместим в группе модулей памяти с номером (i-1)*2 + j-1.

Блок  B_ij , i,j = 1,2, матрицы B разместим в группе модулей памяти с номером (j-1)*2 + i-1.

 Рис. 58 Соответствие 4 групп процессорных элементов блокам матрицы.

B11	B21
B12	B22

Рис. 59. Первое перемножение блоков и первая группа пересылок.

A11*B12	A12*B21
A21*B12	A22*B21

Рис. 60. Второе перемножение блоков и вторая группа пересылок.

 Рис. 61 Сложение блоков.

Для вычисления произведения матриц в этом случае требуется два перемножения блоков, два сложения блоков и две пересылки блоков. 

Перемножения блоков в каждой группе процессорных элементов можно выполнять по такой же схеме рекурсивно. Всего у этого алгоритма log₄p шагов. На каждом шаге размерности блоков в два раза уменьшаются, но количество блоков в 4 раза возрастает.

Рис. 62. Разбиение каждой из 4 групп ПЭ еще на 4 группы второго уровня. При двойной нумерации цифра перед точкой означает номер группы ПЭ первого уровня. Цифра после точки – номер группы ПЭ второго уровня.

Количество параллельных шагов с умножениями (скалярными) в данном алгоритме, как и в других известных параллельных алгоритмах, равно n³/p. При наличии p процессорных элементов и при базовом последовательном алгоритме перемножения матриц со сложностью n³ – эта формула, очевидно, не улучшаема. 

Для пересылок данных в этом алгоритме удобно использовать полнодоступный коммутатор или (log₂p)-мерный куб. Всего в этом алгоритме получается 2*log₄p = log₂p блочных пересылок.

На каждом шаге пересылается n² элементов по p штук одновременно. Всего скалярных пересылочных шагов n²/p . Итого, общее количество скалярных пересылочных шагов n²*log₂p/p . Если p = n, то количество одновременных скалярных пересылок равно n*log₂n – это существенно меньше, чем при размещениях матриц по строкам или столбцам и меньше, чем пересылок в алгоритмах Кэннона и Фокса [35]. 

Перемножение прямоугольных матриц тоже может быть выполнено блочно-рекурсивным алгоритмом. Действительно, пусть требуется перемножить матрицу A размера n*m на матрицу B размера m*k. Обозначим q = p^1/2 . Разобьем матрицу A на блоки размера (n/q)*(m/q) , а матрицу B на блоки размера (m/q)*(k/q). Тогда задача перемножения прямоугольных матриц будет сведена к задаче перемножения квадратных блочных матриц размера q * q , где q = p^1/2 .      

Блочно-рекурсивное размещение данных предполагает количество процессорных элементов (вычислительных узлов) равным степени четверки. Это жесткое ограничение. Иногда, если количество ПЭ равно степени четверки, умноженной на некоторое число, можно комбинировать блочно-рекурсивное размещение данных с блочно-аффинным. На следующем рисунке изображено такое размещение для случая 12 ПЭ.

Рис. 63. Вычислительная система состоит из 12 ПЭ, которые разбиваются на 4 группы по 3 ПЭ в каждой.

В данном примере матрицы разбиваются на блоки следующим образом:

A = {A_ij} i = 1,2, j = 1,…,6 ; B = {B_ij} i = 1,2, j = 1,…,6