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

Отметим, что в исходной последовательной программе оператор присваивания выполняется только в том случае, когда i ≠ k и j ≠ k. Из этого следует, что при фиксированном k все итерации внутреннего двойного цикла со счетчиками i и j могут быть выполнены независимо.

Матрицу A размерности n рассмотрим, как блочную матрицу 2*2 с квадратными блоками размера (n/2) * (n/2). Всего в матрице 4 блока. Обозначим A_ij , i,j = 1,2, блоки матрицы A.

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

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

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

Параллельный алгоритм Флойда выглядит следующим образом.

do 77 k = 1, n/2

% Пересылки 220 и 330 одновременно:

do 220 i = 1, n/2

220 A(i,k) пересылаем из группы ПЭ с номером 0 в группу ПЭ с номером 2

do 330 i = n/2+1, n

330 A(i,k) пересылаем из группы ПЭ с номером 1 в группу ПЭ с номером 3

% Конец пересылок

% Пересылки 440 и 550 одновременно:

do 440 j = 1, n/2

440 A(k,j) пересылаем из группы ПЭ с номером 0 в группу ПЭ с номером 1

do 550 j = n/2+1, n

550 A(k,j) пересылаем из группы ПЭ с номером 2 в группу ПЭ с номером 3

% Конец пересылок

do 77 i = 1, n

do 77 j = 1, n

if A(i,j) > A(i,k)+A(k,j) then

77 A(i,j) = A(i,k)+A(k,j)

do 88 k = n/2, n+1

% Пересылки 221 и 331 одновременно:

do 221 i = 1, n/2

221 A(i,k) пересылаем из группы ПЭ с номером 2 в группу ПЭ с номером 0

do 331 i = n/2+1, n

331 A(i,k) пересылаем из группы ПЭ с номером 3 в группу ПЭ с номером 1

% Конец пересылок

% Пересылки 441 и 551 одновременно:

do 441 j = 1, n/2

441 A(k,j) пересылаем из группы ПЭ с номером 1 в группу ПЭ с номером 0

do 551 j = n/2+1, n

551 A(k,j) пересылаем из группы ПЭ с номером 3 в группу ПЭ с номером 2

% Конец пересылок

do 88 i = 1, n

do 88 j = 1, n

if A(i,j) > A(i,k)+A(k,j) then

88  A(i,j) = A(i,k)+A(k,j)

0	1
2	3

0	1
2	3

0	1
2	3

0	1
2	3

Рис. 55. Схема четырех пересылочных тактов.

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

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

При использовании полнодоступного коммутатора или коммуникационной сети N-Cube, данное разбиение множества процессорных элементов на группы позволяет за один шаг выполнять пересылки из группы 0 в 1 и из 2 в 3, а также и другие необходимые комбинации пересылок. Переход к двоичной кодировке ПЭ, как указано на рисунке, позволяет установить соответствие ПЭ узлам коммуникационной сети N-Cube.  

  Рис. 57. То же разбиение множества процессорных элементов на группы в двоичной кодировке. Нумерация соответствует нумерации узлов 4-х мерного куба.

При разбиении групп ПЭ на подгруппы в предложенном выше алгоритме рекурсивно изменяются (детализируются) только пересылки. В алгоритме можно выделить n пересылочных шагов (количество итераций внешнего цикла). Каждый k-ый пересылочный шаг состоит из 2*s = 2*log₄(p) пересылок элементов k-ой строки и k-ого столбца.

Пусть в вычислительной системе используется полнодоступный коммутатор или log₂(p)-мерный куб

Если p = n² , то пересылки всех элементов k-ой строки можно выполнить одновременно. Аналогично, одновременно можно выполнить пересылки элементов и k-ого столбца. Всего в данном случае n*log₂(n) пересылок и столько же исполнений тела исходного гнезда циклов.

Если n = p, то в каждом процессорном элементе разместится блок матрицы A d*d , где d = n^1/2 . Теперь алгоритм сводится к предыдущему случаю, с поправкой на то, что пересылка одной строки или столбца – это d одновременных пересылок чисел. Всего в данном случае n*d*log₂(n) = n^3/2*log₂(n) пересылок. Это существенно меньше, чем при размещении матрицы по строкам или по столбцам – известный алгоритм [126] требует n²*log₂(n) пересылок.