Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
паралельне представлення алгоритмів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра електронні обчислювальні машини
Інформація про роботу
Рік:
2005
Тип роботи:
Лабораторна робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська Політехніка”
Кафедра “Електронні обчислювальні машини”
ЛАБОРАТОРНА РОБОТА №2.
з курсу: “Паралельне та розподільне числення”
на тему:
“паралельне представлення алгоритмів”
Львів 2005
Мета: вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення.
Завдання: запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу
,
де А та В матриці з елементами та , відповідно(), тобто:
().
Тип вхідних послідовностей:
Варіант №
Тип матриці А
Тип матриці В
15
100…001
110…011
…………
110…011
100…001
Текст програми з одноразовим присвоюванням:
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <iomanip.h>
int **allocate(int ,int **);
int ***allocate_cub(int ,int ***);
int output(int, int **, char *);
int output_cub(int, int ***, char *, int);
int main( void)
{
int i, j, k, size;
int **A, **B, ***C;
cout<<"please, input size: "<<endl;
cin>>size;
if (size%2==0)
{
cout<<"For odd matrix only"<<endl;
return 0;
}
if (size<3)
{
cout<<"The matrix is too small"<<endl;
return 0;
}
A=allocate(size, A);
B=allocate(size, B);
C=allocate_cub(size+1, C);
//matrix A
for ( i=0; i<size; i++)
for ( j=0; j<size; j++)
{
if(i==j) A[i][j]=1;
if( (i>j) && (i<(size-j))) A[i][j]=1;
if( (j>(size/2)) && (j>i) && ((i+j)>(size-2)) ) A[i][j]=1;
}
//matrix B
for(i=(size/2); i<size; i++)
for (j=0; j<size; j++)
B[i][j]=1+rand()%10;
for(i=0;i<size;i++)
for(j=0;j<size;j++)
for(k=0;k<size;k++)
//if(k<size-1)
C[k+1][i][j]=C[k][i][j]+A[i][k]*B[k][j];
output(size, A, "A");
output(size, B, "B");
output_cub(size, C, "C", size);
free(A);
free(B);
free(C);
return 0;
}
int output(int n,int **m,char *name)
{
int i,j;
cout<<"~~~~~~~~~~ "<<name<<" ~~~~~~~~~~"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<m[i][j];
cout<<endl<<endl;
}
cout<<endl;
return 0;
}
int output_cub(int n, int ***m, char *name, int level)
{
int i,j;
cout<<"~~~~~~~~~~ "<<name<<" ~~~~~~~~~~"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<m[level][i][j];
cout<<endl<<endl;
}
cout<<endl;
return 0;
}
int ** allocate(int n, int **m)
{
int i;
m = (int**)calloc(n,sizeof(int*));
for(i=0;i<n;i++)
m[i] = (int*)calloc(n,sizeof(int));
return m;
}
int ***allocate_cub(int n,int ***m)
{
int i,j;
m = (int***)calloc(n,sizeof(int**));
for(i=0;i<n;i++) m[i] = (int**)calloc(n,sizeof(int*));
for(i=0;i<n;i++)
for(j=0;j<n;j++) m[i][j] = (int*)calloc(n,sizeof(int));
return m;
}
Рекурсивні рівняння:
,
де= A[r][i][j],
= B[r][i][j],
r – індекс рекурсії.
Локалізований граф залежностей:
Оптимізований граф залежностей:
При використанні неоптимізованого локального рекурсивного алгоритму кількість арифметичних операцій приблизно у два рази більша, ніж при роботі алгоритму, де усунуто зайві обчислення(враховуючи тип вхідних даних).
Текст програми, що реалізовує оптимізований локально-рекурсивний алгоритм:
//marichka
//parallel
//lab2
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <iomanip.h>
int ***allocate_cub(int ,int ***);
int output(int, int **, char *);
int output_cub(int, int ***, char *, int);
int main( void)
{
int i, j, k, size, op1=0, op2=0;
int ***A, ***B, ***C;
cout<<"please, input size: "<<endl;
cin>>size;
if (size%2==0)
{
cout<<"For odd matrix only"<<endl;
return 0;
}
if (size<3)
{
cout<<"The matrix is too small"<<endl;
return 0;
}
C=allocate_cub(size+1, C);
A=allocate_cub(size, A);
B=allocate_cub(size, B);
/* //matrix A
for ( i=0; i<size; i++)
for ( j=0; j<size; j++)
{
if(i==j) A[i][j]=1;
if( (i>j) && (i<(size-j))) A[i][j]=1;
if( (j>(size/2)) && (j>i) && ((i+j)>(size-2)) ) A[i][j]=1;
}
//matrix B
for(i=(size/2); i<size; i++)
for (j=0; j<size; j++)
B[i][j]=1+rand()%10;
*/ //matrix A_cub
for ( i=0; i<size; i++)
for ( k=0; k<size; k++)
{
if(i==k) A[k][i][0]=1;
if( (i>k) && (i<(size-k))) A[k][i][0]=1;
if( (k>(size/2)) && (k>i) && ((i+k)>(size-2)) ) A[k][i][0]=1;
}
//matrix B
for(k=(size/2); k<size; k++)
for (j=0; j<size; j++)
B[k][0][j]=1+rand()%10;
for(k=0;k<size;k++)
for(i=0;i<size;i++)
for(j=0;j<size;j++)
{
if(j<size-1)
A[k][i][j+1]=A[k][i][j];
if(i<size-1)
B[k][i+1][j]=B[k][i][j];
op1++;
if(B[k][i][j]!=0)
{
C[k+1][i][j]=C[k][i][j] + A[k][i][j]*B[k][i][j];
op2++;
}
else
C[k+1][i][j]=C[k][i][j];
}
cout<<"~~~~~~~~~~ A ~~~~~~~~~~"<<endl;
for(k=0;k<size;k++)
{
for(i=0;i<size;i++)
cout<<setw(4)<<A[i][k][k];
cout<<endl<<endl;
}
cout<<endl;
cout<<"~~~~~~~~~~ B ~~~~~~~~~~"<<endl;
for(k=0;k<size;k++)
{
for(j=0;j<size;j++)
cout<<setw(4)<<B[k][k][j];
cout<<endl<<endl;
}
cout<<endl;
output_cub(size, C, "C", size);
cout<<"OPERATIONS"<<endl;
cout<<"\toptimized "<<op2<<endl<<"\tnonoptimized "<<op1<<endl;
free(A);
free(B);
free(C);
return 0;
}
int output(int n,int **m,char *name)
{
int i,j;
cout<<"~~~~~~~~~~ "<<name<<" ~~~~~~~~~~"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<m[i][j];
cout<<endl<<endl;
}
cout<<endl;
return 0;
}
int output_cub(int n, int ***m, char *name, int level)
{
int i,j;
cout<<"~~~~~~~~~~ "<<name<<" ~~~~~~~~~~"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<setw(4)<<m[level][i][j];
cout<<endl<<endl;
}
cout<<endl;
return 0;
}
int ** allocate(int n, int **m)
{
int i;
m = (int**)calloc(n,sizeof(int*));
for(i=0;i<n;i++)
m[i] = (int*)calloc(n,sizeof(int));
return m;
}
int ***allocate_cub(int n,int ***m)
{
int i,j;
m = (int***)calloc(n,sizeof(int**));
for(i=0;i<n;i++) m[i] = (int**)calloc(n,sizeof(int*));
for(i=0;i<n;i++)
for(j=0;j<n;j++) m[i][j] = (int*)calloc(n,sizeof(int));
return m;
}
Результат виконання програми:
please, input size:
5
~~~~~~~~~~ A ~~~~~~~~~~
1 0 0 0 1
1 1 0 1 1
1 1 1 1 1
1 1 0 1 1
1 0 0 0 1
~~~~~~~~~~ B ~~~~~~~~~~
0 0 0 0 0
0 0 0 0 0
2 8 5 1 10
5 9 9 3 5
6 6 2 8 2
~~~~~~~~~~ C ~~~~~~~~~~
6 6 2 8 2
11 15 11 11 7
13 23 16 12 17
11 15 11 11 7
6 6 2 8 2
OPERATIONS
optimized 75
nonoptimized 125
Висновок:
На даній лабораторній роботі я застосувала паралельне представлення алгоритму для прискорення обчислень, використавши метод паралельного представлення. Цей метод передбачає написання рекурсивних рівнянь, побудову локалізованого та нелокалізованого графів залежностей. Виконавши оптимізацію алгоритму, я досягла збільшення його продуктивності у два рази.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора