Лабораторная работа. Параллельные алгоритмы матрично-векторного умножения

Содержание

Слайд 2

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнения:
Постановка задачи
Реализация последовательного алгоритма умножения матрицы на вектор
Способы распределения данных
Разработка параллельного алгоритма, основанного на разделении матрицы по строкам
Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам
Разработка параллельного алгоритма, основанного на блочном разделении матрицы

Содержание

Слайд 3

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Умножение матрицы на вектор

или

⮲ Задача умножения матрицы на вектор может быть сведена к выполнению m независимых операций умножения строк матрицы A на вектор b

Упражнение 1: Постановка задачи…

Слайд 4

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Для выполнения матрично-векторного умножения необходимо выполнить m операций вычисления скалярного произведения
Трудоемкость вычислений имеет порядок O(mn)

// 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]
}
}

Упражнение 1: Постановка задачи

Слайд 5

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Поэтапная разработка последовательного алгоритма:
Задание 1 – Создание проекта MatrixVectorMult
Задание 2 – Определение размеров объектов и ввод данных
Задание 3 – Завершение процесса вычислений
Задание 4 – Реализация умножения матрицы на вектор
Задание 5 – Проведение вычислительных экспериментов

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

Слайд 6

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 1 – Создание проекта MatrixVectorMult:
Переменные, которые будут использоваться в программе:
Вывод начального сообщения и ожидание нажатия любой клавиши перед завершением выполнения приложения:

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

double* pMatrix; // Initial matrix
double* pVector; // Initial vector
double* pResult; // Result vector
int Size; // Sizes of initial matrix and vector

printf ("Serial matrix-vector multiplication program\n");
getch();

Слайд 7

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 2 – Определение размеров объектов и ввод данных:…
Для задания исходных данных реализуем функцию ProcessInitialization:
определяет размеры матрицы и вектора,
выделяет память для всех объектов, участвующих в умножении (pMatrix, pVector и pResult),
задает значения элементов исходных матрицы и вектора

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

// Function for process intialization
void ProcessInitialization (double* &pMatrix,
double* &pVector, double* &pResult, int &Size);

Слайд 8

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 2 – Определение размеров объектов и ввод данных:…
Определение значений элементов исходных матрицы и вектора по шаблону:

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

Слайд 9

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 2 – Определение размеров объектов и ввод данных:…
Функция для простого определения значений элементов исходных матрицы и вектора:
Функция для задания значений элементов матрицы и вектора при помощи датчика случайных чисел:

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

// Function for simple data initialization
void DummyDataInitialization (double* pMatrix,
double* pVector, int Size)

// Function for random initialization of object elements
void RandomDataInitialization (double* pMatrix,
double* pVector,int Size)

Слайд 10

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 2 – Определение размеров объектов и ввод данных:…
Для контроля правильности задания исходных данных необходимо разработать:
Функцию для форматированной печати матрицы PrintMatrix (входные параметры - матрица pMatrix, количество строк RowCount и количество столбцов ColCount),
Функцию для форматированной печати вектора PrintVector (входные параметры - вектор pVector и количество элементов в векторе Size)

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

Слайд 11

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 2 – Определение размеров объектов и ввод данных:
Контроль правильности выполнения этапа задания исходных данных:

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

Слайд 12

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 3 – Завершение процесса вычислений:
Функция для корректного завершения процесса вычислений ProcessTermination:
Освобождает память, выделенную в ходе выполнения программы,
Входные параметры - матрица pMatrix и векторы pVector и pResult

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

Слайд 13

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 4 – Реализация умножения матрицы на вектор:…
Функция ResultCalculation выполняет умножение матрицы на вектор в соответствии с алгоритмом, изложенным в упражнении 1:

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

// Function for matrix-vector multiplication
void ResultCalculation (double* pMatrix, double* pVector,
double* pResult, int Size) {
int i, j; // Loop variables
for (i=0; i pResult[i] = 0;
for (j=0; j pResult[i] += pMatrix[i*Size+j]*pVector[j];
}
}

Слайд 14

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Задание 4 – Реализация умножения матрицы на вектор:

Упражнение 2: Реализация последовательного алгоритма умножения матрицы на вектор…

Слайд 15

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

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

Задание 5 – Проведение вычислительных экспериментов:
Замените вызов функции DummyDataInitialization на RandomDataInitialization в функции ProcessInitialization,
Добавьте вычисление и вывод времени выполнения умножения,
Измерьте времена работы алгоритма умножения матрицы на вектор при различных количествах исходных данных,
Заполните таблицу результатов вычислений

Слайд 16

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Непрерывное (последовательное) распределение

Упражнение 3: Способы распределения данных…

горизонтальные полосы

вертикальные полосы

Слайд 17

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Чередующееся (цикличное) горизонтальное разбиение

Упражнение 3: Способы распределения данных…

Слайд 18

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 3: Способы распределения данных

Слайд 19

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам…

Распределение данных – ленточная схема (разбиение матрицы по строкам)

Базовая подзадача - операция скалярного умножения одной строки матрицы на вектор

Слайд 20

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам…

Схема параллельного выполнения:

Слайд 21

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Программная реализация:

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам…

// Function for calculating matrix-vector multiplication
void ParallelResultCalculation(double* pMatrix, double* pVector,
double* pResult, int Size) {
int i, j; // Loop variables
#pragma omp parallel for private (j)
for (i=0; i pResult[i] = 0;
for (j=0; j pResult[i] += pMatrix[i*Size+j]*pVector[j];
}
}

Слайд 22

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам…

Проведение вычислительных экспериментов:
Добавьте вычисление и вывод времени выполнения параллельного алгоритма умножения матрицы на вектор,
Проведите вычислительные эксперименты,
Измерьте времена работы умножения матрицы на вектор при различных количествах исходных данных
Определите получаемое ускорение,
Заполните таблицу результатов вычислений

Слайд 23

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Desk-side T-Forge Mini cluster
AMD Opteron® 275 2.2 GHz dual core processors
RAM 4 GB

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам…

Слайд 24

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам…

Intel Core 2 CPU 6300 1.86 GHz, 2 GB RAM

Слайд 25

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 4: Разработка параллельного алгоритма, основанного на разделении матрицы по строкам

Pentium D 820 2.8 GHz, 2 GB RAM

Слайд 26

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам…

Распределение данных – ленточная схема (разбиение матрицы по столбцам)

Базовая подзадача - операция умножения столбца матрицы А на один из элементов вектора b

Слайд 27

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам…

Схема параллельного выполнения:

Слайд 28

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Программная реализация:

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам…

// Function for calculating matrix-vector multiplication
void ParallelResultCalculation(double* pMatrix, double* pVector,
double* pResult, int Size) {
int i, j; // Loop variables
double IterGlobalSum = 0;
for (i=0; i IterGlobalSum = 0;
#pragma omp parallel for reduction(+:IterGlobalSum)
for (j=0; j IterGlobalSum += pMatrix[i*Size+j]*pVector[j];
pResult[i] = IterGlobalSum;
}
}

Слайд 29

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам…

Проведение вычислительных экспериментов:
Добавьте вычисление и вывод времени выполнения параллельного алгоритма умножения матрицы на вектор,
Проведите вычислительные эксперименты,
Измерьте времена работы умножения матрицы на вектор при различных количествах исходных данных
Определите получаемое ускорение,
Заполните таблицу результатов вычислений

Слайд 30

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам…

Desk-side T-Forge Mini cluster
AMD Opteron® 275 2.2 GHz dual core processors
RAM 4 GB

Слайд 31

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам…

Intel Core 2 CPU 6300 1.86 GHz, 2 GB RAM

Слайд 32

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 5: Разработка параллельного алгоритма, основанного на разделении матрицы по столбцам

Pentium D 820 2.8 GHz, 2 GB RAM

Слайд 33

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки…

Распределение данных – блочная схема

Базовая подзадача – умножение блока матрицы A на блок вектора b

Слайд 34

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки…

Схема параллельного выполнения:

Слайд 35

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Программная реализация
Code

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки…

Слайд 36

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки…

Проведение вычислительных экспериментов:
Добавьте вычисление и вывод времени выполнения параллельного алгоритма умножения матрицы на вектор,
Проведите вычислительные эксперименты,
Измерьте времена работы умножения матрицы на вектор при различных количествах исходных данных
Определите получаемое ускорение,
Заполните таблицу результатов вычислений

Слайд 37

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки…

Desk-side T-Forge Mini cluster
AMD Opteron® 275 2.2 GHz dual core processors
RAM 4 GB

Слайд 38

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки…

Intel Core 2 CPU 6300 1.86 GHz, 2 GB RAM

Слайд 39

Н.Новгород, 2007 г. Основы параллельных вычислений: Умножение матрицы на вектор ©

Н.Новгород, 2007 г.

Основы параллельных вычислений: Умножение матрицы на вектор © Гергель

В.П.

Упражнение 6: Разработка параллельного алгоритма, основанного на разделении матрицы на блоки

Pentium D 820 2.8 GHz, 2 GB RAM