Нижегородскийгосударственныйуниверситет
им. Н.И.Лобачевского
ФакультетВычислительнойматематикиикибернетики
Образовательныйкомплекс
Введениевметодыпараллельного
программирования
Лабораторнаяработа 1.
Параллельныеалгоритмы матрично-векторногоумножения
Гергель
В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ
Упражнения:
Постановка задачи
Реализация последовательного алгоритма умножения матрицы на вектор
Разработка
параллельного алгоритма умножения матрицы на вектор
Реализация параллельного алгоритма матричновекторного умножения
Умножение матрицы на вектор c = A⋅b
или
⎛c0 ⎞ ⎛ a0,0, a0,1, ..., a0,n−1 ⎞⎛b0 ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜c1
⎟=⎜ ...⎟⎜b1
⎟
⎜cm−1 ⎟⎠ ⎜⎝am−1,0, am−1,1, ..., am−1,n−1 ⎟⎠⎜⎝bn−1 ⎟⎠ ⎝
ª Задача умножения матрицы на вектор может быть сведена к выполнению m независимых операций умножения строк матрицы A на вектор b n
ci =(ai ,b)=∑ai jbj , 0 ≤ i < m
j=1
|
// 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] } } |
Для выполнения матрично-векторного умножения необходимо выполнить m операций вычисления скалярного произведения
Трудоемкость вычислений имеет порядок O(mn)
Поэтапнаяразработкапоследовательногоалгоритма:
– Задание 1 – Открытие проекта SerialMatrixVectorMult
– Задание 2 – Ввод размеров объектов
– Задание 3 – Ввод данных
– Задание 4 – Завершение процесса вычислений
– Задание 5 – Реализация умножения матрицы на вектор
– Задание 6 – Проведение вычислительных экспериментов
Задание 1 – Открытие проекта SerialMatrixVectorMult:…
– Запустите приложение Microsoft Visual Studio 2005,
– Откройте проект SerialMatrixVector.sln, расположенный в папке C:\MsLabs\SerialMatrixVector,
– При
помощи окна Solution Explorer откройте файл SerialMV.cpp 
Задание 1 – Открытие проекта SerialMatrixVectorMult:
– Переменные, которые будут использоваться в программе:
|
double* pMatrix; // Initial matrix double* pVector; // Initial vector double* pResult; // Result vector
|
– Вывод начального сообщения и ожидание нажатия любой клавиши перед завершением выполнения приложения:
printf ("Serial matrix-vector multiplication program\n"); getch();
Задание 2 – Ввод размеров объектов:…
– Для задания исходных данных реализуем функцию
ProcessInitialization:
• определяет размеры матрицы и вектора,
• выделяет память для всех
объектов, участвующих в умножении (pMatrix, pVector и pResult),
• задает значения элементов исходных матрицы и вектора
// Function for process intialization void ProcessInitialization (double* &pMatrix, double* &pVector, double* &pResult, int &Size);
:
Задание 2 – Ввод размеров объектов:…
– Определение размеров объектов (задание значения переменной Size):
|
// Setting the size of the initial matrix and the vector printf("\nEnter the size of the initial objects: "); scanf("%d", &Size); printf("\nChosen objects’ size = %d", Size); } |
Задание 2 – Ввод размеров объектов:…
– Определение размеров объектов (задание значения переменной Size) с контролем ошибочных ситуаций:
|
} while (Size <= 0); } |
:
Задание 2 – Ввод размеров объектов:…
– Добавьте вызов функции ProcessInitialization в основную функцию приложения:
|
double* pResult; // Result vector int Size; // Sizes of initial matrix and vector printf ("Serial matrix-vector multiplication program\n"); // Process initializattion ProcessInitialization(pMatrix, pVector, pResult, Size); getch(); } |
Задание 2 – Ввод размеров объектов:
– Скомпилируйте и запустите приложение:
Задание 3 – Ввод данных:… – Выделение памяти:
|
// Function for process initialization void ProcessInitialization (double* &pMatrix, double* &pVector, double* &pResult, int &Size) {
// Memory allocation pMatrix = new double [Size*Size]; pVector = new double [Size]; pResult = new double [Size]; } |
Задание 3 – Ввод данных:…
– Определение значений элементов исходных матрицы и
|
вектора по шаблону: |
||
|
⎛0 0 ⎜ pMatrix=⎜⎜12 12 ⎜ ⎜3 3 ⎝ |
0
1 2 3 |
0⎞ ⎛1⎞ ⎟ ⎜ ⎟ 1⎟ ⎜1⎟ 2⎟, pVector=⎜1⎟ ⎟ ⎜ ⎟ 3⎟⎠ ⎜⎝1⎟⎠ |
:
Задание 3 – Ввод данных:…
– Функция для простого определения значений элементов исходных
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
