Реферат: Всвязи с большими объемами перерабатываемой информации в сложных вычислительных системах возможным путем решения возникающих в них задач является распараллеливание

ВІДКРИТИЙ МІЖНАРОДНИЙ УНІВЕРСИТЕТ

РОЗВИТКУ ЛЮДИНИ “УКРАЇНА”

ЛАБОРАТОРНА РОБОТА №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. Варианты заданий

1.2. Используя свой вариант задания и данные табл.1.2, строятся исходные матрицы для выполнения работы.

Входные матрицы А[7,8] и В[8,5] будут иметь вид:

Матрица А[7,8]

Матрица В[8,5]

1.3. Выполняется распараллеливание задачи путем ее алгебраических преобразований, т.е. в данном случае – путем исключения из матриц нулевых строк и столбцов. Строятся матрицы, полученные в результате распараллеливания.

В данном случае матрица А[7,8] содержит один (восьмой) нулевой столбец, а матрица В[8,5] имеет три (шестая, седьмая и восьмая) нулевых строки, часть из которые в данном случае можно исключить. При этом следует учесть, что после исключения нулевых строк и столбцов, число элементов в каждой строке матрицы А должно быть равно числу элементов в каждом столбце матрицы В. Иначе матрицы нельзя будет перемножить.

В данном случае можно исключить восьмой столбец матрицы А и восьмую строку матрицы B. Строки 6 и 7 матрицы В исключить нельзя.

В результате матрицы А и В преобразуются к виду:

Матрица А[7,7]

Матрица В[7,5]

1.4. Строится результирующая матрица С путём перемножения матриц А и В, полученных в результате распараллеливания. Для данного примера матрица С будет иметь вид:

Матрица С [7,5]

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 с.

5. Малышкин В.Э. Основы параллельных вычислений. Учебное пособие. – Новосибирск: Изд-во НГТУ, 2000.