Скачать 475.48 Kb.
|
Рис. 1.4. Списки смежности1.2.8 Листинг текста программы построения параллельной формы алгоритма решения задачи перемножения матриц ml-mpo-lab2.c /* Program for building of parallel form of algorithm * for task solution of multiplication of two rectangular matrixes * Построение параллельной формы алгоритма решения задачи перемножения двух прямоугольных матриц * Copyright (C) 2005 Eugene Dokukin aka MustLive. http://mlbpg.narod.ru * Open Source Software, GPL. http://www.gnu.org */ #include #include // matrix demensions: A 7x8 and B 8x5 #define SIZE_Ia 7 // max rows for matrix A #define SIZE_Ja 8 // max columns for matrix A #define SIZE_Ib 8 // max rows for matrix B #define SIZE_Jb 5 // max columns for matrix B #define CPU 8 // number of CPUs #define AlgHeight 100 // potential height of algorithm int A_I, A_J; // number of rows and columns for matrix A int B_I, B_J; // number of rows and columns for matrix B int NULL_Ia[SIZE_Ia]; // nulls in rows of A int NULL_Ja[SIZE_Ja]; // nulls in columns of A int NULL_Ib[SIZE_Ib]; // nulls in rows of B int NULL_Jb[SIZE_Jb]; // nulls in columns of B char MatrixA[SIZE_Ia][SIZE_Ja]; // matrix A char MatrixB[SIZE_Ib][SIZE_Jb]; // matrix B int height; // height of algorithm int operations; // number of operation int VarName; // name of variable struct CharArray { char str[64]; // array of char } MatrixC[SIZE_Ia][SIZE_Jb]; // matrix C struct CharArray Parallel[AlgHeight][CPU]; // matrix Parallel with size AlgHeightxCPU void Error () { // enter correct parameters printf ("\nProgram for building of parallel form of algorithm\n"); printf ("for task solution of multiplication of two rectangular matrixes\n"); printf ("Copyright (C) 2005 MustLive. http://mlbpg.narod.ru\n"); printf ("Open Source Software, GPL. http://www.gnu.org\n\n"); } void NullMatrix () { // null all elements of all matrixes int i,j; // counters for (i=0;i for (j=0;j MatrixA[i][j] = '0'; } } for (i=0;i for (j=0;j MatrixB[i][j] = '0'; } } for (i=0;i for (j=0;j MatrixC[i][j].str[0] = '0'; } } for (i=0;i for (j=0;j Parallel[i][j].str[0] = '0'; } } } void ReadMatrixes (char filename[255]) { // open file and read two matrixes FILE *fp; // pointer on file int i,j; // counters VarName = 0; if ( (fp = fopen(filename, "r")) == NULL) { Error(); fprintf(stderr, "Error opening file %s.\n",filename); exit(0); } else { for (i=0;i for (j=0;j fscanf (fp, "%c ",&MatrixA[i][j]); if ( feof(fp) ) break; NULL_Ia[i] = NULL_Ia[i] + ((int)MatrixA[i][j]-48); NULL_Ja[j] = NULL_Ja[j] + ((int)MatrixA[i][j]-48); } fscanf (fp, "%c\n",&MatrixA[i][j]); NULL_Ia[i] = NULL_Ia[i] + ((int)MatrixA[i][j]-48); NULL_Ja[j] = NULL_Ja[j] + ((int)MatrixA[i][j]-48); if ( feof(fp) ) break; } fscanf (fp,"\n"); for (i=0;i for (j=0;j fscanf (fp, "%c ",&MatrixB[i][j]); if (VarName == 0 && MatrixB[i][j] != '0') { VarName = (int)MatrixB[i][j]+1; } if ( feof(fp) ) break; NULL_Ib[i] = NULL_Ib[i] + ((int)MatrixB[i][j]-48); NULL_Jb[j] = NULL_Jb[j] + ((int)MatrixB[i][j]-48); } fscanf (fp, "%c\n",&MatrixB[i][j]); NULL_Ib[i] = NULL_Ib[i] + ((int)MatrixB[i][j]-48); NULL_Jb[j] = NULL_Jb[j] + ((int)MatrixB[i][j]-48); if ( feof(fp) ) break; } } fclose(fp); } void ReorganizeInputMatrixes () { // algebraic manipulation of input matrixes while (NULL_Ia[A_I-1] == 0) { // if last row of matrix А is null A_I--; } while (NULL_Jb[B_J-1] == 0) { // if last column of matrix B is null B_J--; } // if last column of matrix A and last row of matrix B is null while ((NULL_Ja[A_J-1] == 0) && (NULL_Ib[B_I-1] == 0)) { A_J--; B_I--; } } void MultiplyInputMatrixes () { // multiplication of two rectangular matrixes int i,j,k,pos; // counters char string[2]; // temp string for (i=0;i for (j=0;j pos = 0; for (k=0;k if (MatrixA[i][k] != '0' && MatrixB[k][j] != '0') { if (pos == 0) { strcpy(MatrixC[i][j].str, ""); } else { sprintf(string,"+"); strncat(MatrixC[i][j].str, string, 1); } sprintf(string,"%c",MatrixA[i][k]); strncat(MatrixC[i][j].str, string, 1); sprintf(string,"%d%d",i+1,k+1); strncat(MatrixC[i][j].str, string, 2); sprintf(string,"*%c",MatrixB[k][j]); strncat(MatrixC[i][j].str, string, 2); sprintf(string,"%d%d",k+1,j+1); strncat(MatrixC[i][j].str, string, 2); pos++; } } } } } void BuildParallelAlgorithm () { // building of parallel form of algorithm int i,j,k,pos,cpus,l,m; // counters int save, TempVar, TempCpu; // temp vars for summation of matrix's elements char string[2]; // temp string height = 0; operations = 0; cpus = 0; for (i=0;i for (j=0;j pos = 0; for (k=0;k if (MatrixA[i][k] != '0' && MatrixB[k][j] != '0') { if (height > AlgHeight) { break; } while (Parallel[height][cpus].str[0] != '0') { cpus++; } if (pos > 0) { save = 0; l = height + 1; while (save == 0) { for (m=0;m<8;m++) { if (Parallel[l][m].str[0] == '0' && save == 0){ strcpy(Parallel[l][m].str, ""); sprintf(string,"%c%d",TempVar,TempCpu); strncat(Parallel[l][m].str, string, 2); sprintf(string,"+%c",VarName); strncat(Parallel[l][m].str, string, 2); sprintf(string,"%d=",cpus+1); strncat(Parallel[l][m].str, string, 2); sprintf(string,"%c%d",VarName+1,m+1); strncat(Parallel[l][m].str, string, 2); save = 1; operations++; } } l++; } } strcpy(Parallel[height][cpus].str, ""); sprintf(string,"%c",MatrixA[i][k]); strncat(Parallel[height][cpus].str, string, 1); sprintf(string,"%d%d",i+1,k+1); strncat(Parallel[height][cpus].str, string, 2); sprintf(string,"*%c",MatrixB[k][j]); strncat(Parallel[height][cpus].str, string, 2); sprintf(string,"%d%d",k+1,j+1); strncat(Parallel[height][cpus].str, string, 2); sprintf(string,"="); strncat(Parallel[height][cpus].str, string, 1); sprintf(string,"%c%d",VarName,cpus+1); strncat(Parallel[height][cpus].str, string, 2); TempVar = VarName; TempCpu = cpus+1; pos++; cpus++; operations++; if (cpus == CPU) { cpus = 0; height++; VarName++; } } } } } } void DisplayInputMatrixes () { // display input matrixes int i,j; // counters printf ("\nMatrix A\n\n"); for (i=0;i for (j=0;j if (MatrixA[i][j] != '0') { printf("%c%d%d\t",MatrixA[i][j],i+1,j+1); } else { printf("%c\t",MatrixA[i][j]); } } printf("\n"); } printf ("\nMatrix B\n\n"); for (i=0;i for (j=0;j if (MatrixB[i][j] != '0') { printf("%c%d%d\t",MatrixB[i][j],i+1,j+1); } else { printf("%c\t",MatrixB[i][j]); } } printf("\n"); } } void DisplayResultMatrix () { // display resulting matrix int i,j; // counters printf ("\n\nResulting matrix C = A x B\n"); printf ("\nMatrix C\n\n"); for (i=0;i for (j=0;j printf("%s\t",MatrixC[i][j].str); } printf("\n"); } } void DisplayResultParallelMatrix () { // display resulting matrix of parallel algorithm int i,j; // counters printf ("\n\nResulting matrix of parallel algorithm:\n\n"); for (i=0;i<=height;i++) { for (j=0;j if (Parallel[i][j].str[0] != '0') { printf("%s\t",Parallel[i][j].str); } } printf("\n"); } } // open file and write resulting matrix of parallel algorithm void WriteResultParallelMatrix (char filename[255]) { FILE *fp; // pointer on file int i,j; // counters if ( (fp = fopen(filename, "w")) == NULL) { Error(); fprintf(stderr, "Error saving file %s.\n",filename); exit(0); } else { for (i=0;i<=height;i++) { for (j=0;j if (Parallel[i][j].str[0] != '0') { fprintf(fp,"%s\t",Parallel[i][j].str); } } fprintf(fp,"\n"); } } fclose(fp); } int main (int argc, char *argv[]) { float accel; // acceleration of algorithm if (argv[1] == NULL){ // input filename Error(); printf ("%s filename\n",argv[0]); exit(0); } NULL_Ia[SIZE_Ia] = 0; NULL_Ja[SIZE_Ja] = 0; NULL_Ib[SIZE_Ib] = 0; NULL_Jb[SIZE_Jb] = 0; A_I = SIZE_Ia; A_J = SIZE_Ja; B_I = SIZE_Ib; B_J = SIZE_Jb; if (A_J != B_I) { Error(); fprintf(stderr, "Error: can't multiply input matrixes.\n"); fprintf(stderr, "Number of columns of A not equal number of rows of B.\n"); exit(0); } NullMatrix(); ReadMatrixes (argv[1]); if (argv[2] == NULL) { printf ("\nInput Matrixes:\n"); DisplayInputMatrixes(); } ReorganizeInputMatrixes(); if (argv[2] == NULL) { printf ("\n\nReorganized Matrixes:\n"); DisplayInputMatrixes(); } MultiplyInputMatrixes(); if (argv[2] == NULL){ DisplayResultMatrix(); } BuildParallelAlgorithm(); if (argv[2] != NULL){ // output filename WriteResultParallelMatrix(argv[2]); } else { DisplayResultParallelMatrix(); } if (argv[2] == NULL){ // display key features printf ("\n\nKey features of parallel algorithm:\n\n"); printf ("1) Height: h = %i\n",height+1); printf ("2) Width: l = %i\n",CPU); accel = (float)operations/(height+1); printf ("3) Acceleration: S = %.4f\n",accel); printf ("4) Effectiveness: Ep = %.4f\n",(float)accel/CPU); } } 1.2.4 Результаты работы программы Запуск программы: ml-mpo-lab2.exe matrixes.txt Данные, а также ход работы, выводятся на экран. Input Matrixes: Matrix A a11 a12 0 0 0 0 0 0 a21 0 a23 a24 0 0 0 0 0 a32 0 a34 a35 0 0 0 0 0 a43 0 a45 0 0 0 0 0 0 a54 0 a56 0 0 0 0 0 0 0 0 a67 0 0 0 0 0 0 0 a77 0 Matrix B b11 b12 0 0 0 b21 0 b23 b24 0 0 b32 0 b34 b35 0 0 b43 0 b45 0 0 0 b54 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Reorganized Matrixes: Matrix A a11 a12 0 0 0 0 0 a21 0 a23 a24 0 0 0 0 a32 0 a34 a35 0 0 0 0 a43 0 a45 0 0 0 0 0 a54 0 a56 0 0 0 0 0 0 0 a67 0 0 0 0 0 0 a77 Matrix B b11 b12 0 0 0 b21 0 b23 b24 0 0 b32 0 b34 b35 0 0 b43 0 b45 0 0 0 b54 0 0 0 0 0 0 0 0 0 0 0 Resulting matrix C = A x B Matrix C a11*b11+a12*b21 a11*b12 a12*b23 a12*b24 0 a21*b11 a21*b12+a23*b32 a24*b43 a23*b34 a23*b35+a24*b45 a32*b21 0 a32*b23+a34*b43 a32*b24+a35*b54 a34*b45 0 a43*b32 0 a43*b34+a45*b54 a43*b35 0 0 a54*b43 0 a54*b45 0 0 0 0 0 0 0 0 0 0 Resulting matrix of parallel algorithm: a11*b11=c1 a12*b21=c2 a11*b12=c3 a12*b23=c4 a12*b24=c5 a21*b11=c6 a21*b12=c7 a23*b32=c8 c1+c2=d1 c7+c8=d2 a24*b43=d3 a23*b34=d4 a23*b35=d5 a24*b45=d6 a32*b21=d7 a32*b23=d8 d5+d6=e1 a34*b43=e2 a32*b24=e3 a35*b54=e4 a34*b45=e5 a43*b32=e6 a43*b34=e7 a45*b54=e8 d8+e2=f1 e3+e4=f2 e7+e8=f3 a43*b35=f4 a54*b43=f5 a54*b45=f6 Key features of parallel algorithm: 1) Height: h = 4 2) Width: l = 8 3) Acceleration: S = 7.5000 4) Effectiveness: Ep = 0.9375 1.2.10 Входные и выходные данные matrixes.txt a a 0 0 0 0 0 0 a 0 a a 0 0 0 0 0 a 0 a a 0 0 0 0 0 a 0 a 0 0 0 0 0 0 a 0 a 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 a 0 b b 0 0 0 b 0 b b 0 0 b 0 b b 0 0 b 0 b 0 0 0 b 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Запуск программы: ml-mpo-lab2.exe matrixes.txt result.txt Данные и ход работы не выводятся на экран, результат записывается в файл. result.txt a11*b11=c1 a12*b21=c2 a11*b12=c3 a12*b23=c4 a12*b24=c5 a21*b11=c6 a21*b12=c7 a23*b32=c8 c1+c2=d1 c7+c8=d2 a24*b43=d3 a23*b34=d4 a23*b35=d5 a24*b45=d6 a32*b21=d7 a32*b23=d8 d5+d6=e1 a34*b43=e2 a32*b24=e3 a35*b54=e4 a34*b45=e5 a43*b32=e6 a43*b34=e7 a45*b54=e8 d8+e2=f1 e3+e4=f2 e7+e8=f3 a43*b35=f4 a54*b43=f5 a54*b45=f6 |
Методы и средства организации обработки потоковой информации на распределенных... Специальность 05. 13. 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей | Нир: “разработка алгоритмов поиска глобальных экстремумов при наличии... Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования “Саратовский государственный... | ||
Тема: «Аксиома параллельных прямых» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Реферат в связи с большими объемами перерабатываемой информации в... Цель работы – приобретение практических навыков распараллеливания процесса вычислений при решении вычислительных задач большой размерности... | ||
«Реализация фгос на уроках математики: нетрадиционные уроки» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Календарно-тематическое планирование учебного материала Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | ||
Дидактические: 1 продолжить формирование зун по теме «параллельные прямые» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Г. Н. Флерова «утверждаю» Директор Н. Г. Кренделева Приказ от «30»августа... Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | ||
Методические рекомендации по изучению дисциплины теория и методика... Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Рабочая программа составлена в соответствии с требованиями федерального... Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | ||
Конспект урока решение задач по теме «Параллельные прямые» (Тема урока) фио (полностью) Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Методы решения задач с переменной интенсивностью потоков данных на... Специальность 05. 13. 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей | ||
Лекция № Тема: логические основы ЭВМ В вычислительных машинах коды нуля и единицы представляются электрическими сигналами, имеющими два различных состояния. Наиболее... | Рабочая программа учебной дисциплины вычислительные системы Целью курса «Вычислительные системы» является изучение общих сведений о многопроцессорных вычислительных системах, включая их назначение,... | ||
Диплом разработка и исследование информационных моделей шифратора и дешифратора Во многих устройствах, в том числе и в электронно-вычислительных машинах (эвм), используются кодированные сигналы или коды. Кодом... | Программа по формированию навыков безопасного поведения на дорогах... Знать: определение параллельных прямых в пространстве. Уметь: анализировать в простейших случаях взаимное расположение прямых в пространстве,... |