ВІДКРИТИЙ МІЖНАРОДНИЙ УНІВЕРСИТЕТ
РОЗВИТКУ ЛЮДИНИ “УКРАЇНА”
ЛАБОРАТОРНА РОБОТА №1
"РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ
МЕТОДОМ АЛГЕБРАїЧНИХ ПЕРЕТВОРЕНЬ"
з дисципліни
"Методи паралельних обчислень "
спеціальності
"Програмне забезпечення автоматизованих систем"
Виконав студент 3 курсу
групи ПА-21
______________ Докукін Є.В.
(підпис) (Прізвище І.Б.)
"____"____________ 2005 р.
ЗАРАХОВАНО
Викладач ________________ Доля В.Г.
"____"____________ 200__ р.
Київ
Університет "Україна"
2005
СОДЕРЖАНИЕ
1.1.Реферат 3
Табл. 1.1. Варианты заданий 3
1. Лабораторная работа №1
"Распараллеливание вычислений
методом алгебраических преобразований"
Цель работы – приобретение практических навыков распараллеливания процесса вычислений при решении вычислительных задач большой размерности с использованием метода алгебраических преобразований.
Реферат
В связи с большими объемами перерабатываемой информации в сложных вычислительных системах возможным путем решения возникающих в них задач является распараллеливание (распределение) потоков информации и вычислительных процессов между вычислительными средствами (ресурсами) системы. Распараллеливание процессов вычислений многовариантно.
Распараллеливание вычислений может быть организовано на уровнях:
региональных (территориальных) вычислительных систем;
вычислительных комплексов (узлов) отдельного территориального региона;
вычислительных машин отдельного вычислительного комплекса (узла);
отдельных функциональных устройств ПВМ (процессоров, устройств памяти и др.).
Распараллеливание вычислений может осуществляться путем параллельной организации математических и программных средств вычислений, в том числе:
метода решения поставленной задачи;
математической модели исследуемого объекта или процесса;
алгоритма решения задачи;
программных средств решения задачи и др.
Основными методами распараллеливания вычислений являются:
упрощение структуры решаемой задачи с помощью алгебраических преобразований;
искусственное расщепление (декомпозиция) задачи на ряд подзадач меньшей размерности;
агрегирование выполняемых операций;
организация макроалгоритмов процесса вычислений и др.
1.2. Решение задачи перемножения двух прямоугольных матриц большой размерности
1.2.1 Постановка задачи
Выбрать свой вариант задания на выполнение работы из Табл.1.1.
По варианту задания № 17, выбраны соответствующие матрицы А и В.
Табл. 1.1. Варианты заданий
| № задания | Размерность | |
| Матрица А | Матрица В | |
| 17 | 7 х 8 | 8 х 5 |
Используя свой вариант задания и данные табл.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 |
Выполняется распараллеливание задачи путем ее алгебраических преобразований, т.е. в данном случае – путем исключения из матриц нулевых строк и столбцов. Строятся матрицы, полученные в результате распараллеливания.
В данном случае матрица А[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 |
Строится результирующая матрица С путём перемножения матриц А и В, полученных в результате распараллеливания. Для данного примера матрица С будет иметь вид:
Матрица С [7,5]
| Номера строк | Номера столбцов | ||||
| 1 | 2 | 3 | 4 | 5 | |
| 1 | а11b11+а12b21 | а11b12 | а12b23 | а12b24 | 0 |
| 2 | а21b11 | а21b12+а23b32 | а24b43 | а23b34 | а23b35+а24b45 |
| 3 | а32b21 | 0 | а32b23+а34b43 | а32b24 +а35b54 | а34b45 |
| 4 | 0 | а43b34 | 0 | а43b34+а45b54 | а43b35 |
| 5 | 0 | 0 | а54b43 | 0 | а54b45 |
| 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. mlbpg.narod
* Open Source Software, GPL. gnu */
#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 multiplicationn");
printf ("of two rectangular big dimension matrixesn");
printf ("Copyright (C) 2005 MustLive. mlbpg.narodn");
printf ("Open Source Software, GPL. gnunn");
}
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, "%in",&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, "%in",&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 Ann");
for (i=0;i<A_I;i++) {
for (j=0;j<A_J;j++) {
printf("%it",MatrixA[i][j]);
}
printf("n");
}
printf ("nMatrix Bnn");
for (i=0;i<B_I;i++) {
for (j=0;j<B_J;j++) {
printf("%it",MatrixB[i][j]);
}
printf("n");
}
}
void DisplayResultMatrix () { // display resulting matrix
int i,j; // counters
printf ("nnResulting matrix C = A x Bn");
printf ("nMatrix Cnn");
for (i=0;i<A_I;i++) {
for (j=0;j<B_J;j++) {
printf("%it",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,"%it",MatrixC[i][j]);
}
fprintf(fp,"n");
}
}
fclose(fp);
}
int main (int argc, char *argv[]) {
if (argv[1] == NULL){ // input filename
Error();
printf ("%s filenamen",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 ("nnReorganized 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. Литература
Воеводин В.В. Математические основы параллельных вычислений. – М.: МГУ, 1991. – 345 с.
Воеводин В.В. Параллельные вычисления. – СПб: БХВ-Петербург. – 2002.
Молчанов И.Н. Введение в алгоритмы параллельных вычислений. К.: Наукова думка. - 1990 – 128 с.
Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. – К.: Наукова думка, 2000 – 177 с.
Малышкин В.Э. Основы параллельных вычислений. Учебное пособие. – Новосибирск: Изд-во НГТУ, 2000.