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

Страницы работы

69 страниц (Word-файл)

Фрагмент текста работы

Нижегородскийгосударственныйуниверситет им. Н.И.Лобачевского

ФакультетВычислительнойматематикиикибернетики

Образовательныйкомплекс

Введениевметодыпараллельного программирования

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

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

Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

Содержание

Упражнения:

‰  Постановка задачи

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

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

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

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

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

или

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

Упражнение 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

int Size;         // Sizes of initial matrix and 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):

// Function for process initialization void ProcessInitialization (double* &pMatrix, double* &pVector, double* &pResult, int &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) с контролем ошибочных ситуаций:

// Function for process initialization void ProcessInitialization (double* &pMatrix, double* &pVector, double* &pResult, int &Size) { // Setting the size of the initial matrix and the vector do { printf("\nEnter size of the initial objects: "); scanf("%d", &Size); printf("\nChosen objects’ size = %d", Size); if (Size <= 0) printf("\nSize of objects must be greater than 0!\n");

}

while (Size <= 0);

}

:

матрично-векторногоумножения

‰  Задание 2 – Ввод размеров объектов:…

–  Добавьте вызов функции ProcessInitialization в основную функцию приложения:

void main() { 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"); // Process initializattion

ProcessInitialization(pMatrix, pVector, pResult, Size); getch();

}


‰  Задание 2 – Ввод размеров объектов:

–  Скомпилируйте и запустите приложение:

‰  Задание 3 – Ввод данных:… – Выделение памяти:

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

// Setting the size of the initial matrix and the vector <…>

// 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 – Ввод данных:…

–  Функция для простого определения значений элементов исходных

Похожие материалы

Информация о работе