Определение подзадач и выделение информационных зависимостей

Умножение матрицы на вектор при разделении данных по столбцам

Рассмотрим теперь другой подход к параллельному умножению матрицы на вектор, основанный на разделении исходной матрицы на непрерывные наборы (вертикальные полосы) столбцов.

При таком способе разделения данных в качестве базовой подзадачи может быть выбрана операция умножения столбца матрицы А на один из элементов вектора b. Для организации вычислений в этом случае каждая базовая подзадача i, 0 i<n, должна содержать i-й столбец матрицы А и i-е элементы b_i и c_i векторов b и с.

Параллельный алгоритм умножения матрицы на вектор начинается с того, что каждая базовая задача i выполняет умножение своего столбца матрицы А на элемент b_i, в итоге в каждой подзадаче получается вектор c'(i) промежуточных результатов. Далее для получения элементов результирующего вектора с подзадачи должны обменяться своими промежуточными данными между собой (элемент j, 0 j<n, частичного результата c'(i) подзадачи i, 0 i<n, должен быть передан подзадаче j). Данная обобщенная передача данных (all-to-all communication или total exchange) является наиболее общей коммуникационной процедурой и может быть реализована при помощи функции MPI_Alltoall библиотеки MPI. После выполнения передачи данных каждая базовая подзадача i, 0 i<n, будет содержать n частичных значений c'_i(j), 0 j<n, сложением которых и определяется элемент c_i вектора результата с (см. рис. 6.5).

Рис. 6.5. Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор с использованием разбиения матрицы по столбцам

Дата добавления: 2015-06-28