Всвязи с большими объемами перерабатываемой информации в сложных вычислительных системах возможным путем решения возникающих в них задач является распараллеливание ВІДКРИТИЙ МІЖНАРОДНИЙ УНІВЕРСИТЕТ РОЗВИТКУ ЛЮДИНИ “УКРАЇНА” ЛАБОРАТОРНА РОБОТА №1 "РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ МЕТОДОМ АЛГЕБРАїЧНИХ ПЕРЕТВОРЕНЬ" з дисципліни " Методи паралельних обчислень " спеціальності " Програмне забезпечення автоматизованих систем " Виконав студент 3 курсу групи ПА-21 ______________ Докукін Є.В . (підпис) (Прізвище І.Б.) "____"____________ 2005 р. ЗАРАХОВАНО Викладач ________________ Доля В.Г. "____"____________ 200__ р. Київ Університет "Україна" 2005 СОДЕРЖАНИЕ 1.1. . 3 1.2. Решение задачи перемножения двух прямоугольных матриц большой размерности. 3 1.2.1 Постановка задачи. 3 1.2.2 Блок-схема алгоритма. 6 1.2.3 Листинг текста программы.. 7 1.2.4 Результаты работы программы.. 10 1.2.5 Входные и выходные данные. 11 1.3. Литература. 12 1 . Лабораторная работа №1 "Распараллеливание вычислений методом алгебраических преобразований" Цель работы – приобретение практических навыков распараллеливания процесса вычислений при решении вычислительных задач большой размерности с использованием метода алгебраических преобразований. 1.1. В связи с большими объемами перерабатываемой информации в сложных вычислительных системах возможным путем решения возникающих в них задач является распараллеливание (распределение) потоков информации и вычислительных процессов между вычислительными средствами (ресурсами) системы. Распараллеливание процессов вычислений многовариантно. Распараллеливание вычислений может быть организовано на уровнях: · региональных (территориальных) вычислительных систем; · вычислительных комплексов (узлов) отдельного территориального региона; · вычислительных машин отдельного вычислительного комплекса (узла); · отдельных функциональных устройств ПВМ (процессоров, устройств памяти и др.). Распараллеливание вычислений может осуществляться путем параллельной организации математических и программных средств вычислений, в том числе: · метода решения поставленной задачи; · математической модели исследуемого объекта или процесса; · алгоритма решения задачи; · программных средств решения задачи и др. Основными методами распараллеливания вычислений являются: · упрощение структуры решаемой задачи с помощью алгебраических преобразований; · искусственное расщепление (декомпозиция) задачи на ряд подзадач меньшей размерности; · агрегирование выполняемых операций; · организация макроалгоритмов процесса вычислений и др. 1.2. Решение задачи перемножения двух прямоугольных матриц большой размерности 1.2.1 Постановка задачи 1.1. Выбрать свой вариант задания на выполнение работы из Табл.1.1. По варианту задания № 17, выбраны соответствующие матрицы А и В. Табл. 1.1. Варианты заданий № задания Размерность Матрица А Матрица В 17 7 х 8 8 х 5 1.2. Используя свой вариант задания и данные табл.1.2, строятся исходные матрицы для выполнения работы. Входные матрицы А[7,8] и В[8,5] будут иметь вид: Матрица А[7,8] Номера строк Номера столбцов 1 2 3 4 5 6 7 8 1 а11 а12 0 0 0 0 0 0 2 а21 0 а23 а24 0 0 0 0 3 0 а32 0 а34 а35 0 0 0 4 0 0 а43 0 а45 0 0 0 5 0 0 0 а54 0 а56 0 0 6 0 0 0 0 0 0 а67 0 7 0 0 0 0 0 0 а77 0 Матрица В[8,5] Номера строк Номера столбцов 1 2 3 4 5 1 b11 b12 0 0 0 2 b21 0 b23 b24 0 3 0 b32 0 b34 b35 4 0 0 b43 0 b45 5 0 0 0 b54 0 6 0 0 0 0 0 7 0 0 0 0 0 8 0 0 0 0 0 1.3. Выполняется распараллеливание задачи путем ее алгебраических преобразований, т.е. в данном случае – путем исключения из матриц нулевых строк и столбцов. Строятся матрицы, полученные в результате распараллеливания. В данном случае матрица А[7,8] содержит один (восьмой) нулевой столбец, а матрица В[8,5] имеет три (шестая, седьмая и восьмая) нулевых строки, часть из которые в данном случае можно исключить. При этом следует учесть, что после исключения нулевых строк и столбцов, число элементов в каждой строке матрицы А должно быть равно числу элементов в каждом столбце матрицы В. Иначе матрицы нельзя будет перемножить. В данном случае можно исключить восьмой столбец матрицы А и восьмую строку матрицы B. Строки 6 и 7 матрицы В исключить нельзя. В результате матрицы А и В преобразуются к виду: Матрица А[7,7] Номера строк Номера столбцов 1 2 3 4 5 6 7 1 а11 а12 0 0 0 0 0 2 а21 0 а23 а24 0 0 0 3 0 а32 0 а34 а35 0 0 4 0 0 а43 0 а45 0 0 5 0 0 0 а54 0 а56 0 6 0 0 0 0 0 0 а67 7 0 0 0 0 0 0 а77 Матрица В[7,5] Номера строк Номера столбцов 1 2 3 4 5 1 b11 b12 0 0 0 2 b21 0 b23 b24 0 3 0 b32 0 b34 b35 4 0 0 b43 0 b45 5 0 0 0 b54 0 6 0 0 0 0 0 7 0 0 0 0 0 1.4. Строится результирующая матрица С путём перемножения матриц А и В, полученных в результате распараллеливания. Для данного примера матрица С будет иметь вид: Матрица С [7,5] Номера строк Номера столбцов 1 2 3 4 5 1 а11 b11 +а12 b21 а11 b12 а12 b23 а12 b24 0 2 а21 b11 а21 b12 +а23 b32 а24 b43 а23 b34 а23 b35 +а24 b45 3 а32 b21 0 а32 b23 +а34 b43 а32 b24 +а35 b54 а34 b45 4 0 а43 b34 0 а43 b34 +а45 b54 а43 b35 5 0 0 а54 b43 0 а54 b45 6 0 0 0 0 0 7 0 0 0 0 0 1.2.2 Блок-схема алгоритма 1.2.3 Листинг текста программы ml-mpo-lab1.c /* Program for task solution of multiplication of two rectangular big dimension matrixes * Решение задачи перемножения двух прямоугольных матриц большой размерности * Copyright (C) 2005 Eugene Dokukin aka MustLive. http://mlbpg.narod.ru * Open Source Software, GPL. http://www.gnu.org */ #include <stdio.h> // 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 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 int MatrixA[SIZE_Ia][SIZE_Ja]; // matrix A int MatrixB[SIZE_Ib][SIZE_Jb]; // matrix B int MatrixC[SIZE_Ia][SIZE_Jb]; // matrix C void Error () { // enter correct parameters printf ("\nProgram for task solution of multiplication\n"); printf ("of two rectangular big dimension 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<A_I;i++) { for (j=0;j<A_J;j++) { MatrixA[i][j] = 0; } } for (i=0;i<B_I;i++) { for (j=0;j<B_J;j++) { MatrixB[i][j] = 0; } } for (i=0;i<A_I;i++) { for (j=0;j<B_J;j++) { MatrixC[i][j] = 0; } } } void ReadMatrixes (char filename[255]) { // open file and read two matrixes FILE *fp; // pointer on file int i,j; // counters if ( (fp = fopen(filename, "r")) == NULL) { Error(); fprintf(stderr, "Error opening file %s.\n",filename); exit(0); } else { for (i=0;i<A_I;i++) { for (j=0;j<A_J-1;j++) { fscanf (fp, "%i ",&MatrixA[i][j]); if ( feof(fp) ) break; NULL_Ia[i] = NULL_Ia[i] + MatrixA[i][j]; NULL_Ja[j] = NULL_Ja[j] + MatrixA[i][j]; } fscanf (fp, "%i\n",&MatrixA[i][j]); NULL_Ia[i] = NULL_Ia[i] + MatrixA[i][j]; NULL_Ja[j] = NULL_Ja[j] + MatrixA[i][j]; if ( feof(fp) ) break; } fscanf (fp,"\n"); for (i=0;i<B_I;i++) { for (j=0;j<B_J-1;j++) { fscanf (fp, "%i ",&MatrixB[i][j]); if ( feof(fp) ) break; NULL_Ib[i] = NULL_Ib[i] + MatrixB[i][j]; NULL_Jb[j] = NULL_Jb[j] + MatrixB[i][j]; } fscanf (fp, "%i\n",&MatrixB[i][j]); NULL_Ib[i] = NULL_Ib[i] + MatrixB[i][j]; NULL_Jb[j] = NULL_Jb[j] + MatrixB[i][j]; 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; // counters for (i=0;i<A_I;i++) { for (j=0;j<B_J;j++) { for (k=0;k<A_J;k++) { MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j]; } } } } void DisplayInputMatrixes () { // display input matrixes int i,j; // counters printf ("\nMatrix A\n\n"); for (i=0;i<A_I;i++) { for (j=0;j<A_J;j++) { printf("%i\t",MatrixA[i][j]); } printf("\n"); } printf ("\nMatrix B\n\n"); for (i=0;i<B_I;i++) { for (j=0;j<B_J;j++) { printf("%i\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<A_I;i++) { for (j=0;j<B_J;j++) { printf("%i\t",MatrixC[i][j]); } printf("\n"); } } void WriteResultMatrix (char filename[255]) { // open file and write resulting matrix 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<A_I;i++) { for (j=0;j<B_J;j++) { fprintf(fp,"%i\t",MatrixC[i][j]); } fprintf(fp,"\n"); } } fclose(fp); } int main (int argc, char *argv[]) { 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){ // output filename WriteResultMatrix(argv[2]); } else { DisplayResultMatrix(); } } 1.2.4 Результаты работы программы Запуск программы: ml-mpo-lab1.exe matrixes.txt Данные, а также ход работы, выводятся на экран. Input Matrixes: Matrix A 1 2 0 0 0 0 0 3 0 4 5 0 0 0 0 6 0 7 8 0 0 0 0 1 0 2 0 0 0 0 0 3 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Matrix B 2 3 0 0 0 1 0 5 6 0 0 4 0 1 2 0 0 3 0 4 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Reorganized Matrixes: Matrix A 1 2 0 0 0 0 3 0 4 5 0 0 0 6 0 7 8 0 0 0 1 0 2 0 0 0 0 3 0 4 0 0 0 0 0 0 0 0 0 0 0 0 Matrix B 2 3 0 0 0 1 0 5 6 0 0 4 0 1 2 0 0 3 0 4 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 Resulting matrix C = A x B Matrix C 4 3 10 12 0 6 25 15 4 28 6 0 51 76 28 0 4 0 11 2 0 0 9 0 12 0 0 0 0 0 0 0 0 0 0 1.2.5 Входные и выходные данные matrixes . txt 1 2 0 0 0 0 0 0 3 0 4 5 0 0 0 0 0 6 0 7 8 0 0 0 0 0 1 0 2 0 0 0 0 0 0 3 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 6 0 2 3 0 0 0 1 0 5 6 0 0 4 0 1 2 0 0 3 0 4 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Запуск программы: ml-mpo-lab1.exe matrixes.txt result.txt Данные и ход работы не выводятся на экран, результат записывается в файл. result.txt 4 3 10 12 0 6 25 15 4 28 6 0 51 76 28 0 4 0 11 2 0 0 9 0 12 0 0 0 0 0 0 0 0 0 0 1.3. Литература 1. Воеводин В.В. Математические основы параллельных вычислений. – М.: МГУ, 1991. – 345 с. 2. Воеводин В.В. Параллельные вычисления. – СПб: БХВ-Петербург. – 2002. 3. Молчанов И.Н. Введение в алгоритмы параллельных вычислений. К.: Наукова думка. - 1990 – 128 с. 4. Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. – К.: Наукова думка, 2000 – 177 с.