Алгоритм умножения матрицы
(для простоты возьмем квадратную матрицу) размерности
на вектор
размерности
можно представить как
скалярных умножений векторов, получающихся из строк матрицы
на вектор
.
Если строки матрицы
слоистым образом распределены по процессорам и вектор
хранится на каждом процессоре, то параллельный алгоритм можно
записать следующим образом:
Шаг 1:
на
Шаг 2:
на
Шаг 3:
На втором шаге на каждом процессоре параллельно вычисляются
соответствующие блоки результирующего вектора
,
затем (если это необходимо) на третьем шаге они пересылаются
на первый процессор.
Предположим, что столбцы матрицы
распределены слоистым образом по процессорам. В этом случае
необходимо модифицировать алгоритм с учетом хранения матрицы. Результат
матрично-векторного произведения можно получить, умножив каждый столбец матрицы
на соответствующий элемент вектора
и сложив получившиеся вектора. Степень параллелизма этого
алгоритма меньше, чем в предыдущем, и обусловлена тем, что приходится
осуществлять суммирование.
Условно, по шагам алгоритм записывается следующим образом:
Шаг 1:
на
Шаг 2:
на
Шаг 3:
на
Шаг 4:
Шаг 5:
на
На втором шаге осуществляется покомпонентное умножение векторов, на третьем – частичное суммирование, на четвертом – пересылка частичных сумм на первый процессор, на последнем – завершающее суммирование.
Матрично-векторное умножение обычно является частью более
широкого процесса вычислений и для выбора того или иного алгоритма главную роль
играет способ хранения
и
в момент, когда требуется их произведение. Например, если
и
уже находятся в памяти
-го процессора,
то эффективнее использовать второй алгоритм,
хотя степень параллелизма в нем ниже, чем в первом. Еще один важный фактор при
выборе параллельного алгоритма - желаемое расположение результата по окончании
операции умножения: во втором алгоритме вектор-результат размещается в памяти
одного процессора, тогда как в первом он распределен по процессорам. На рис. 56
приведен текст Фортран-программы, реализующей параллельный алгоритм умножения
матрицы на вектор.
Рис. 56. Пример распараллеливания алгоритма умножения матрицы на вектор
