Теория и практика параллельных вычислений
Выделение информационных зависимостей
Рассмотрим общую схему параллельных вычислений для операции умножения матрицы на вектор при блочном разделении исходных данных. После перемножения блоков матрицы A и вектора b каждая подзадача (i,j) будет содержать вектор частичных результатов c'(i,j), определяемый в соответствии с выражениями
Поэлементное суммирование векторов частичных результатов для каждой горизонтальной полосы (данная процедура часто именуется операцией редукции – см. лекцию 3) блоков матрицы A позволяет получить результирующий вектор c
Для размещения вектора c применим ту же схему, что и для исходного вектора b: организуем вычисления таким образом, чтобы при завершении расчетов вектор c располагался поблочно в каждой из вертикальных полос блоков матрицы A (тем самым, каждый блок вектора c должен быть продублирован по каждой горизонтальной полосе). Выполнение всех необходимых действий для этого – суммирование частичных результатов и дублирование блоков результирующего вектора — может быть обеспечено при помощи функции MPI_Allreduce библиотеки MPI.
Общая схема выполняемых вычислений для умножения матрицы на вектор при блочном разделении данных показана на рис. 6.8.
Рис. 6.8. Общая схема параллельного алгоритма умножения матрицы на вектор при блочном разделении данных: a) исходное распределение результатов, б) распределение векторов частичных результатов, в) распределение блоков результирующего вектора c
Рассмотрев представленную схему параллельных вычислений, можно сделать вывод, что информационная зависимость базовых подзадач проявляется только на этапе суммирования результатов перемножения блоков матрицы A и блоков вектора b. Выполнение таких расчетов может быть выполнено по обычной каскадной схеме (см. лекцию 3), и, как результат, характер имеющихся информационных связей для подзадач одной и той же горизонтальной полосы блоков соответствует структуре двоичного дерева.
Для выполнения базовой подзадачи скалярного произведения процессор должен содержать соответствующую строку матрицы А и копию вектора b. После завершения вычислений каждая базовая подзадача определяет один из элементов вектора результата c.
Для объединения результатов расчета и получения полного вектора c на каждом из процессоров вычислительной системы необходимо выполнить операцию обобщенного сбора данных (см. лекцию 4), в которой каждый процессор передает свой вычисленный элемент вектора c всем остальным процессорам. Этот шаг можно выполнить, например, с использованием функции MPI_Allgather из библиотеки MPI.
В общем виде схема информационного взаимодействия подзадач в ходе выполняемых вычислений показана на рис. 6.2.
Рис. 6.2. Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на разделении матрицы по строкам
