Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра ЕОМ Звіт про виконання лабораторної роботи №2 з курсу: «Паралельні та розподілені обчислення», на тему: «Паралельне представлення алгоритмів» Львів 2005 рік Мета: вивчити можливості паралельного представлення алгоритму. Набути навиків такого представлення. Текст програмної реалізації #include <conio.h> #include <iostream.h> #include <stdlib.h> #include <time.h> #include <iomanip.h> #include <fstream.h> #include <windows.h> ofstream f("rezult.txt"); int nAr = 0; int nAr1 = 0; double** InputMatrix(int n) { double **temp; temp = new double*[n]; int i=0,j=0; for (i=0;i<n;i++) { temp[i] = new double[n]; } for (i=0;i<n;i++) { for (j=0;j<n;j++) { temp[i][j] = (rand()%9)+1; } } return temp; } double** InputMatrixA(int n) { double **temp; temp = new double*[n]; int i=0,j=0; for (i=0;i<n;i++) { temp[i] = new double[n]; } for (i=0;i<n;i++) { for (j=0;j<n;j++) { if (j>i) temp[i][j] = 0; else temp[i][j] = n-(i-j); } } return temp; } double** InputMatrixB(int n,bool avto = true) { double **temp; int count=n-2; temp = new double*[n]; int i=0,j=0; for (i=0;i<n;i++) { temp[i] = new double[n]; } if (avto) { for (i=0;i<n;i++) { for (j=0;j<n;j++) { if ((j>=i) && (j>count)) temp[i][j] = (rand()%9)+1; else temp[i][j] = 0; } count--; } } else { for (i=0;i<n;i++) { for (j=0;j<n;j++) { if ((j>=i) && (j>count)) { cout<<"B["<<i<<"]["<<j<<"] = "; cin>>temp[i][j]; } else temp[i][j] = 0; } count--; } } return temp; } void PrintMatrix(double** mas,int n,char *str = NULL) { if (str) { cout<<str<<endl; f<<str<<endl; } for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { cout<<setw(4)<<mas[i][j]; f<<setw(4)<<mas[i][j]; } cout<<endl; f<<endl; } cout<<endl; f<<endl; } void PrintMatrix(double*** mas,int n,char *str = NULL) { if (str) { cout<<str<<endl; f<<str<<endl; } int i,j,k; //A k=0; for (i=0;i<n;i++) { for (j=0;j<n;j++) { cout<<setw(4)<<mas[i][j][k]; f<<setw(4)<<mas[i][j][k]; } cout<<endl; f<<endl; } cout<<endl; f<<endl; //B i=0; for (j=0;j<n;j++) { for (k=0;k<n;k++) { cout<<setw(4)<<mas[i][j][k]; f<<setw(4)<<mas[i][j][k]; } cout<<endl; f<<endl; } cout<<endl; f<<endl; //C j=n-1; for (i=0;i<n;i++) { for (k=0;k<n;k++) { cout<<setw(4)<<mas[i][j][k]; f<<setw(4)<<mas[i][j][k]; } cout<<endl; f<<endl; } cout<<endl; f<<endl; } double*** To3DMatrixA(double **mas,int n) { int i=0,j=0,k=0; double ***temp = NULL; temp = new double**[n]; for (i=0;i<n;i++) { temp[i] = new double*[n]; for (int j=0;j<n;j++) { temp[i][j] = new double[n]; } } for (k=0;k<n;k++) { for (i=0;i<n;i++) { for (j=0;j<n;j++) { temp[i][j][k] = mas[i][j]; } } } return temp; } double*** To3DMatrixB(double **mas,int n) { int i=0,j=0,k=0; int l=0,m=0; double ***temp = NULL; temp = new double**[n]; for (i=0;i<n;i++) { temp[i] = new double*[n]; for (int j=0;j<n;j++) { temp[i][j] = new double[n]; } } for (i=0;i<n;i++) { for (j=0;j<n;j++) { for (k=0;k<n;k++) { temp[i][j][k] = mas[j][k]; } } } return temp; } double*** MulMatrix(double ***M1,double ***M2,int n) { int i,j,k,l=0; int count=(n-1)/2; double ***temp = NULL; temp = new double**[n]; for (i=0;i<n;i++) { temp[i] = new double*[n]; for (j=0;j<n;j++) { temp[i][j] = new double[n]; } } for (k=0;k<n;k++) { for (i=0;i<n;i++) { for (j=0;j<n;j++) temp[i][j][k] = 0; } } for (k=n/2;k<n;k++) { for (i=0;i<n;i++) { if (i>=count) { j=0; temp[i][j][k] = M1[i][j][k] * M2[i][j][k]; nAr++; for (j=1;j<n;j++) { temp[i][j][k] = M1[i][j][k] * M2[i][j][k] + temp[i][j-1][k]; nAr++; } } } count--; } //for (k=0;k<n;k++) for (k=0;k<n;k++) { for (i=0;i<n;i++) { //temp[i][j][k] = M1[i][j][k] * M2[i][j][k]; for (j=0;j<n;j++) { nAr1++; } } } return temp; } double** FormRez(double ***M,int n) { int i,j,k; double** temp = NULL; temp = new double*[n]; for (i=0;i<n;i++) { temp[i] = new double[n]; } j=n-1; for (i=0;i<n;i++) { for (k=0;k<n;k++) { temp[i][k] = M[i][j][k]; } } return temp; } void FreeMem(double **M,int n) { int i; for (i=0;i<n;i++) { delete [] M[i]; } delete [] M; } void FreeMem(double ***M,int n) { int i,j; for (i=0;i<n;i++) { for (j=0;j<n;j++) { delete [] M[i][j]; } delete [] M[i]; } delete [] M; } void UkrMes(char * str) { char temp[80]; CharToOem(str,temp); cout<<temp; f<<temp; } void main() { int n = 3; double **A,**B,**C,***A1,***B1,***C1; srand(time(NULL)); UkrMes("Ââåäiòü êiëüêiñòü åëåìåíòiâ â ìàòðèöi : "); cin>>n; //if (n%2 != 1) // n++; A = InputMatrixA(n); PrintMatrix(A,n,"A = \n"); UkrMes("Âèáåðiòü ñïîñiá ãåíåðóâàííÿ åëåìåíòiâ :\n"); UkrMes("1 - Àâòîìàòè÷íî\n"); UkrMes("2 - Ââiä ç êëàâiàòóðè\n"); int choice = 1; cin>>choice; if (choice-1) { B = InputMatrixB(n,false); } else B = InputMatrixB(n); PrintMatrix(B,n,"B = \n"); A1 = To3DMatrixA(A,n); PrintMatrix(A1,n,"A(3d) = \n"); B1 = To3DMatrixB(B,n); PrintMatrix(B1,n,"B(3d) = \n"); C1 = MulMatrix(A1,B1,n); PrintMatrix(C1,n,"C(3d) = \n"); C = FormRez(C1,n); PrintMatrix(C,n,"C = \n"); UkrMes("Êiëüêiñòü îïåðaöié â îïòèìiçîâàíîìó âàðiàíòi : "); cout<<nAr<<endl; f<<nAr<<endl; UkrMes("Êiëüêiñòü îïåðaöié â íåîïòèìiçîâàíîìó âàðiàíòi : "); cout<<nAr1<<endl; f<<nAr1<<endl; FreeMem(A,n); FreeMem(B,n); FreeMem(C,n); FreeMem(A1,n); FreeMem(B1,n); FreeMem(C1,n); getch(); } Граф залежностей
 Приклад виконання програми Ââåäiòü êiëüêiñòü åëåìåíòiâ â ìàòðèöi : A = 5 0 0 0 0 4 5 0 0 0 3 4 5 0 0 2 3 4 5 0 1 2 3 4 5 Âèáåðiòü ñïîñiá ãåíåðóâàííÿ åëåìåíòiâ : 1 - Àâòîìàòè÷íî 2 - Ââiä ç êëàâiàòóðè B = 0 0 0 0 5 0 0 0 1 1 0 0 5 1 7 0 0 0 2 7 0 0 0 0 3 A(3d) = 5 0 0 0 0 4 5 0 0 0 3 4 5 0 0 2 3 4 5 0 1 2 3 4 5 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 B(3d) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 1 1 0 0 5 1 7 0 0 0 2 7 0 0 0 0 3 0 0 0 0 3 0 0 0 0 3 0 0 0 0 3 0 0 0 0 3 0 0 0 0 3 C(3d) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 0 0 0 0 25 0 0 0 0 25 0 0 0 0 25 0 0 0 0 25 0 0 0 0 25 0 0 0 5 25 0 0 25 9 54 0 0 20 17 76 0 0 15 13 71 C = 0 0 0 0 25 0 0 0 5 25 0 0 25 9 54 0 0 20 17 76 0 0 15 13 71 Êiëüêiñòü îïåðaöié â îïòèìiçîâàíîìó âàðiàíòi : 60 Êiëüêiñòü îïåðaöié â íåîïòèìiçîâàíîìó âàðiàíòi : 125