Національний університет “Львівська Політехніка”
Кафедра “Електронні обчислювальні машини”
Лабораторна робота №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[...
