Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Блочно-рекурсивное размещение матрицы для алгоритма Флойда.
Будем считать, что количество процессорных элементов 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.
Рис. 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)
Рис. 55. Схема четырех пересылочных тактов.
Каждая из 4 групп процессорных элементов в свою очередь может быть опять разбита на 4 группы и т.д. В следующей таблице приведена двойная нумерация такого разбиения на группы: число перед точкой означает номер группы в первом разбиении, а число после точки – номер внутри меньшей группы.
Рис. 56. Соответствие 16 групп процессорных элементов блокам матрицы.
При использовании полнодоступного коммутатора или коммуникационной сети N-Cube, данное разбиение множества процессорных элементов на группы позволяет за один шаг выполнять пересылки из группы 0 в 1 и из 2 в 3, а также и другие необходимые комбинации пересылок. Переход к двоичной кодировке ПЭ, как указано на рисунке, позволяет установить соответствие ПЭ узлам коммуникационной сети N-Cube.
Рис. 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) пересылок.
|
Последнее изменение этой страницы: 2019-05-17; Просмотров: 400; Нарушение авторского права страницы