Будем считать, что количество процессорных элементов p вычислительной системы является степенью числа 4: p = 4s .
Отметим, что в исходной последовательной программе оператор присваивания выполняется только в том случае, когда i ≠ k и j ≠ k. Из этого следует, что при фиксированном k все итерации внутреннего двойного цикла со счетчиками i и j могут быть выполнены независимо.
Матрицу A размерности n рассмотрим, как блочную матрицу 2*2 с квадратными блоками размера (n/2) * (n/2). Всего в матрице 4 блока. Обозначим Aij , i,j = 1,2, блоки матрицы A.
0 | 1 |
2 | 3 |
Рис. 54 Соответствие 4 групп процессорных элементов блокам матрицы.
Множество всех процессорных элементов разобьем на 4 равных группы. Разместим элементы матрицы поблочно – в каждой группе модулей памяти по одному:
блок Aij , 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 группы и т.д. В следующей таблице приведена двойная нумерация такого разбиения на группы: число перед точкой означает номер группы в первом разбиении, а число после точки – номер внутри меньшей группы.
0.0 | 0.1 | 1.0 | 1.1 |
0.2 | 0.3 | 1.2 | 1.3 |
2.0 | 2.1 | 3.0 | 3.1 |
2.2 | 2.3 | 3.2 | 3.3 |
Рис. 56. Соответствие 16 групп процессорных элементов блокам матрицы.
При использовании полнодоступного коммутатора или коммуникационной сети N-Cube, данное разбиение множества процессорных элементов на группы позволяет за один шаг выполнять пересылки из группы 0 в 1 и из 2 в 3, а также и другие необходимые комбинации пересылок. Переход к двоичной кодировке ПЭ, как указано на рисунке, позволяет установить соответствие ПЭ узлам коммуникационной сети N-Cube.
0000 | 0001 | 0100 | 0101 |
0010 | 0011 | 0110 | 0111 |
1000 | 1001 | 1100 | 1101 |
1010 | 1011 | 1110 | 1111 |
Рис. 57. То же разбиение множества процессорных элементов на группы в двоичной кодировке. Нумерация соответствует нумерации узлов 4-х мерного куба.
При разбиении групп ПЭ на подгруппы в предложенном выше алгоритме рекурсивно изменяются (детализируются) только пересылки. В алгоритме можно выделить n пересылочных шагов (количество итераций внешнего цикла). Каждый k-ый пересылочный шаг состоит из 2*s = 2*log4(p) пересылок элементов k-ой строки и k-ого столбца.
Пусть в вычислительной системе используется полнодоступный коммутатор или log2(p)-мерный куб
Если p = n2 , то пересылки всех элементов k-ой строки можно выполнить одновременно. Аналогично, одновременно можно выполнить пересылки элементов и k-ого столбца. Всего в данном случае n*log2(n) пересылок и столько же исполнений тела исходного гнезда циклов.
Если n = p, то в каждом процессорном элементе разместится блок матрицы A d*d , где d = n1/2 . Теперь алгоритм сводится к предыдущему случаю, с поправкой на то, что пересылка одной строки или столбца – это d одновременных пересылок чисел. Всего в данном случае n*d*log2(n) = n3/2*log2(n) пересылок. Это существенно меньше, чем при размещении матрицы по строкам или по столбцам – известный алгоритм [126] требует n2*log2(n) пересылок.
Дата: 2018-12-21, просмотров: 482.