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