ВУЗ:
Составители:
130
10.2. Параллельные алгоритмы при ленточном разбиении матрицы
Рассмотрим два параллельных алгоритма умножения матриц с ленточным
разбиением на строки или столбцы (полосы). Если каждая подзадача содержит
по одной строке матрицы А и одному столбцу матрицы В, общее число подза-
дач (необходимых процессоров) равно n
2
. При большой размерности матриц
это может быть неприемлемо. Чаще декомпозицию осуществляют таким обра-
зом, что подзадача заключается в вычислении элементов одной строки матрицы
С. При этом количество подзадач (потребных процессоров) равно n. Далее рас-
смотрим именно этот случай.
Для выполнения всех вычислений в подзадаче процессору должны быть
доступны одна из строк матрицы A и все столбцы матрицы B. Если дублирова-
ние матрицы B во всех подзадачах неприемлемо в силу большой размерности
матрицы, необходимо строить итерационный процесс с обменом данными ме-
жду процессорами. Возможны две схемы организации вычислений с обменом
данными.
Первый алгоритм. На каждой итерации каждая подзадача содержит по од-
ной строке матрицы А и одному столбцу матрицы В. При выполнении итерации
проводится скалярное умножение содержащихся в подзадачах строк и столб-
цов, что приводит к получению соответствующих элементов результирующей
матрицы С. В конце каждой итерации столбцы матрицы В передаются между
подзадачами. Процесс передачи организуется так, чтобы после завершения ите-
раций в каждой подзадаче последовательно «побывали» все столбцы матрицы
В.
Для указанной схемы передачи данных наиболее подходящей является то-
пология связей подзадач в виде кольцевой структуры. При этом на каждой ите-
рации подзадача i, 0 i<n передает свой столбец матрицы В подзадаче с номером
i+1 , а подзадача n-1 передает свои данные подзадаче с номером 0. На рис. 10.1
приведены граф-схема и временная диаграмма алгоритма перемножения мат-
риц для случая, когда матрицы состоят из четырех строк и четырех столбцов
(n=4).
Страницы
- « первая
- ‹ предыдущая
- …
- 128
- 129
- 130
- 131
- 132
- …
- следующая ›
- последняя »
