Паралельне представлення алгоритмів.. Лабораторна робота з Паралельні та розподілені обчислення . Робота № 200808

Паралельне представлення алгоритмів.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Електронні обчислювальні машини

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Паралельні та розподілені обчислення

Група:

КІЗ

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Національний університет “Львівська Політехніка” Кафедра “Електронні обчислювальні машини” Лабораторна робота №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 Висновок: завдяки цій лабораторній роботі я зрозумів, яким чином можна представити алгоритм паралельно. Я застосував паралельне представлення. Цей метод передбачає написання рекурсивних рівнянь, побудову локалізованого та нелокалізованого графів залежностей. Виконавши оптимізацію алгоритму, я збільшив його продуктивніть більш, ніж у два рази.

Лабораторна робота Паралельні та розподілені обчислення

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись