Теория и практика параллельных вычислений
Умножение матрицы на вектор при блочном разделении данных
Рассмотрим теперь параллельный алгоритм умножения матрицы на вектор, который основан на ином способе разделения данных – на разбиении матрицы на прямоугольные фрагменты (блоки). При таком способе разделения данных исходная матрица A представляется в виде набора прямоугольных блоков. Вектор b также должен быть разделен на блоки. Блоки матрицы и блоки вектора распределены между процессорами вычислительной системы. Логическая (виртуальная) топология вычислительной системы в данном случае имеет вид прямоугольной двумерной решетки. Размеры процессорной решетки соответствуют количеству прямоугольных блоков, на которые разбита матрица A. На процессоре pi,j, находящемся на пересечении i-й строки и j-го столбца процессорной решетки, располагается блок Ai,j матрицы A и блок bj вектора b.
После перемножения блоков матрицы A и вектора b каждый процессор pi,j будет содержать вектор частичных результатов c'(i,j). Поэлементное суммирование векторов частичных результатов для каждой горизонтальной строки процессорной решетки позволяет получить результирующий вектор c.
Задания и упражнения
- Запустите систему ПараЛаб. Установите количество процессоров, равное четырем.
- Выполните три последовательных эксперимента с использованием трех различных алгоритмов умножения матрицы на вектор — алгоритмов, основанных на горизонтальном, вертикальном и блочном разбиении матрицы. Сравните временные характеристики алгоритмов, которые отображаются в правой нижней части окна. Убедитесь в том, что у алгоритмов, основанных на ленточном разбиении матрицы, время выполнения практически совпадает, а также в том, что время выполнения алгоритма, основанного на блочном разбиении, несколько больше.
- Измените объем исходных данных (выполните команду Параметры задачи пункта меню Задача). Снова проведите эксперименты. Сравните временные характеристики алгоритмов.
- Измените количество процессоров, установите количество процессоров, равное 16 (выполните команду Количество процессоров пункта меню Система). Проведите вычислительные эксперименты и сравните временные характеристики.
