Постановка задачи умножения матрицы на вектор

Лабораторная работа

Матрицы и матричные операции широко используются при математическом моделировании самых разнообразных процессов, явлений и систем. Матричные вычисления составляют основу многих научных и инженерных расчетов – среди областей приложений могут быть указаны вычислительная математика, физика, экономика и др. Являясь вычислительно-трудоемкими, матричные вычисления представляют собой классическую область применения параллельных вычислений. С одной стороны, использование высокопроизводительных многопроцессорных систем позволяет существенно повысить сложность решаемых задач. С другой стороны, в силу своей достаточно простой формулировки матричные операции предоставляют прекрасную возможность для демонстрации многих приемов и методов параллельного программирования.

Цель лабораторной работы

Целью данной лабораторной работы является разработка параллельной программы матрично-векторного умножения с использованием в качестве аппаратной платформы многопроцессорной вычислительной системы с общей памятью.

Задачи

– Постановка задачи матрично-векторного умножения.

– Реализация последовательного алгоритма умножения матрицы на вектор.

– Разработка параллельного алгоритма умножения матрицы на вектор.

– Реализация параллельного алгоритма матрично-векторного умножения.

При выполнении лабораторной работы предполагается, что имеющиеся в составе вычислительной системы процессоры обладают равной производительностью, являются равноправными при доступе к общей памяти и время доступа к памяти является одинаковым (при одновременном доступе нескольких процессоров к одному и тому же элементу памяти очередность и синхронизация доступа обеспечивается на аппаратном уровне). Многопроцессорные системы подобного типа обычно именуются симметричными мультипроцессорами (symmetric multiprocessors, SMP). Перечисленному выше набору предположений удовлетворяют также активно развиваемые в последнее время многоядерные процессоры, в которых каждое ядро представляет практически независимо функционирующее вычислительное устройство. Именно многоядерные процессоры (учитывая их новизну и массовый характер распространения) будут использоваться далее для проведения вычислительных экспериментов.

Для общности излагаемого учебного материала, для упоминания одновременно и мультипроцессоров и многоядерных процессоров, при обозначении одного вычислительного устройства будет использоваться понятие вычислительный элемент (ВЭ).

Постановка задачи умножения матрицы на вектор

В результате умножения матрицы А размерности m× n и вектора b, состоящего из n элементов, получается вектор c размера m, каждый i-ый элемент которого есть результат скалярного умножения i-й строки матрицы А (обозначим эту строчку a_i) и вектора b (см. рис. 1.1):

Рис. 1.1. Элемент результирующего вектора – это результат скалярного умножения строки матрицы на вектор

 

Так, например, при умножении матрицы, состоящей из 3 строк и 4 столбцов на вектор из 4 элементов, получается вектор размера 3:

Тем самым, получение результирующего вектора c предполагает повторение m однотипных операций по умножению строк матрицы A и вектора b. Каждая такая операция включает умножение элементов строки матрицы и вектора b и последующее суммирование полученных произведений.

Псевдокод для представленного алгоритма умножения матрицы на вектор может выглядеть следующим образом:

// Serial algorithm of matrix-vector multiplication

for (i = 0; i < m; i++)

{

c[i] = 0;

for (j = 0; j < n; j++)

{

c[i] += A[i][j]*b[j]

}

}