Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
СІ
Кафедра:
Спеціалізовані комп’ютерні системи
Інформація про роботу
Рік:
2025
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
/
Звіт з лабораторної роботи №2
з дисципліни: «Паралельні та розподілені обчислення»
Варіант 14
Мета роботи: вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції.
ЗАВДАННЯ
1.Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат.
2. На основі створеного алгоритму написати програму використовуючи засоби МPI яка дозволяє обчислити вираз та ілюструє проведену декомпозицію для оптимальної кількості процесорів.
3. Дослідити ефективність паралельного обчислення за критерієм часу.
Завдання згідно варіанту
/
Аналіз задачі
Для заданого виразу вхідними даними є:
розмірність матриць – N;
матриці ;
вектори-стовпці .
Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності.
Матриця C2 повинна генеруватись за формулою:
Cij=14/(i +j4)
Вектор стовпець b повинен генеруватись за формулою:
bi=14/(i3) – для парних і
bi=1/(i+14) – для непарних і
Декомпозиція/
Рис.1. Декомпозиція
y1 - результат множення матриці А на вектор-стовпець b є вектор-стовпець.
y2 - результатом множення матриці А1 на вектор-стовпець «14b1+14c1» є вектор-стовпець.
Y3 - результатом множення матриці на матрицю є матриця, та при додаванні матриць результатом буде також матриця.
Y3^3 - матриця
y2y1’ – матриця
y2’Y3 – рядок
y2’Y3y1 – число
y2’Y3y1Y3 - матриця
Y3^3y1y1’ – матриця
Y3^3y1y1’+ y2y1’+ y2’Y3y1Y3 – матриця
Результат роботи
Для тестування MPI ввела вручну кожен елемент матриць та векторів як двійку з розміром матриць та векторів N = 2 із виводом результатів на екран та у файл, кількість процесів 3. Екзешник запускається в терміналі.
/ /
/ /
Рис.2.1 та 2.2. Результати роботи програм
Перевірка в Matlab (лайв скрипт)
Задання векторів та матриць:
i = 1
j = 1
bi = zeros(2,1)
Cij = zeros(2,2)
A2 = [2 2; 2 2]
B2 = [2 2; 2 2]
A = [2 2; 2 2]
A1 = [2 2; 2 2]
b1 = [2; 2]
c1 = [2; 2]
while i<=2
if(mod(i,2) == 0)
bi(i)=14/(i*i*i)
else
bi(i)=1/(i+14)
end
i=i+1
end
i=1
j=1
while i<3
while j<3
Cij(i,j)=14/(i+j*j*j*j)
j=j+1
end
j = 1
i=i+1
end
y1 = A*bi
y2 = A1*((14*b1)+(14*c1))
Y3 = (A2*Cij)-B2
res1 = Y3*Y3*Y3*y1*y1'
res2 = y2*y1'
res3 = y2'*Y3*y1*Y3
X = res1 + res2 + res3
Результат перевірки:
i = 1
j = 1
bi = 2×1
0
0
Cij = 2×2
0 0
0 0
A2 = 2×2
2 2
2 2
B2 = 2×2
2 2
2 2
A = 2×2
2 2
2 2
A1 = 2×2
2 2
2 2
b1 = 2×1
2
2
c1 = 2×1
2
2
bi = 2×1
0.0667
0
i = 2
bi = 2×1
0.0667
1.7500
i = 3
i = 1
j = 1
Cij = 2×2
7 0
0 0
j = 2
Cij = 2×2
7.0000 0.8235
0 0
j = 3
j = 1
i = 2
Cij = 2×2
7.0000 0.8235
4.6667 0
j = 2
Cij = 2×2
7.0000 0.8235
4.6667 0.7778
j = 3
j = 1
i = 3
y1 = 2×1
3.6333
3.6333
y2 = 2×1
224
224
Y3 = 2×2
21.3333 1.2026
21.3333 1.2026
res1 = 2×2
105 ×
1.5109 1.5109
1.5109 1.5109
res2 = 2×2
813.8667 813.8667
813.8667 813.8667
res3 = 2×2
105 ×
7.8256 0.4411
7.8256 0.4411
X = 2×2
105 ×
9.3446 1.9602
9.3446 1.9602
Вміст файлу 0.txt:
N = 2.000000
Cij =
7.000000 0.823529
4.666667 0.777778
bi =
0.066667
1.750000
c1 =
2.000000
2.000000
A2 =
2.000000 2.000000
2.000000 2.000000
B2 =
2.000000 2.000000
2.000000 2.000000
A1 =
2.000000 2.000000
2.000000 2.000000
A =
2.000000 2.000000
2.000000 2.000000
b1 =
2.000000
2.000000
A2*C2 =
23.333332 3.202614
23.333332 3.202614
Y3 =
21.333332 1.202614
21.333332 1.202614
Y3^2= =
480.766815 27.102053
480.766815 27.102053
Y3^3= =
10834.535156 610.770386
10834.535156 610.770386
y2y1' = =
813.866699 813.866699
813.866699 813.866699
y2'Y3y1Y3 = =
782560.187500 44114.914062
782560.187500 44114.914062
Y3^3y1y1' = =
151090.765625 151090.765625
151090.765625 151090.765625
X =
934464.812500 196019.531250
934464.812500 196019.531250
Вміст файлу 1.txt:
N = 2.000000
b1 =
2.000000
2.000000
c1 =
2.000000
2.000000
14 * b1 + 14 * c1 =
56.000000
56.000000
A1 =
2.000000 2.000000
2.000000 2.000000
y2= =
224.000000
224.000000
y1= =
3.633333
3.633333
y2y1' =
813.866699 813.866699
813.866699 813.866699
y2'Y3 =
9557.333008 538.771240
y2'Y3y1 = 36682.511719
y2'Y3y1Y3' =
782560.187500 44114.914062
782560.187500 44114.914062
Вміст файлу 2.txt:
N = 2.000000
bij = =
0.066667
1.750000
y1=A*bi =
3.633333
3.633333
Y3^3 =
10834.535156 610.770386
10834.535156 610.770386
Y3^3y1 =
41584.613281
41584.613281
Y3^3y1y1' = =
151090.765625 151090.765625
151090.765625 151090.765625
y2'Y3 =
9557.333008 538.771240
y2'Y3y1 = 36682.511719
Вміст файлу consistent.txt:
N = 2.000000
Cij =
7.000000 0.823529
4.666667 0.777778
bi =
0.066667
1.750000
c1 =
2.000000
2.000000
A2 =
2.000000 2.000000
2.000000 2.000000
B2 =
2.000000 2.000000
2.000000 2.000000
A1 =
2.000000 2.000000
2.000000 2.000000
A =
2.000000 2.000000
2.000000 2.000000
b1 =
2.000000
2.000000
A2*C2 =
23.333332 3.202614
23.333332 3.202614
Y3 =
21.333332 1.202614
21.333332 1.202614
Y3^2= =
480.766815 27.102053
480.766815 27.102053
Y3^3= =
10834.535156 610.770386
10834.535156 610.770386
14 * b1 + 14 * c1 =
56.000000
56.000000
y2= =
224.000000
224.000000
y1=A*bi =
3.633333
3.633333
y2y1' =
813.866699 813.866699
813.866699 813.866699
y2'Y3 =
9557.333008 538.771240
Y3^3y1 =
41584.613281
41584.613281
Y3^3y1y1' = =
151090.765625 151090.765625
151090.765625 151090.765625
y2'Y3y1 = 36682.511719
y2'Y3y1Y3' =
782560.187500 44114.914062
782560.187500 44114.914062
X =
934464.812500 196019.531250
934464.812500 196019.531250
Текст програми (MPI)
Header.h:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include "math.h"
#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
//Operations
float** dobytok_2_matruc(int rozmir, float** matrix1, float** matrix2);
float** dobytok_matrix_vectorStovpec(int rozmir, float** matrix, float** vector);
float* dobytok_vectorRjadok_matrix(int rozmir, float** matrix, float* vector);
float** transp_vectorRjadka(int rozmir, float** vector);
float* transp_vectorStovpcja(int rozmir, float** vector);
float dobytok_Rjadka_na_Stovbec(int rozmir, float** vectorS, float* vectorR);
float** dobytok_Stovbec_na_Rjadok(int rozmir, float** vectorS, float* vectorR);
float** dobytok_chislo_na_Stovbec(int rozmir, float number, float** vectorS);
float** dobytok_chisla_na_matrix(int rozmir, float numb, float** matrix);
//initialization
void vector_Column(float**& V, int size);
void vector_Row(float*& V, int size);
void matrix(float**& M, int size);
void number(float**& Numb);
//file
void write_to_file(ofstream& fx, float** MRC, int N, int processor, char whatIs, char* name);
void write_to_file_ROW(ofstream& fx, float* MRC, int N, int processor, char* name); //Прибрати зайві параметри за потреби
void write_to_file1(ofstream& fx, float MRC, int N, int processor, char* name);
//input
void manual_input(int& N, float**& C, float**& b, float**& c1, float**& A2, float**& B2, float**& A1, float**& A, float**& b1);
void auto_input(int& N, float**& C, float**& b, float**& c1, float**& A2, float**& B2, float**& A1, float**& A, float**& b1);
void CPU_0();
void CPU_1();
void CPU_2();
WtFile.cpp:
#include "Header.h"
void write_to_file(ofstream& fx, float** MRC, int N, int processor, char whatIs, char* name)
{
fx.setf(ios::fixed);
const char* path;
if (processor == 0) path = "D:\\0.txt";
else if (processor == 1) path = "D:\\1.txt";
else if (processor == 2) path = "D:\\2.txt";
else {
cout << "Error: bad processor = " << processor << endl;
path = "D:\\Error.txt";
}
if (whatIs == 'M')
{
fx.open(path, std::ofstream::out | std::ofstream::app);
fx << name << " = \r\n";
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++) {
fx.width(10);
fx.fixed;
fx << MRC[i][j] << "\t";
}
fx << "\r\n";
}fx << "\r\n\n\n";
fx.close();
}
else if (whatIs == 'R')
{
fx.open(path, std::ofstream::out | std::ofstream::app);
fx << name << " = \r\n";
for (int i = 0; i < N; i++) {
fx.width(10);
fx.fixed;
fx << MRC[0][i] << "\t";
}
fx << "\r\n\n\n";
fx.close();
}
else if (whatIs == 'C')
{
fx.open(path, std::ofstream::out | std::ofstream::app);
fx << name << " = \r\n";
for (int i = 0; i < N; i++) {
fx.width(10);
fx.fixed;
fx << MRC[i][0] << "\r\n";
}fx << "\r\n\n\n";
fx.close();
}
else if (whatIs == 'N')
{
fx.open(path, std::ofstream::out | std::ofstream::app);
fx << name << " = " << MRC[0][0] << "\r\n";
fx.close();
}
else
{
cout << "Error: bad type to write into file, proc = " << processor << endl;
}
}
void write_to_file_ROW(ofstream& fx, float* MRC, int N, int processor, char* name)
{
fx.setf(ios::fixed);
const char* path;
if (processor == 0) path = "D:\\0.txt";
else if (processor == 1) path = "D:\\1.txt";
else if (processor == 2) path = "D:\\2.txt";
else {
cout << "Error: bad processor = " << processor << endl;
path = "D:\\Error.txt";
}
fx.open(path, std::ofstream::out | std::ofstream::app);
fx << name << " = \r\n";
for (int i = 0; i < N; i++) {
fx.width(10);
fx.fixed;
fx << MRC[i] << "\t";
}
fx << "\r\n\n\n";
fx.close();
}
void write_to_file1(ofstream& fx, float MRC, int N, int processor, char* name)
{
fx.setf(ios::fixed);
const char* path;
if (processor == 0) path = "D:\\0.txt";
else if (processor == 1) path = "D:\\1.txt";
else if (processor == 2) path = "D:\\2.txt";
else {
cout << "Error: bad processor = " << processor << endl;
path = "D:\\Error.txt";
}
fx.open(path, std::ofstream::out | std::ofstream::app);
fx << name << " = " << MRC << "\r\n";
fx.close();
}
input.cpp:
#include "Header.h"
#include <cmath>
ofstream fio;
void manual_input(int& N, float**& C, float**& b, float**& c1, float**& A2, float**& B2, float**& A1, float**& A, float**& b1)
{
//enter N
cout << "Enter size (N): ";
cin >> N;
float NN = N;
write_to_file1(fio, NN, N, 0, (char*)"N");
//generate Cij
matrix(C, N);
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
C[i-1][j-1] = (float)14 / (float)(i + pow(j,4));
}
}
write_to_file(fio, C, N, 0, 'M', (char*)"Cij");
//generate b (bi) -- вектор-стовпець
vector_Column(b, N);
for (int i = 1; i <= N; i++)
{
if (i % 2 == 0) {
b[i - 1][0] = (float)14 / (float)(pow(i,3));
}
else
{
b[i - 1][0] = (float)1 / (float)(i+14);
}
}
write_to_file(fio, b, N, 0, 'C', (char*)"bi");
//generate c1 -- вектор-рядок
vector_Column(c1, N);
cout << "Vector Column c1 = " << endl;
for (int j = 0; j < N; j++)
{
cout << "c1[" << j << "]=";
cin >> c1[j][0];
}
write_to_file(fio, c1, N, 0, 'C', (char*)"c1");
//generate A2
matrix(A2, N);
cout << endl << "Matrix A2 = " << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << "A2[" << i << "][" << j << "]=";
cin >> A2[i][j];
}
}
write_to_file(fio, A2, N, 0, 'M', (char*)"A2");
//generate B2
matrix(B2, N);
cout << "Matrix B2 = " << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << "B2[" << i << "][" << j << "]=";
cin >> B2[i][j];
}
}
write_to_file(fio, B2, N, 0, 'M', (char*)"B2");
//generate A1
matrix(A1, N);
cout << "Matrix A1 = " << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << "A1[" << i << "][" << j << "]=";
cin >> A1[i][j];
}
}
write_to_file(fio, A1, N, 0, 'M', (char*)"A1");
//generate A
matrix(A, N);
cout << "Matrix A = " << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << "A[" << i << "][" << j << "]=";
cin >> A[i][j];
}
}
write_to_file(fio, A, N, 0, 'M', (char*)"A");
//generate b1 -- вектор-рядок
vector_Column(b1, N);
cout << "Vector Column b1 = " << endl;
for (int j = 0; j < N; j++)
{
cout << "b1[" << j << "]=";
cin >> b1[j][0];
}
write_to_file(fio, b1, N, 0, 'C', (char*)"b1");
cout << endl << "Thanks!" << endl;
}
//Початковий ввід (генерація) даних
void auto_input(int& N, float**& C, float**& b, float**& c1, float**& A2, float**& B2, float**& A1, float**& A, float**& b1)
{
//enter N
cout << "Enter size (N): ";
cin >> N;
float NN = N;
write_to_file1(fio, NN, N, 0, (char*)"N");
//generate Cij
matrix(C, N);
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
C[i - 1][j - 1] = (float)14 / (float)(i + pow(j, 4));
}
}
write_to_file(fio, C, N, 0, 'M', (char*)"Cij");
//generate b (bij) -- вектор-стовпець
vector_Column(b, N);
for (int i = 1; i <= N; i++)
{
if (i % 2 == 0) {
b[i - 1][0] = (float)14 / (float)(pow(i, 3));
}
else
{
b[i - 1][0] = (float)1 / (float)(i + 14);
}
}
write_to_file(fio, b, N, 0, 'C', (char*)"bi");
//generate c1 -- вектор-рядок
vector_Column(c1, N);
for (int j = 0; j < N; j++)
{
c1[j][0] = rand() % 9 + 1;
}
write_to_file(fio, c1, N, 0, 'C', (char*)"c1");
//generate A2
matrix(A2, N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
A2[i][j] = rand() % 9 + 1;
}
}
write_to_file(fio, A2, N, 0, 'M', (char*)"A2");
//generate B2
matrix(B2, N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
B2[i][j] = rand() % 9 + 1;
}
}
write_to_file(fio, B2, N, 0, 'M', (char*)"B2");
//generate A1
matrix(A1, N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
A1[i][j] = rand() % 9 + 1;
}
}
write_to_file(fio, A1, N, 0, 'M', (char*)"A1");
//generate A
matrix(A, N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
A[i][j] = rand() % 29 + 1;
}
}
write_to_file(fio, A, N, 0, 'M', (char*)"A");;
//generate b1 -- вектор-рядок
vector_Column(b1, N);
for (int j = 0; j < N; j++)
{
b1[j][0] = rand() % 9 + 1;
}
write_to_file(fio, b1, N, 0, 'C', (char*)"b1");
}
main.cpp:
#include "Header.h"
#include <chrono>
//main
int main(int argc, char* argv[])
{
//видалення файлів попередньої сесії, якщо такі існують
remove("D:\\0.txt");
remove("D:\\1.txt");
remove("D:\\2.txt");
//початок основної програми
int procCnt = 0, procNumb;
MPI_Init(&argc, &argv); /*START MPI
28.08.2022 13:08-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора