Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне представлення алгоритмів.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2005
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Група:
КІЗ
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська Політехніка”
Кафедра “Електронні обчислювальні машини”
Лабораторна робота №2.
з курсу: “Паралельне та розподільне числення”
на тему:
паралельне представлення алгоритмів
Виконав:
студент групи КІ3
Львів 2005
Мета: вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення.
Завдання: запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу
EMBED Equation.3 ,
де А та В матриці з елементами EMBED Equation.3 та EMBED Equation.3 , відповідно( EMBED Equation.3 ), тобто:
EMBED Equation.3 ( EMBED Equation.3 ).
Тип вхідних послідовностей:
Текст програми з одноразовим присвоюванням: (lab#2a.c)
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <stdlib.h>
int ***matrixr(int ,int ***);
int **matrix(int ,int **);
int outpmr(int ,int ***,char *,int);
int outpm(int ,int **,char *);
int main(void)
{
int i,j,n,k,r=0;
int **A, **B, ***C;
clrscr();
printf("please, input n: ");
scanf("%d",&n);
if(n<3) return 1;
if(n%2==0)
{
n+=1;
printf("dimension is: %d=%d+%d\n\n",n,n-1,1);
}
else printf("dimension is: %d\n\n",n);
A=matrix(n,A);
B=matrix(n,B);
C=matrixr(n,C);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j) A[i][j]=1;
if(i<j) A[i][j]=j-i+1;
if(i>j) A[i][j]=i-j+1;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++) if(i<=j && i<=n/2 && j<n-i) B[i][j]=1+rand()%10;
outpm(n,A,"A");
outpm(n,B,"B");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(r=0;r<n;r++) if(r<n-1) C[r+1][i][j]=C[r][i][j]+A[i][r]*B[r][j];
outpmr(n,C,"C",n-1);
getch();
free(A);
free(B);
free(C);
return 0;
}
int **matrix(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 ***matrixr(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;
}
int outpm(int n,int **X,char *name)
{
int i,j;
printf(" ===========[%s]========\n",name);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) printf(" %-2d ",X[i][j]);
printf("\n\n");
}
printf("\n");
return 0;
}
int outpmr(int n,int ***m,char *name,int level)
{
int i,j;
printf(" ===========[%s]========\n",name);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) printf(" %-2d ",m[level][i][j]);
printf("\n\n");
}
printf("\n");
return 0;
}
Рекурсивні рівняння:
EMBED Equation.3 ,
де EMBED Equation.3 = A[r][i][j],
EMBED Equation.3 = B[r][i][j],
r – індекс рекурсії.
Локалізований граф залежностей:
EMBED Visio.Drawing.6
Оптимізований граф залежностей:
EMBED Visio.Drawing.6
При використанні неоптимізованого локального рекурсивного алгоритму кількість арифметичних операцій приблизно у два рази більша, ніж при роботі алгоритму, де усунуто зайві обчислення(враховуючи тип вхідних даних). Приріст продуктивності зростає при збільшенні кількості вхідних даних. Так, для розмірності n=5 продуктивність зростає приблизно в 2 рази, а для n=9 – майже в 3 рази.
Текст програми, що реалізовує оптимізований локально-рекурсивний алгоритм:
(lab#2opt.c)
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <stdlib.h>
int ***matrixr(int ,int ***);
int outpmr(int ,int ***,char *,int);
void main( void)
{
int i,j,n,r,op1=0,op2=0;
int ***A, ***B, ***C;
clrscr();
printf("please, input n: ");
scanf("%d",&n);
if(n%2==0)
{
n+=1;
printf("dimension is: %d=%d+%d\n\n",n,n-1,1);
}
else printf("dimension is: %d\n\n",n);
A=matrixr(n,A);
B=matrixr(n,B);
C=matrixr(n,C);
for(r=0;r<n;r++)
for(i=0;i<n;i++)
{
if(r==i) A[r][i][0]=1;
if(r<i) A[r][i][0]=i-r+1;
if(r>i) A[r][i][0]=r-i+1;
}
for(r=0;r<n;r++)
for(j=0;j<n;j++) if(r<=j && r<=n/2 && j<n-r) B[r][0][j]=1+rand()%10;
for(r=0;r<n;r++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(j<n-1) A[r][i][j+1]=A[r][i][j];
if(i<n-1) B[r][i+1][j]=B[r][i][j];
if(r<n-1)
{
op1++;
if(B[r][i][j]!=0)
{
C[r+1][i][j]=C[r][i][j] + A[r][i][j]*B[r][i][j];
op2++;
}
else C[r+1][i][j]=C[r][i][j];
}
}
printf(" ===========[A]========\n");
for(r=0;r<n;r++)
{
for(i=0;i<n;i++) printf(" %-2d ",A[r][i][r]);
printf("\n\n");
}
printf("\n");
printf(" ===========[B]========\n");
for(r=0;r<n;r++)
{
for(j=0;j<n;j++) printf(" %-2d ",B[r][r][j]);
printf("\n\n");
}
printf("\n");
outpmr(n,C,"C result",n-1);
printf("operations: %d (%d)\nperformance increase: %d",op2,op1,op1/op2);
getch();
free(A);
free(B);
free(C);
}
int outpmr(int n,int ***m,char *name,int pos)
{
int i,j;
printf(" ===========[%s]========\n",name);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) printf(" %-2d ",m[pos][i][j]);
printf("\n\n");
}
printf("\n");
return 0;
}
int ***matrixr(int n,int ***m)
{
int r,i;
m = (int***)calloc(n,sizeof(int**));
for(r=0;r<n;r++) m[r] = (int**)calloc(n,sizeof(int*));
for(r=0;r<n;r++)
for(i=0;i<n;i++) m[r][i] = (int*)calloc(n,sizeof(int));
return m;
}
Результат виконання програми:
please, input n: 5
dimension is: 5
===========[A]========
1 2 3 4 5
2 1 2 3 4
3 2 1 2 3
4 3 2 1 2
5 4 3 2 1
===========[B]========
7 1 3 1 7
0 8 6 6 0
0 0 9 0 0
0 0 0 0 0
0 0 0 0 0
===========[C result]========
7 17 42 13 7
14 10 30 8 14
21 19 30 15 21
28 28 48 22 28
35 37 66 29 35
operations: 45 (100)
performance increase: 2
Висновок: завдяки цій лабораторній роботі я зрозумів, яким чином можна представити алгоритм паралельно. Я застосував паралельне представлення. Цей метод передбачає написання рекурсивних рівнянь, побудову локалізованого та нелокалізованого графів залежностей. Виконавши оптимізацію алгоритму, я збільшив його продуктивніть більш, ніж у два рази.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора