Лекции по параллельным вычислениям. Гергель В.П - 142 стр.

UptoLike

Составители:

Рубрика:

142

б)

Рис. 10.3 Граф-схема (а) и временная диаграмма (б) модифицированного алго-

ритма перемножения матриц для решетки подзадач 2×2

В результате такого начального распределения каждой подзадаче будут

доступны блоки, которые могут быть перемножены без дополнительных опера-

ций передачи данных. При этом существенно упрощается получение всех по-

следующих блоков для подзадач. После выполнения очередной операции блоч-

ного умножения каждый блок матрицы A должен быть передан предшествую-

щей подзадаче влево по строкам решетки подзадач, а каждый блок матрицы В –

предшествующей подзадаче вверх по столбцам решетки. Последовательность

циклических сдвигов и умножений блоков исходных матриц A и B приведет к

получению в подзадачах соответствующих блоков результирующей матрицы C.

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

логии сети передачи данных между процессорами (в виде решетки или полного

графа), которые сформулированы для предыдущего алгоритма. Что касается

анализа эффективности описанной модификации алгоритма, заметим, что этот

алгоритм отличается только характеристиками коммуникационных операций.

В частности, на этапе инициализации производится перераспределение

блоков матриц А и B при помощи циклического сдвига матричных блоков по

строкам и столбцам процессорной решетки. В случае сети со структурой пол-