Блочно-рекурсивное размещение матрицы для алгоритма Флойда
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Будем считать, что количество процессорных элементов 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, просмотров: 312.