Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ ЗАСОБАМИ MPI
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЕОМ
/
ЗВІТ ДО ЛАБОРАТОРНОЇ РОБОТИ №1
з дисципліни:
«Паралельні та розподілені обчислення»
на тему:
«ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ ЗАСОБАМИ MPI»
Варіант №26
МЕТА РОБОТИ: Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції. Освоїти інструменти бібліотеки MPI для реалізації декомпозиції задач.
1. Завдання
1.Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат .
2. На основі створеного алгоритму написати програму використовуючи засоби МPI яка дозволяє обчислити вираз та ілюструє проведену декомпозицію для кількості процесорів заданих у варіанті.
1.1. Завдання згідно варіанту
Номер варіанту
Вираз який треба обчислити
К-сть процесорів
Вектор y1
Вектор y2
Матриця Y3
26
матриця
6
bi=i3+3i2-i/(2+i)
( b1c1‘A1c1’)’
A2(B2+26C2)
Cij=1/(i2+j)
2. Аналіз задачі
Для заданого виразу вхідними даними є:
розмірність матриць – N;
матриці ;
вектори-стовпці .
Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності.
Матриця C2 повинна генеруватись за формулою:
Cij=1/(i2+j)
Вектор стовпець b повинен генеруватись за формулою:
bi=i3+3i2-i/(2+i)
3. Декомпозиція
При утворенні y1 враховуємо, що результатом множення матриці А на вектор-стовпець b є вектор-стовпець.
При утворенні y2 враховуємо, що результатом множення двох матриць є матриця.
При утворенні Y3 враховуємо, результатом множення матриці на матрицю є матриці, та при її добутку на різницю матрицею буде також матриця.
Таким чином, згідно поставленої задачі, в обчисленні загального виразу приймають участь два різні елементи – вектор-стовпець та матриця.
Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана. Правила множення наведені в таблиці 1.
Таблиці 1
Результати добутків в матричних обчисленнях
результатом множення матриці на матрицю є матриця.
cij=
результатом множення матриці на вектор-стовпець є вектор-стовпець.
cj=
результатом множення вектора-рядка на вектор-стовпець є число
с=
результатом множення вектора-стовпця на вектор-рядок є матриця
сij=
результатом множення двох векторів-стовпців є число.
с=
результатом множення вектора-рядка на матрицю на є вектор-рядок.
сj=
Оскільки задано якого типу повинен бути результат розв’язання задачі можна здійснити перевірку правильності декомпозиції, тобто чи за нею можна розв’язати заданий вираз згідно варіанту. Оскільки вище наведено результати Y3, y1 та y2 перевірку почнемо з 3 стадії, тобто після отримання цих результатів.
Стадія 4:
Результатом піднесення матриці Y3 до квадрату, тобто множення матриці саму на себе, буде матриця.
Стадія 5:
Результатом піднесення квадратної матриці до кубічної, тобто множення матриці Y32 на матрицю Y3 буде матриця.
Результатом множення вектора- рядка y1’ на матрицю Y3 буде рядок.
Результатом множення вектора-рядка y2 на вектора-стовбець y1 буде просте число.
Стадія 6:
Результатом множення матриці (Y33) на вектора-стовбець (y1) буде вектора-стовбець.
Результатом множення вектора-рядка (y1’*Y3 ) вектора-стовбець (y1) буде просте число .
Результатом множення простого числа (y2*y1) на матрицю (Y3) буде матриця .
Стадія 7:
Результатом множення вектора-стовбеця (Y33*y1)на вектора-рядкядок(y1’)буде матриця .
Результатом множення числа(y1’*Y3* y1)на матрицю (Y3)буде матриця .
Стадія 8:
Результатом додавання матриці(Y33*y1* y1’)до матриці (y2*y1* Y3)буде матриця .
Стадія 9:
Сумою двох матриць, (Y33*y1* y1’+ y2*y1* Y3) та (y1’*Y3* y1* Y3)), буде матриця.
Як можемо побачити з перевірки в результаті буде отримано матрицю, що співпадає з заданим розв’язком задачі згідно варіанту.
4. Результати роботи
4.1. Результат роботи розробленої програми
В якості результатів роботи приводяться текстові файли процесорів, що містять дані якими оперує відповідний процесор. Для тестування було обрано автоматичну генерацію початкових даних з розміром матриць та векторів N = 4.
/
Рис.2. Запуск і виконання програми за допомогою mpich2 в командному рядку
Вміст файлу 0.txt
N = 4
Cij =
0 0 0 0
0 1 2 3
0 0.25 0.5 0.75
0 0.111111 0.222222 0.333333
bi =
0
9
18
27
c1 =
6 9 8 5
A2 =
9 2 4 1
8 3 9 3
8 7 8 6
8 9 4 1
B2 =
1 7 6 1
5 8 7 6
9 6 3 1
3 1 7 5
A1 =
9 2 8 4
3 7 3 4
7 3 4 8
3 2 6 6
A =
2 7 4 8
3 4 8 5
5 3 6 7
1 2 5 6
b1 =
5 5 6 1
X =
2.57164e+014 2.30867e+014 2.37498e+014 1.97954e+014
4.33977e+014 3.89573e+014 4.00774e+014 3.34064e+014
7.10288e+014 6.37615e+014 6.55972e+014 5.46814e+014
7.07094e+014 6.34769e+014 6.5304e+014 5.44386e+014
Вміст файлу 1.txt
N = 5.60519e-045
Cij =
0 0 0 0
0 1 2 3
0 0.25 0.5 0.75
0 0.111111 0.222222 0.333333
B2 =
1 7 6 1
5 8 7 6
9 6 3 1
3 1 7 5
В2+26С =
1 7 6 1
5 34 59 84
9 12.5 16 20.5
3 3.88889 12.7778 13.6667
y2 =
19968 16000 18048 14592
y1 =
351
315
324
270
y2 * y1 = 2.18362e+007
Y3 =
58 184.889 248.778 272.667
113 282.167 407.333 485.5
133 417.333 665.667 842
92 415.889 655.778 859.667
y1’*Y3* y1 = 5.70459e+008
y1’*Y3* y1* Y3 =
3.30866e+010 1.05472e+011 1.41918e+011 1.55545e+011
6.44619e+010 1.60965e+011 2.32367e+011 2.76958e+011
7.58711e+010 2.38072e+011 3.79736e+011 4.80327e+011
5.24823e+010 2.37248e+011 3.74095e+011 4.90405e+011
Вміст файлу 2.txt
N = 5.60519e-045
b1 =
5 5 6 1
c1 =
6 9 8 5
b1*C‘1 = 128
rez5 =
1152 256 1024 512
384 896 384 512
896 384 512 1024
384 256 768 768
y2 =
19968 16000 18048 14592
Ykyb =
1.44726e+008 5.03977e+008 7.83926e+008 9.96373e+008
2.44168e+008 8.50416e+008 1.32289e+009 1.68152e+009
3.99375e+008 1.3918e+009 2.16532e+009 2.75269e+009
3.97475e+008 1.38554e+009 2.15568e+009 2.74058e+009
rez8 =
7.32564e+011
1.23621e+012
2.02339e+012
2.01436e+012
Вміст файлу 3.txt
N = 5.60519e-045
bij =
0
9
18
27
A =
2 7 4 8
3 4 8 5
5 3 6 7
1 2 5 6
y1=A*bi =
351
315
324
270
Y3 =
58 184.889 248.778 272.667
113 282.167 407.333 485.5
133 417.333 665.667 842
92 415.889 655.778 859.667
Ykvadrat =
82429.2 280115 434152 549452
137280 472418 732576 928146
220870 770331 1.19836e+006 1.52321e+006
218639 765564 1.19257e+006 1.51819e+006
rez6 =
123885 401285 608367 753557
y1’*Y3* y1 = 5.70459e+008
Вміст файлу 4.txt
N = 5.60519e-045
A2 =
9 2 4 1
8 3 9 3
8 7 8 6
8 9 4 1
В2+26С =
1 7 6 1
5 34 59 84
9 12.5 16 20.5
3 3.88889 12.7778 13.6667
Y3 =
58 184.889 248.778 272.667
113 282.167 407.333 485.5
133 417.333 665.667 842
92 415.889 655.778 859.667
Ykvadrat =
82429.2 280115 434152 549452
137280 472418 732576 928146
220870 770331 1.19836e+006 1.52321e+006
218639 765564 1.19257e+006 1.51819e+006
Ykyb =
1.44726e+008 5.03977e+008 7.83926e+008 9.96373e+008
2.44168e+008 8.50416e+008 1.32289e+009 1.68152e+009
3.99375e+008 1.3918e+009 2.16532e+009 2.75269e+009
3.97475e+008 1.38554e+009 2.15568e+009 2.74058e+009
Вміст файлу 5.txt
N = 5.60519e-045
A1 =
9 2 8 4
3 7 3 4
7 3 4 8
3 2 6 6
rez2 = 128
b1*C‘1*A1 =
1152 256 1024 512
384 896 384 512
896 384 512 1024
384 256 768 768
b1*C‘1*A1 =
1152 256 1024 512
384 896 384 512
896 384 512 1024
384 256 768 768
Y3 =
58 184.889 248.778 272.667
113 282.167 407.333 485.5
133 417.333 665.667 842
92 415.889 655.778 859.667
y1 =
351
315
324
270
y1' * Y3 =
123885 401285 608367 753557
rez7 = 2.18362e+007
y2*y1* Y3 =
1.2665e+009 4.03726e+009 5.43235e+009 5.95399e+009
2.46749e+009 6.16144e+009 8.8946e+009 1.06015e+010
2.90421e+009 9.11296e+009 1.45356e+010 1.8386e+010
2.00893e+009 9.08142e+009 1.43197e+010 1.87718e+010
rez8 =
7.32564e+011
1.23621e+012
2.02339e+012
2.01436e+012
Y33*y1* y1’ =
2.5713e+014 2.30758e+014 2.37351e+014 1.97792e+014
4.3391e+014 3.89406e+014 4.00532e+014 3.33777e+014
7.10209e+014 6.37368e+014 6.55578e+014 5.46315e+014
7.07039e+014 6.34522e+014 6.52652e+014 5.43876e+014
Y33*y1* y1’+ y2*y1* Y3 =
2.57131e+014 2.30762e+014 2.37356e+014 1.97798e+014
4.33912e+014 3.89413e+014 4.00541e+014 3.33787e+014
7.10212e+014 6.37377e+014 6.55593e+014 5.46333e+014
7.07041e+014 6.34532e+014 6.52666e+014 5.43895e+014
5. Тексти програм
5.1. Текст програми PRO1 на мові С++
< Header.h>
#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);
//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);
//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();
void CPU_3();
void CPU_4();
void CPU_5();
< main.cpp>
#include "Header.h"
//main
int main(int argc,char *argv[])
{
//видалення файлів попередньої сесії, якщо такі існують
remove( "E:\\0.txt" );
remove( "E:\\1.txt" );
remove( "E:\\2.txt" );
remove( "E:\\3.txt" );
remove( "E:\\4.txt" );
remove( "E:\\5.txt" );
remove( "E:\\6.txt" );
remove( "E:\\7.txt" );
//початок основної програми
int procCnt=0,procNumb;
MPI_Init(&argc, &argv); /*START MPI */
MPI_Comm_size(MPI_COMM_WORLD, &procCnt);
MPI_Comm_rank(MPI_COMM_WORLD, &procNumb);
if(procNumb==0)
{
CPU_0();
}
if(procNumb==1)
{
CPU_1();
}
if(procNumb==2)
{
CPU_2();
}
if(procNumb==3)
{
CPU_3();
}
if(procNumb==4)
{
CPU_4();
}
if(procNumb==5)
{
CPU_5();
}
MPI_Finalize(); /* EXIT MPI */
}
<types.cpp>
#include "Header.h"
void matrix(float**&M,int size)
{
M=new float*[size];
for(int i=0;i<size;i++)
M[i] = new float[size];
}
void vector_Row(float**&V,int size)
{
V=new float*[1];
for(int i=0;i<1;i++)
V[i] = new float[size];
}
void vector_Column(float**&V,int size)
{
V=new float*[size];
for(int i=0;i<size;i++)
V[i] = new float[1];
}
void number(float**&Numb)
{
Numb=new float*[1];
for(int i=0;i<1;i++)
Numb[i] = new float[1];
}
<Operations.cpp>
#include "proto.h"
#include "Header.h"
float ** dobytok_2_matruc(int rozmir,float** matrix1, float** matrix2)
{
float tmp=0;
float** result;
matrix(result,rozmir);
for(int k=0;k<rozmir;k++)
{
for(int l =0;l<rozmir;l++)
{
for(int s=0;s<rozmir;s++)
tmp+=matrix1[k][s]*matrix2[s][l];
result[k][l] = tmp;
tmp=0;
}
}
return result;//повертає матрицю
}
float** dobytok_matrix_vectorStovpec(int rozmir,float** matrix, float** vector)
{
float** result;
vector_Column(result,rozmir);
for (int i = 0; i < rozmir; i++){
result[i][0]= 0;
for (int j = 0; j < rozmir; j++)
result[i][0]+= matrix[i][j]*vector[j][0];
}
return result; //повертає вектор-стовпець
}
float** dobytok_vectorRjadok_matrix(int rozmir,float** matrix, float** vector)
{
float** result;
vector_Row(result,rozmir);
for (int i = 0; i < rozmir; i++){
result[0][i]= 0;
for (int j = 0; j < rozmir; j++)
result[0][i]+= matrix[j][i]*vector[0][j];
}
return result; //повертає вектор-рядок
}
float** transp_vectorStovpcja(int rozmir,float** vector)
{
float** result;
vector_Row(result,rozmir);
for (int i = 0; i < rozmir; i++){
result[0][i] = vector[i][0];
}
return result; //повертає вектор-рядок
}
float** transp_vectorRjadka(int rozmir,float** vector)
{
float** result;
vector_Column(result,rozmir);
for (int i = 0; i < rozmir; i++){
result[i][0] = vector[0][i];
}
return result; //повертає вектор-стовпець
}
float dobytok_Rjadka_na_Stovbec(int rozmir,float** vectorS,float** vectorR)
{
float res=0.0;
for(int i=0;i<rozmir;i++)
res+=vectorR[0][i] * vectorS[i][0];
return res;//number
}
float** dobytok_Stovbec_na_Rjadok(int rozmir,float** vectorS,float** vectorR)
{
float** res;
matrix(res,rozmir);
for(int i=0;i<rozmir;i++)
for(int j=0;j<rozmir;j++)
res[i][j]=vectorS[i][0] * vectorR[0][j];
return res; //matrix
}}
<input.cpp>
#include "Header.h"
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;
number(NN);
NN[0][0] = N;
write_to_file(fio,NN,N,0,'N',"N");
//generate Cij
matrix(C,N);
cout<<endl<<"Matrix Cij = "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if((i==0)&&(j==0))
C[i][j]=0;
else
C[i][j] = (float)(j*j+i)/(float)(i*i+j);
cout<<C[i][j]<<"\t";
}
cout<<endl;
}
write_to_file(fio,C,N,0,'M',"Cij");
cout<<"Matrix Cij - generated successful!"<<endl;
//generate b (bi) -- вектор-стовпець
vector_Column(b,N);
cout<<"Vector Column bi = "<<endl;
for(int i = 0;i<N;i++)
{
cin>>b[i][0];
cout<<endl;
}
write_to_file(fio,b,N,0,'C',"bi");
//generate c1 -- вектор-рядок
vector_Row(c1,N);
cout<<"Vector Row c1 = "<<endl;
for(int j=0;j<N;j++)
{
cin>>c1[0][j];
cout<<"\t";
}
write_to_file(fio,c1,N,0,'R',"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++)
{
cin>>A2[i][j];
cout<<"\t";
}
cout<<endl;
}
write_to_file(fio,A2,N,0,'M',"A2");
//generate B2
matrix(B2,N);
cout<<"Matrix B2 = "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>B2[i][j];
cout<<"\t";
}
cout<<endl;
}
write_to_file(fio,B2,N,0,'M',"B2");
//generate A1
matrix(A1,N);
cout<<"Matrix A1 = "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>A1[i][j];
cout<<"\t";
}
cout<<endl;
}
write_to_file(fio,A1,N,0,'M',"A1");
//generate A
matrix(A,N);
cout<<"Matrix A = "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>A[i][j];
cout<<"\t";
}
cout<<endl;
}
write_to_file(fio,A,N,0,'M',"A");
//generate b1 -- вектор-рядок
vector_Row(b1,N);
cout<<"Vector Row b1 = "<<endl;
for(int j = 0;j<N;j++)
{
cin>>b1[0][j];
cout<<"\t";
}
write_to_file(fio,b1,N,0,'R',"b1");
cout<<endl<<"Thanks that all. Please wait for complete."<<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;
number(NN);
NN[0][0] = N;
write_to_file(fio,NN,N,0,'N',"N");
//generate Cij
matrix(C,N);
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if((i==0)&&(j==0)) C[i][j]=0;
else C[i][j] = (float)(j+i)/(float)(i*i+j);
}
}
write_to_file(fio,C,N,0,'M',"Cij");
//generate b (bij) -- вектор-стовпець
vector_Column(b,N);
for(int i = 0;i<N;i++)
{
b[i][0] = 4*pow((float)i+1,(int)-3);
}
write_to_file(fio,b,N,0,'C',"bi");
//generate c1 -- вектор-рядок
vector_Row(c1,N);
for(int j=0;j<N;j++)
{
c1[0][j] = rand()%9+1;
}
write_to_file(fio,c1,N,0,'R',"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
06.01.2014 03:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора