Последовательный алгоритм
Алгоритм последовательного умножения
заключается в следующем - скалярно умножить i-ю строку матрицы
A на вектор b, получившееся число записать в i-ю
компоненту результирующего вектора с
:
Параллеллный алгоритм с ленточным разделением данных по
строкам
При разделении элементов
матрицы по строкам, каждому процессу распределяется часть строк исходной
матрицы. Строки распределяются последовательно, поровну между всеми процессами.
В результате каждый процесс скалярно умножит отправленные ему строки матицы
A на вектор b и получит часть результирующего вектора
с
. Останется только собрать все части
результата в единый вектор.
Рис.
1.
Организация вычислений при выполнении параллельного алгоритма умножения матрицы
на вектор, основанного на разделении матрицы по
строкам
Параллеллный алгоритм с ленточным
разделением данных по столбцам
При
разделении элементов матрицы по столбцам, каждому процессу распределяется часть
столбцов исходной матрицы. Распределение происходит последовательно, поровну
между всеми процессами. Каждый процесс произведёт скалярное умножение части
i-ой строки исходной матрицы A, состоящей из i-х
элементов присланных столбцов на соответствующую часть вектора b. По
окончании получим на каждом процессе часть компонент результирующего вектора
с. Сложив соответствующие части компонент каждого процесса, получим
результирующий вектор.
Рис.
2.
Организация вычислений при выполнении параллельного алгоритма умножения матрицы
на вектор с использованием разбиения матрицы по столбцам
Параллеллный
алгоритм с блочным разделением данных
При
разделении элементов матрицы на блоки, каждому процессу распределяется блок
элементов исходной матрицы. В результате скалярного умножения строк блока на
соответствующие элементы вектора b, на каждом процессе размещается
часть вектора с. Для сбора результирующего вектора необходимо
просуммировать частичные результаты, затем собрать все компоненты вектора
с в надлежащем порядке.
Рис.
3.
Общая схема параллельного алгоритма умножения матрицы на вектор при блочном
разделении данных: a) исходное распределение результатов, b) распределение
векторов частичных результатов, c) распределение блоков результирующего вектора
c
